時間複雑ループ

Question

ながら、入れ子になった私がこの文で、whileループのための時間の複雑さを決定する方法に困惑しています：

procedure P (integer n); 
for (i: 1 to n) 
    x := n; 
    while (x > 0) 
     x := x - i; 

私はループの実行（N-1）のための倍ことを知っています。最初は、whileループがn回実行されると考えました。なぜなら、私はiを1と間違えたからですが、そうではありません。私は数字を入力してプログラムがいつ停止するかを確認していますが、一貫したパターンは見られません。私は、nが増えるにつれて、whileループがより長く実行されることに気付きましたが（それほど多くはありません）、これは幾分対数的になりますか？前もって感謝します。

Answer 1

第ランサイクル

ながらN/3つつサイクル
k番目のランは、N/Kを行うことができるN/2ながらサイクル
第二ランする間、サイクル
最初の実行は、nを行います

したがって全体的な時間は、我々はharmonic seriesの部分和を見ることができるカッコ内

n * (1/1 + 1/2 + 1/3 +...+1/n) 

に比例し、それは、nの自然対数する傾向があり、複雑さはO（N Nログ）

であります