O型符號爲J + =我

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時，內部循環變爲無限循環。

Answer 2

對於當i從0開始的情況下：

您的代碼O（∞），如通過ShadowRanger的answer說明。

對於情況下，我從1開始：

您可以簡單地使用你的實際複雜F（N）爲界觀察：

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)) 

爲了證明價值Harmonic number是O(log(N))，你可以使用簡單的微積分。請參閱here和here。