以下代码的算法复杂性是什么？

Question

以下代码是O(n)还是O(log n)的Big-O？

for (int i = 1; i < n; i*=2)
        sum++;

它看起来像是O(n)还是我完全错过了这个？

Answer 1

它是O(logn),因为i每次加倍.所以总的来说,你需要迭代k一次,直到2^k = n,在这种情况下,它发生在k = logn(自2^logn = n).

简单示例:假设n = 100- 然后:

iter1: i = 1
iter2: i = 2
iter3: i = 4
iter4: i = 8
iter5: i = 16
iter6: i = 32
iter7: i = 64
iter8: i = 128 > 100

很容易看出,当n加倍时会添加迭代,这是对数行为,而线性行为则是为了不断增加迭代而添加迭代n.

PS(编辑):从 数学角度来说,算法确实是O(n)- 因为大O符号给出渐近上界,并且你的算法渐近"更快"运行O(n)- 所以它确实是O(n)- 但它不是一个紧束缚(它不是Theta(n))我怀疑这实际上是你在找什么.