O表記法
2006.03.03 22:44 アルゴリズムの効率
O表記法は、Big-Oh-Notation とも呼ばれ、O(g(n)) のように n を入力のサイズとした関数の集合で表します。O(g(n)) は計算量が g(n) の定数倍で抑えられることを意味します。つまり、この表記は問題の各入力サイズに対して、そのサイズの任意のインスタンスを解くために必要な"最大"の演算回数を見積もります。ここで、インスタンスとは問題の全ての入力値に具体的な値を設定したものを言います。問題が与えられるときには必ず入力の上限が定義されます。いくつか例を挙げます。
このように、O( )の引数はある関数となります。また、O( n )を「オーダーがnである」と言います。では、アルゴリズムの評価に関する典型的な関数について、実際の入力値nとその計算量を以下の表で見てみましょう。ここでlogは2を底とする対数関数です。
どの関数がどれだけ効率が良いか、または悪いかを考えてみましょう。オーダーがO(logn)、O(n)、O(nlogn)のアルゴリズムは効率が良いと言えます。nが増加しても計算量はさほど増加しません。逆に、オーダーがO(2n)やO(n!)のアルゴリズムは、入力nが数十になっただけで、計算量が何千桁にも至ってしまいます。地球上最速のコンピュータを使っても、数百年かかってしまうであろう計算量です。これらの効率の悪いオーダーは、総当りなどの、素朴で力任せのアルゴリズムに良く見られます。そして初心者のプログラマがよくはまってしまいます。しかしながら、世の中には未解決の問題も多々あり、それらを解くことのできる最速のアルゴリズムのオーダーがO(2n)である場合もあります。 重要なことは、プログラムを実装する前に、入力の上限から自分のアルゴリズムの最悪計算ステップを評価することです。これは、学習するよりも、難しい問題にチャレンジし、失敗を繰り返すことによって経験することができます。
問題と解法の例 | 効率の例 | 意味 |
---|---|---|
与えられたx個のデータを、Aというアルゴリズムで整列する。xの最大値はnとする。 | この問題に対するAの効率はO(n2)である。 | Aは最悪でn2の計算ステップが必要である。 |
x個の交差点とy個の道から成る地図情報を基に、交差点aから交差点bまでの最短距離をBというアルゴリズムで求める。xの最大値はn、yの最大値はmである。 | この問題に対するBの効率はO(mlogn)である。 | Bは最悪で mlognの計算ステップが必要である。 |
このように、O( )の引数はある関数となります。また、O( n )を「オーダーがnである」と言います。では、アルゴリズムの評価に関する典型的な関数について、実際の入力値nとその計算量を以下の表で見てみましょう。ここでlogは2を底とする対数関数です。
n | logn | n | nlogn | n2 | 2n | n! |
---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 2 | 1 |
5 | 2 | 5 | 10 | 25 | 32 | 120 |
10 | 3 | 10 | 30 | 100 | 1024 | 3628800 |
20 | 4 | 20 | 80 | 400 | 1048576 | |
50 | 5 | 50 | 250 | 2500 | ||
100 | 6 | 100 | 600 | 10000 | ||
1000 | 9 | 1000 | 9000 | 1000000 | ||
10000 | 13 | 10000 | 130000 | 100000000 | ||
100000 | 16 | 100000 | 1600000 | |||
1000000 | 19 | 1000000 | 19000000 |
どの関数がどれだけ効率が良いか、または悪いかを考えてみましょう。オーダーがO(logn)、O(n)、O(nlogn)のアルゴリズムは効率が良いと言えます。nが増加しても計算量はさほど増加しません。逆に、オーダーがO(2n)やO(n!)のアルゴリズムは、入力nが数十になっただけで、計算量が何千桁にも至ってしまいます。地球上最速のコンピュータを使っても、数百年かかってしまうであろう計算量です。これらの効率の悪いオーダーは、総当りなどの、素朴で力任せのアルゴリズムに良く見られます。そして初心者のプログラマがよくはまってしまいます。しかしながら、世の中には未解決の問題も多々あり、それらを解くことのできる最速のアルゴリズムのオーダーがO(2n)である場合もあります。 重要なことは、プログラムを実装する前に、入力の上限から自分のアルゴリズムの最悪計算ステップを評価することです。これは、学習するよりも、難しい問題にチャレンジし、失敗を繰り返すことによって経験することができます。
スポンサーサイト
| コメント(3) | トラックバック(0) | ↑ページトップ |