ビッグああ分析

Question

コード1：外側のループがn^2回とループの実行をn回の内側を走るので、

I私の意見このコードはO（N^3）です。私の専門家によると、このコードはO（n^3）ではありません。誰かが理由を説明できますか？私は本当に混乱しています。

i, j, sum = 1, 1, 0 

while i < n**3: 
    while j < n: 
    sum = sum + i 
    j += 1 
    i = i + n 

コード2：

私は、このコードはO（n）のだと思います。誰かが確認してもらえますか？

i, j, sum = 0, 0, 0 

while i ** 2 < n: 
    while j ** 2 < n: 
    sum += i*j 
    j += 2 
    i += 4 

Answer 1

i, j, sum = 1, 1, 0 

while i < n**3: 
    while j < n: 
    sum = sum + i 
    j += 1 
    i = i + n 

jがforループのように再初期化されていないため、内側ループは、外側ループの最初のパスの間のみ実行されることに注意してください。内部ループの実行時間は正確にnであることは明らかです。一方、外側ループはn^2回実行されます。どうして？ iがどのように変更されているかを見てください：最初に1、次にn+1、次に2n+1、...、そして最後にn^2*n+1ですので、iはn^2回増分します。したがって、合計実行時間はn + n^2であり、これはO(n^2)です。

i, j, sum = 0, 0, 0 

while i ** 2 < n: 
    while j ** 2 < n: 
    sum += i*j 
    j += 2 
    i += 4 

条件while i ** 2 < nがwhile i < sqrt(n)と同等であることを付記有する第一の場合と同様の解析。内側ループは外側ループの最初のパスの間だけ実行され、実行時間はsqrt(n)/2であるため、jは2でインクリメントされます（1ではないため）。外部ループはsqrt(n)/4回実行されるので、合計実行時間はsqrt(n)/2 + sqrt(n)/4であり、これはO(sqrt(n))です。