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

Question

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

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

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

score 10 · Accepted Answer

它是O(logn)，因为i每次都加倍。因此，总的来说，您需要迭代k时间，直到2^k = n，在这种情况下，它发生在k = logn(since 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)）我怀疑这实际上是您正在寻找的。

score 3 · Accepted Answer

3

复杂度为O(logn)，因为循环运行 (log ₂ n - 1) 次。

于 2012-08-20T06:51:35.157 回答

score 2 · Accepted Answer

2

O(log(n))，因为你只循环 ~log2(n) 次

于 2012-08-20T06:51:18.300 回答

score 1 · Accepted Answer

不，复杂性不是线性的。尝试玩几个场景：对于 n = 2、n=4、n=16、n=1024，这个循环做了多少次迭代？n = 1024 * 1024 怎么样？也许这会帮助你得到正确的答案。

score 0 · Accepted Answer

0

它是 O(log(n))。看代码num++；它循环 O(log(n)) 次。

于 2012-08-20T07:04:21.313 回答

score 0 · Accepted Answer

For 循环检查运行 lg(n) +1 次。内部循环运行 lg(n) 次。所以，复杂度是 O(lg n)，而不是 O(log n)。

如果 n==8，以下是代码的运行方式：

6 回答 6