就 n 而言，此函数的复杂性是多少？

Question

f(n):
   s = 1
   m = n
   while m >= 1:
       for j in 1,2,3, .., m:
           s = s + 1
       m = m / 2

我的尝试

s = s + 1运行语句重复了多少次？好吧，让我们为 n 尝试一两个数字，看看我们得到了什么。

n = 32
m = n = 32

m = 32 => inner for loop, loops 32 times
m = 16 => -.- 16 times
m =  8 => -.- 8 times
m =  4 => -.- 4 times
m =  2 => -.- 2 times
m =  1 => -.- 1 time

In total 16+8+4+2+1 = 31 times for n = 32

Doing the same for n = 8 gives 15 times
Doing the same for n = 4 gives 7 times
Doing the same for n = 64 gives 127 times

注意它看起来总是2 * n - 1，我相信这不是巧合，因为我们真正观察到的是语句执行的总次数等于几何和sum of 2^k from k=0 to k=log(n) 它有一个封闭形式的解决方案 2n + 1 鉴于我们使用的是 2 底对数。

因此，我的猜测是复杂度为 O(n)。

这是正确的吗？

Answer 1

嗯，你刚才观察到的确实是真的。我们也可以用数学证明。

第一次迭代的内循环执行 -> n
第二次迭代的内循环执行 -> n/2
第三次迭代的内循环执行 -> n/(2^2) 等等....

因此总时间为 (n + (n/2) + (n/(2^2)) + ... + (n/(2^k))) 其中 n/(2^ k) 应该等于 1，这意味着 k = log(n)。从所有项中取 n common 会给我们一个 GP 现在使用上面系列中的 GP 公式，总时间将是 1(1 - ((1/2)^k)) / (1 - 1/2)。输入 k = log(n) 的值，我们将得到总时间为 2*(n-1).

备注-:

这给了我们 O(n) 的时间复杂度。
log 以 2 为底。

就 n 而言，此函数的复杂性是多少？

What is the complexity of this function in terms of n?

complexity-theory

big-o

time-complexity