[解決済み] ビッグ・オー、どうやって計算・概算するんだ？

質問内容

CSの学位を持っている人なら必ず知っていることです。 ビッグ・オーとは . これは、アルゴリズムがどれだけうまくスケールするかを測るのに役立ちます。

しかし、気になるのは、どのように あなた アルゴリズムの複雑さを計算したり、概算したりするのですか？

どのように解決するのですか？

しかし、私の生徒たちは、このテーマを理解するのに数カ月かかるので、注意してください。より詳しい情報は、「Skype」の第2章にあります。 Javaによるデータ構造とアルゴリズム という本があります。

はありません。 メカニカルプロシジャ BigOhを得るために使用することができます。

クックブックとしては 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までの番号が付けられています。

BigOhの計算方法はたくさんあります。ここからは、入力データのサイズに依存しない文はすべて定数をとるものとします。 C の計算ステップ数。

関数の個々のステップ数を加算していくのですが、ローカル変数の宣言もリターンステートメントも、そのサイズに依存することなく data の配列になります。

つまり、1行目と4行目はそれぞれCの量のステップをとり、なんとなくこんな感じの関数になります。

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

次のパートは、その値を定義するものです。 for ステートメントを使用します。計算ステップ数をカウントしていることを忘れないでください。 for 文が実行される N 回です。これは、以下を追加したのと同じです。 C , N 回です。

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

の本文の回数を数えるような機械的なルールはありません。 for そのコードが何を行っているかを見て数える必要があります。計算を簡単にするために、変数の初期化、条件、インクリメントの部分は無視しています。 for ステートメントを使用します。

実際のBigOhを取得するためには 漸近的解析 という関数があります。これは大体こんな感じで行われます。

1. すべての定数を削除する C .
2. から f() を取得します。 ポリノミ その中の standard form .
3. 多項式を分割し、成長率で並べ替える。
4. のとき、大きくなるものを残す。 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) は、（ほぼ、ほとんど）一定という意味です。 C サイズに関係なく N .

は for の文は厄介です。インデックスが 2 * N で、増分は2ずつです。つまり、最初の for のみが実行されます。 N のステップで、そのカウントを2で割る必要があります。

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

文番号 二 の値に依存するので、さらにやっかいです。 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 を上回ると、内側のSummationが負の数で終わってしまうのです! これはありえないし、間違っている。和算を2つに分割する必要があります。 i 取る N / 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実行の複雑さを仮定しています。

ここで、いくつかの恒等式を用いて和を簡略化することができる。

1. Summation(w from 1 to N)( C ) = N * C
2. Summation(w from 1 to N)( A (+/-) B ) = Summation(w from 1 to N)( A )（+/-） Summation(w from 1 to N)( B )（+/-） Summation(w from 1 to N)( B )（+/-） Summation(w from 1 to N)( B )
3. Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (Cは定数で、以下の要素とは無関係) w )
4. Summation(w from 1 to 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²)