時間複雑にネスト・ループ

Question

問題：私は大きなシータを持っ

s <-- 0; 
i = 2; 
while (i <= n^2) do 
    for j <-- i to 2i[ln(i)] do 
     s <-- s + i - j; 
    end 
    i <-- i + 2; 
end 
return (s); 

（N^2（LN（n））をforループから：

は、この機能の複雑さ（ビッグシータ）を検索は2i [ln（i）] - i回実行され、それはci [ln（i）]時間になります。そして、それはwhileループのおおよその時刻なのでn^2で乗算されます。

解決済みそれは別の方法と大きなシータ（n^4）を持っています。

私の答えが正しいかどうかは確かではありません。ループが依存している場合と独立している場合に、これらの問題を解決する方法についての私の混乱に基づいています。

Answer 1

最も堅牢な解決策は2 <= i <= n^2/2の場合は2*(2i)*ln(i) - 2i + 1の合計です。我々は持っている：一方

1 + 2 + ... + floor(n^2/2) = O(n^4) 

：（定数4を考慮する必要はありません）

1*ln(1) + ... + floor(n^2/2)*ln(floor(n^2/2)) = O(n^4*ln(n)) 

を

を実際には、あなたもに漸近的に等価な式を得ることができますあなたの合計はcomparison with an integralです。

したがって、時間の複雑さはO(n^4*ln(n))-O(n^4)+O(n) = O(n^4*ln(n))です。

MathJaxを書く計算がなければ、痛みは、here is a more detailed proofです。