判断一段伪代码的运行次

Question

我有以下伪代码，我想确定它的运行时间 T(n)。有人可以给我我应该遵循的步骤吗？这是代码：

i := 1;
while (i <= n)
   j := i;
   x := x+A[i];
   while (j > 0)
      y := x/(2*j);
      j = j /2; // Assume here that this returns the floor of the quotient
   i = 2 * i;
return y;

Answer 1

如果我的计算没有错，我认为是O(log log N)

首先，我们省略不影响循环次数的行，同样假设数组随机访问为O(1)。

i := 1;
while (i <= n)
   j := i;
   while (j > 0)
      j = j / 2;
   i = 2 * i;
return y;

那我们假设一行的所有操作都在O(1)内完成，我们将它们相加得到结果。

除了数学分析，我们还可以使用计算：我们运行片段多次，看时间增长（我也省略了不影响循环时间的操作）。

#include <iostream>
using namespace std;

int main(){
    long long i, j, n;
    double cost;
    clock_t start, finish;
    i = 1;
    n = 1000000000000;
    start = clock();
    while (i <= n) {
        j = i;
        while (j > 0) {
            j = j / 2;
        }
        i = 2 * i;
    }
    finish = clock();
    cout << (double)(finish - start)/CLOCKS_PER_SEC << endl;
}

判断一段伪代码的运行次

Determine the run-time of a pseudo code

algorithm

runtime

pseudocode