algorithm - 循环迭代分析

Question

请参阅下面的解决方案，我想要一些建设性的反馈。

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 循环运行时，它都会给出一个常量 xk。

= 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) <- 谁知道我如何进一步简化它？

编辑:我假设我们会以某种方式使用算术级数......

Answer 1

我们先用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)