Big（o）の図解

Question

このコードを実行すると、合計30回実行されます。私は外側ループがNを実行することを知っていますが、内部ループはとBig（O）を見つけようとする前にではなく、i*iのようなものを見たことがありません。

Answer 1

このアルゴリズムはO(n^3)です：私たちが実行される頻度を内部コード

cout << j << endl; 
result++; 

把握する必要があり、これを実現するために。このためには、よく知られた結果である1*1+2*2+...+n*n = n^3/3+n^2/2+n/6を要約する必要があります（例えば、Sum of the Squares of the First n Natural Numbersを参照）。従って、O(T(n)) = O(1*1+2*2+...+n*n) = O(n^3)であり、アルゴリズムの（時間）複雑さはO(n^3)である。

編集：これで十分であるなぜあなたは（Time complexity with examplesでも、実施例4を参照）迷っているならば、我々はループが命令の一定量を（追加することを見ることができるように、単一のループとして、あなたのコードを書き換えることは有用です

int i = 0; 
int j = 0; 

while(i < n) { 
    cout << j << endl; 
    result++; 
    if(j < i * i) j++; //were still in the inner loop 
    else {//start the next iteration of the outer loop 
     j = 0; 
     i++; 
    } 
} 

したがって、2つのループ「追加」の2つの比較に加えて、単純に条件ジャンプとその効果がより明確になりますif文：内部コードの各実行）について。