Big O、どうやって計算/概算するのですか? 質問する

Question

ここではできるだけ簡単に説明しようと努力しますが、このトピックを理解するには生徒が2、3か月かかることをご了承ください。詳細については、第2章をご覧ください。Java のデータ構造とアルゴリズム本。

ありません機械的手順BigOh を取得するために使用できます。

「料理本」として、ビッグオーコードから、まず、あるサイズの入力に対して実行される計算ステップの数をカウントする数式を作成していることを認識する必要があります。

目的は単純です。コードを実行する必要なく、理論的な観点からアルゴリズムを比較することです。ステップ数が少ないほど、アルゴリズムは高速になります。

たとえば、次のようなコードがあるとします。

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

この関数は配列のすべての要素の合計を返します。計算の複雑さその関数の:

Number_Of_Steps = f(N)

そこでf(N)、計算ステップの数をカウントする関数が存在します。関数の入力は、処理する構造体のサイズです。つまり、この関数は次のように呼び出されます。

Number_Of_Steps = f(data.length)

パラメータは値Nを受け取りますdata.length。次に、関数の実際の定義が必要ですf()。これはソースコードから実行され、各行には 1 から 4 までの番号が付けられます。

CBigOh を計算する方法は多数あります。ここからは、入力データのサイズに依存しないすべての文が定数の計算ステップを実行するものと仮定します。

関数の個々のステップ数を追加します。ローカル変数の宣言も return ステートメントも配列のサイズに依存しませんdata。

つまり、1 行目と 4 行目はそれぞれ C 個のステップを実行し、関数は次のようになります。

f(N) = C + ??? + C

次の部分は、forステートメントの値を定義することです。計算ステップの数を数えていること、つまりステートメントの本体が回for実行されることを覚えておいてください。これは、を回N追加することと同じです。CN

f(N) = C + (C + C + ... + C) + C = C + N * C + C

文の本体が何回実行されるかを数える機械的なルールはありませんfor。コードが何を行うかを見て数える必要があります。計算を簡略化するために、文の変数の初期化、条件、増分部分は無視しますfor。

実際のBigOhを取得するには、漸近解析関数の。これは大まかに次のように行われます。

すべての定数を取り除きますC。
f()取得から多項式そのstandard form。
多項式の項を分割し、成長率で並べ替えます。
N近づくと大きくなる方をキープしますinfinity。

当社にはf()2 つの用語があります:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Cすべての定数と冗長な部分を取り除きます。

f(N) = 1 + N ^ 1

最後の項は無限大に近づくにつれて大きくなる項なのでf()（限界) これは BigOh 引数であり、sum()関数の BigOh は次のようになります。

O(N)

いくつかの難しい問題を解決するには、いくつかのコツがあります。合計あなたができる時はいつでも。

たとえば、次のコードは合計を使用して簡単に解くことができます。

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

最初に尋ねられる必要があるのは、の実行順序ですfoo()。通常はですがO(1)、これについては教授に尋ねる必要があります。は、サイズに関係なく、O(1)（ほぼ、大抵）一定を意味します。CN

for文番号 1 のステートメントはトリッキーです。インデックスはで終わりますが、2 * N増分は 2 ずつ行われます。つまり、最初のはステップforだけ実行されN、カウントを 2 で割る必要があります。

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

2番目の文は、の値に依存するため、さらに複雑ですi。見てみましょう。インデックス i は、0、2、4、6、8、...、2 * N の値を取り、2 番目は、for最初の N 倍、2 番目は N - 2 倍、3 番目は N - 4 倍、というように実行されます。N / 2 段階まで実行され、2 番目はfor実行されません。

公式では、それは次のことを意味します:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

ここでも、ステップ数を数えています。定義により、すべての合計は常に 1 から始まり、1 より大きい数で終わります。

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

foo()（そうであると仮定しO(1)、C手順を実行します。）

ここで問題があります。がi値を上向きに取ると、内部の合計は負の数で終わります。これは不可能であり、間違っています。の合計をの瞬間が取るN / 2 + 1中心点として 2 つに分割する必要があります。iN / 2 + 1

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

重要な瞬間以降i > N / 2、内部はfor実行されず、その本体には一定の C 実行複雑度があると想定されます。

ここで、いくつかの恒等規則を使用して合計を簡略化できます。

合計(w 1からNまで)( C ) = N * C
合計(w 1 から N まで)( A (+/-) B ) = 合計(w 1 から N まで)( A ) (+/-) 合計(w 1 から N まで)( B )
合計(w 1からNまで)( w * C ) = C * 合計(w 1からNまで)( w ) (Cは定数で、に依存しませんw)
合計(w 1からNまで)( w ) = (N * (N + 1)) / 2

代数を適用します:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

そして、BigOh とは:

O(N²)

Answer 1