Time Complexity：Whileループforループ[Java]

Question

私はちょうど時間の複雑さを学び始めましたが、私は幾分 "okayish"把握していますが、このコードセグメントについてどうやって行くのか少し混乱します。 私は他の記事を読んだことがありますが、誰かが私の言うことを断ることがなければ、苦労することがあります。顔の叩き声のようなもの。

public int example(int[] array) { 

    int result = 15; 
    int i = array.length; 

    while(i > 1) 
    { 
     for(int x = 0; x < array.length;x++) 
     { 
     result+= 1; 
     result+=2*array[x]; 
     } 
     i = i/2; 
    } 
return result; 
} 

私は算術演算を数えています。私は（おそらく）午前間違っている場合、私は信じているから は、

X ++

がn回発生した、私を修正します。

結果+ = 1はn回発生します。 4N回

との合計

結果+ = 3 *アレイ[X]を2N回起こる

全てのi = I/2がLOGN回

起こります

正しい方程式は4nlognでしょうか？

Answer 1

あなたは4n*log(n)で正しいトラックにいます。しかし、大きなO時間の複雑さに対して、定数は削除されるので、これはO(n*log(n))になることに注意してください。

定数があるため、大きなO定義の削除されます。f(x)はO(g(x))すべてのためのf(z) <= c*g(z)場合z>いくつかの数です。ここでのキーは、任意の定数にすることができるcです。 f(x)が100xの場合でも、まだc=200となり、g(x)の方が依然として大きくなる可能性があります。

補足として、定数を除外することができるので、大きなO時間の複雑さを計算するときには、すべての演算をカウントする必要はありません。あなたはループだけを見る必要があります。 1つはn回、もう1つはlog(n)回起こります。したがって、それはO(n*log(n))です。コードは各ループ内で1000回の演算を実行するか、または2回実行することができます。定数は大きなOの式から因数分解されるため、その数は関係ありません。ループの数と性質のみが行います。