c++ - 寻找增长函数

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

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

n + n/2 + n/4 + n/8 + ... = 2n = O(n)。您在循环内做的事情数量不变，因此总步数为 O(n)。当 k=n 时，大约一半的时间花在外循环的第一次迭代上。