请参阅下面的解决方案，我想要一些建设性的反馈。
下面的 O(n) 运行时间是多少。
int a = 0;
int k = n*n*n; //n^3
while(k > 1)
{
for (int j=0; j<k; j++) //runs from 0->k
{ a--; }
k = k/2; //divides by 2 each iteration
}
每次 for 循环运行时，它都会给出一个常数 x k。
= 0xn^3 + 1x (n^3/2) + 2x(n^3/4) +...+ nx(n^3/2^n)
= n^3 (0 + 1/2 + 2/4 +...+ n/2^n) <- 有人知道我如何进一步简化它吗？
编辑:我假设我们会以某种方式使用算术级数......
最佳答案
让我们先使用 k
在第一个 while 循环中，for 循环运行 k 次
在第二个 while 循环中，for 循环运行 k/2 次
在第三个 while 循环中，for 循环运行 k/4 次
...
因此总共运行 ( k + k/2 + k/4 + k/8 + ... + 1) 次
提取k后，为k * ( 1 + 1/2 + 1/4 + 1/8 + ... + 1/k)
随着k的增加，括号内的部分变成2，我们可以忽略
将k改为n^3，结果为O(n^3)
关于algorithm - 循环迭代分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11112137/