fun()的时间复杂度是多少？

Question

我正在阅读这个问题以计算时间复杂度。

int fun(int n)
{
  int count = 0;
  for (int i = n; i > 0; i /= 2)
     for (int j = 0; j < i; j++)
        count += 1;
  return count;
}

我的第一印象是O(n log n)，但答案却是O(n)。请帮我理解为什么它是O(n)。

- Prateek Joshi

Answer 1

内部循环执行 n 次迭代，然后是 n/2，然后是 n/4，以此类推。 因此，内部循环的总迭代次数为：

   n + n/2 + n/4 + n/8 + ... + 1  
<= n * (1 + 1/2 + 1/4 + 1/8 + ...) 
 = 2n

(见几何级数)，因此时间复杂度为O(n)。

- interjay

---

外层循环怎么办？ - Luniam

@Luniam 外层循环的迭代次数少于O(n)（实际上是O(logn)），因此不会影响大O复杂度。 - interjay

这就是我作为OP感到困惑的地方。外层循环是O(logn)，内层循环是O(n)。因此，总时间复杂度为O(nlogn)。在这里感到困惑了...你能帮我吗？ - Luniam

@Luniam 内部循环每次不会执行n次迭代，而是更少。你需要的是它执行的总迭代次数，这就是我在我的答案中计算的。 - interjay

太棒了...解释一下，顺便说一句...如果有人对为什么(1 + 1/2 + 1/4 + 1/8 + ...)变成2感到困惑，那是因为这是一个无限等比数列的和，它等于(1/(1-r))，其中r是第n项和(n-1)项的比值，在我们的例子中是1/2，所以(1/(1-1/2))=2，所以他写了2*n。 - Ankur Verma

Answer 2

让我们拥有i和j表格

where n = 8

i -> 小于 0

j -> 小于 i

i	j
8	[0,7]
4	[0,3]
2	[0,1]
1	[0,0]

"i" 是外层循环，其时间复杂度为 logn

现在检查 "j" 的内层循环

[0, 7] -> b - a + 1 -> 8 -> n

[0, 3] -> b - a + 1 -> 4 -> n/2

[0, 1] -> b - a + 1 -> 2 -> n/4
[0, 0] -> b - a + 1 -> 1 -> n/n

如果你看到它是 [n + n/2 + n/4....1] ，它会一直增加到无穷大，而不是logn次数

如果我们仔细观察，它就是一个无限序列，这是一个等比数列 n[1 + 1/2 + 1/4 + .......] 其中 (r < 1)

序列的总和将给出2（有关等比数列的证明可以在谷歌上查找）

也就是说

n[1 + 1/2 + 1/4 + .......] -> 2n

so logn + 2n => O(n)

- Bhavesh

Answer 3

对于一个输入整数n，

for i=n, j 循环将运行n次， 然后 for i= n/2, j 循环将运行n/2次， . . 以此类推， . . 直到 i=1，其中 j 循环将运行1次。

因此，

T(n) = (n + n/2 + n/4 + n/8 + ...... + 1) 
    T(n) = n(1 + 1/2 + 1/4 + 1/8 + ..... + 1/n)                     .....(1)
let 1/n = 1/2^k

所以，k = logn

现在，使用等比数列求和公式在公式1中

T(n) = n((1-1/2^k) / 1-1/2)
T(n) = 2n(1-1/2^k)

using k = logn
T(n) = 2n(1-1/2^logn)

现在对于较大的 n，logn 趋近于无穷大，而 1/2^infinite 将趋近于 0。因此，T(n) = 2n，所以 T(n) = O(n)。

- SAVOO7

Answer 4

对于输入整数n，

fun()的最里层语句会被执行n + n/2 + n/4 + ... 1 次。因此时间复杂度T(n)可以写成

T(n) = O(n + n/2 + n/4 + ... 1) = O(n) count的值也为n + n/2 + n/4 + .. + 1

最外层循环迭代O(logn)次，所以被忽略，因为O(n)更高。

- Anupam Haldkar