确定伪代码的运行时间

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; 
}