擬似コードの実行時間を決定する

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; 

次に、1行のすべての操作が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; 
}