このアルゴリズムの時間複雑度（Big-O）を測定するにはどうすればよいですか？

Question

私は次のアルゴリズムのビッグOの複雑さを測定しようとしています：

int sumSome(int[] arr){ 
    int sum = 0; 
    for (int i=0; i<arr.length; i++) { 
     for (int j=1; j<arr.length; j = j*2) { 
     if (arr[i] > arr[j]) 
      sum += arr[i]; 
     } 
    } 
    return sum; 
} 

今、私の理解から、それは定数と何なので

if (arr[i] > arr[j]) 
       sum += arr[i]; 

がOの大きなO（1）を持っていますしかし、私はBig-O表記法を見分けるのに苦労しているが、それを聞こえるforループは起こっている。私は

for (int j=1; j<arr.length; j = j*2) { 
     if (arr[i] > arr[j]) 
      sum += arr[i]; 
} 

は、一次関数Oであると仮定（n）のjは多分1理由はそれだけではO（n）であるO（2N）で直線状に上がっています。だからアルゴリズム全体がO（n^2）ではないでしょうか？明らかに私はMOOC試験で質問に正しく答えなかった。ありがとう！

Answer 1

あなたの重要な部分はここにあるように、ビッグ-Oは、ループを探しているの鍵：

for (int i=0; i<arr.length; i++) { 
    for (int j=1; j<arr.length; j = j*2) { 
     if (arr[i] > arr[j]) 
     sum += arr[i]; 
    } 
} 

それは1

刻みで0からNになるので、外側のループは、N回実行

内部ループは、1からN指数関数的に実行するため、外部反復ごとにログをN回実行します。あなたが見逃した部分は、ループ内のイテレータであると思われます：j = j*2これにより、Jは直線的ではなく指数関数的に増加しますので、log-base-2時間でNに達するでしょう。+2、 *2の代わりに）

Big-Oの場合、if内部は係数を追加するだけで、問題はありません。

それでは、ループの注文を掛ける：N * Log N = N Log N

Answer 2

は、jが多分1であるため、線形関数O（n）ですが、O（n）では線形になります。アルゴリズム全体がO（n^2）ではないでしょうか。明らかに私はMOOC試験で質問に正しく答えなかった。ありがとう！

あなたが各繰り返しで2でjを掛けるので、それは、指数関数的に直線的に上がって、しかし、ないです。

j = 1, 2, 4, 8, 16, 32, ..., 2^k < n 
2^k < n | apply log base 2 => k < log_2 n => k = O(log n) 

そこで第二のループは、コードO(n log n)の全配列を作る、O(log n)回だけ実行されます。

厳密に言えば、O(n^2)も正しい答えです。O(n log n)が上限である場合は、O(n^2)となります。しかし、ビッグ・セータはn^2では正しくないでしょうし、人々は通常ビッグ・オーを使ってタイト・バウンドを指しています。