optimization - algorithm - ビッグ・オー、どうやって計算/近似するの?

algorithm / complexity-theory / big-o / performance

CS の学位を取得したほとんどの人は、Big O が何を表しているかを確かに知っています。これは、アルゴリズムがどの程度適切にスケーリングするかを測定するのに役立ちます。

Robert Harvey



Answer #1

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

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)
Number_Of_Steps = f(data.length)

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

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

例として、このコードは和を使って簡単に解くことができます。

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

式の上では、ということは

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 ) )
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 )

代数を適用する。

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²)