大O符号和Σ符号

Question

如果someWork(..)恰好执行i次操作，那么这个循环的大O是多少？算法someWork(..)随着i的增加而增加工作量。如何用sigma符号表示解决方案？

i <--2
while (i < n)
   someWork (..)
   i <-- power (i,2)
done

首先，i <-- power (i,2) 的复杂度为 O(log n)，而someWork(..) 似乎也是 O(log n)，因为随着 i 的增加它会做更多的工作。将这两个复杂度相乘可得到 O((log n)²) 的复杂度。确认无误？

- user3818430

---

为什么？对我来说，整个代码的复杂度看起来是O(log n)。 - Rahul

这个伪代码是从哪里来的？有一个类似的问题看起来很相似：http://stackoverflow.com/q/24581182/3440545，但由于我的答案还没有被接受或投票，所以我不能标记它为重复。 - AbcAeffchen

O(log n) 看起来是正确的，因为它们相等且在同一个循环中，所以只需将两个复杂度相加即可。 - user3818430

O(log n) 不可能是对的。someWork(..) 在循环的最后一轮中至少需要 O(sqrt(n))。详见我的答案。 - AbcAeffchen

Answer 1

在每一轮循环中，2的指数将会翻倍。因此，在第k轮中，数字i将会是22k。只要22k < n成立，循环就会一直进行下去，这相当于k < log log n。确切地说是log₂ log₂ n，但由于所有对数都相等，除了一个常数因子，因此我只写成log log n。

如果someWork()在第k轮中做O(22k)次操作，则总复杂度为：

O( 2 + 22 + 222 + 223 + ... + 22log log n ) 

简化后为O(2 ⋅ 22log log n ) = O(n)。

为了看到简化过程，请看以下内容：
数字2 + 2² + 2⁴ + 2⁸可以用二进制写成100 010 110。因此，你可以看到：

2 + 221 + 222 + ... + 22k < 2 ⋅ 22k

成立，因为它等于100 010 110 < 1 000 000 000。 编辑：

- AbcAeffchen