確定僞代碼的運行時間

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