我正在尝试分析一种算法，在最坏的情况下确实如此
log(1) + log(2) + log(4) + log(n_i) + ... + log(log(n))
工作量。其中 n_i 是 2 的幂。
我的尝试是这样说，因为：
1 + 2 + 3 + ... + n
是 O(n^2)，我的算法是 O(log(n^2)) = O(2log(n))。
这个对吗？
此外，我只希望每个 log(n_i) 项以 0.5 的独立概率出现。那么，我可以声称上面的预期复杂度为 O(2log(n)/2) = O(log(n))？
磅(1) + 磅(2) + 磅(4) + ... + 磅(磅(n))
= 磅(2 0 ) + 磅(2 1 ) + 磅(2 2 ) + ... + 磅(2磅(lb(n)) )
= 0 + 1 + 2 + ... + 磅（磅（n））
= O([lb(lb(n))] 2 )
令 X(i) 为表示第 i 项的随机变量，其中 X(i) = lb(2 i ) = i 概率为 1/2，否则 X(i) = 0。那么 E[X(i)] = i/2。
所以 X(0) + X(1) + ... + X(lb(lb(n))) 的期望只是上述确定性结果的 1/2，由期望的线性决定。也就是说，预期的复杂度仍然是 O([lb(lb(n))] 2 )。
请注意，在处理渐近复杂度时，log（以 e 为底）和 lb（以 2 为底）之间的区别无关紧要，因为 log(x) = lb(x)/lb(e) 和 lb(e) 是一个常数。