寻找增长函数

Question

我正在寻找给定代码的增长函数。

int sum = 0; 
 for (int k = n; k > 0; k /= 2)  {
    cout<<k<<endl;
    for (int i = 0; i < k; i++) 
    {
        sum++; 
        cout<<i<<endl;
    }
 }

但我卡在了 (int k = n; k > 0; k /= 2) 的第一个循环中，它以这种方式执行：

for n = 5 , it executes 3 times
n = 10 , 4 times
n = 100 , 7 times
n = 1000 , 10 times

我如何概括它？

Answer 1

每一步将k除以二，切成两半。您需要削减多少次才能归零？

1 次切割后你有 n/2。
2 次削减后你有 n/4.
削减 3 次后你有 n/8.
4 次削减后你有 n/16.
5 次削减后你有 n/32.
x 削减后你有 n/2x.

所以，还有多久 n = 2x?
答案很简单：x = log2(n).

你的循环运行秒 log n 次。

但是内部循环运行是关于这些部分的大小的。第一个运行的大小是 n，第二个是 n/2，第三个是 n/4，依此类推。这个内循环所有运行的总和是：

n + n/2 + n/4 + n/8 + ... = 2n.

因此总运行时间等于 O(n)（感谢 Douglas Zare！）

Answer 2

首先，10大约是1000的log_2。外循环大约有log_2(n)次迭代。但是，这并不能告诉您总步数，因为您在其中执行了可变数量的步数。

n + n/2 + n/4 + n/8 + ... = 2n = O(n)。您在循环内做的事情数量不变，因此总步数为 O(n)。当 k=n.

时，大约一半的时间花在外循环的第一次迭代上

寻找增长函数

Finding growth Function

c++

time-complexity

big-o