下面代码的算法复杂度是多少

Question

以下代码的Big-O是O（n）还是O（logn）？

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的恒定增加添加迭代。

p。S.（编辑）：从数学上讲，该算法确实是O(n)-因为big-O表示法给出了渐近上界并且你的算法运行得比O(n)渐近"更快"-所以它确实是O(n)-但它不是紧界（它不是Theta(n)），我怀疑这实际上是你想要的。

Answer 2

复杂性为O（logn），因为循环运行（log₂n-1）次。

Answer 3

O（log（n）），因为您只循环~log2（n）次

Answer 4

对于循环检查运行lg（n）+1次。内部循环运行lg（n）次。因此，复杂性是O（lgn），而不是O（logn）。

如果n=8，代码将如何运行：

1. i=1
2. i=2
3. i=4
4. i=8——退出条件

Answer 5

它是O（log（n））。查看代码num++；它循环O（log（n））次。