大 O 西格玛符号

Question

如果 someWork(..)，这个循环的大 O 是什么？确实i操作？算法someWork(..)做更多的工作作为 i增加。如何用西格玛符号表示解？

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)²) .确认？

Answer 1

在循环的每一轮中 2 的指数会翻倍。所以在k -th 轮数 i将是 22k .
只要 22k < n，循环就会持续下去成立，相当于k < log log n .正是log₂ log₂ n ，但由于除常数因子外，所有对数都相等，我只写 log log n .

如 someWork()是否O(22k)本轮操作k ，你得到的总复杂度为

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 .

编辑 :