j個の+のためのO-記法= I

Question

私は次のコードビットのためのO-表記法を見つける必要があります。

for(i = 0; i < N; i++){ 
    for(j = 0; j < N; j+=i){ 
    x+=y; 
    } 
} 

私はO（N *ログ（N）にそれを取得することができました）しかし、私は確信したい。
この種の機能に名前を付けて調べることはできますか？

Answer 1

あなたのコードはO（∞）です。最初の外側ループでは、iは0で、jの増分が0であるため、内部ループはN > 0のとき無限ループになります。私は0から開始した場合については

Answer 2

：ShadowRangerのanswerで説明したように

あなたのコードでは、O（∞）です。ケースでは

iは1から開始したとき：その価値を証明するために

f(N) <= N/1 + N/2 + N/3 + ... + N/N 

    <= N * (Bound of value of Harmonic Number) 

    < c1 * N * (log (N)) i.e. O(N log(N)) 

：

あなたは単にあなたの実際の複雑F（N）はをによって制限され、観察を使用することができますHarmonic numberはO(log(N))です。単純な計算を使用できます。 hereとhereを参照してください。