Ｏ表記法

Ｏ表記法は、Big-Oh-Notation とも呼ばれ、O(g(n)) のように n を入力のサイズとした関数の集合で表します。O(g(n))　は計算量が g(n) の定数倍で抑えられることを意味します。つまり、この表記は問題の各入力サイズに対して、そのサイズの任意のインスタンスを解くために必要な"最大"の演算回数を見積もります。ここで、インスタンスとは問題の全ての入力値に具体的な値を設定したものを言います。問題が与えられるときには必ず入力の上限が定義されます。いくつか例を挙げます。

問題と解法の例	効率の例	意味
与えられたx個のデータを、Ａというアルゴリズムで整列する。xの最大値はnとする。	この問題に対するAの効率はO(n2)である。	Aは最悪でn2の計算ステップが必要である。
x個の交差点とy個の道から成る地図情報を基に、交差点aから交差点bまでの最短距離をBというアルゴリズムで求める。ｘの最大値はn、ｙの最大値は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)のアルゴリズムは効率が良いと言えます。ｎが増加しても計算量はさほど増加しません。逆に、オーダーがO(2ⁿ)やO(n!)のアルゴリズムは、入力nが数十になっただけで、計算量が何千桁にも至ってしまいます。地球上最速のコンピュータを使っても、数百年かかってしまうであろう計算量です。これらの効率の悪いオーダーは、総当りなどの、素朴で力任せのアルゴリズムに良く見られます。そして初心者のプログラマがよくはまってしまいます。しかしながら、世の中には未解決の問題も多々あり、それらを解くことのできる最速のアルゴリズムのオーダーがO(2ⁿ)である場合もあります。 重要なことは、プログラムを実装する前に、入力の上限から自分のアルゴリズムの最悪計算ステップを評価することです。これは、学習するよりも、難しい問題にチャレンジし、失敗を繰り返すことによって経験することができます。

アルゴリズムを実装する前に、

現在のコンピュータは膨大な計算を一瞬でこなすことができますが、すべての問題を高速に解決できるわけではありません。もちろん限界があります。膨大な量のデータを高速に計算する優れたプログラムを書くためには、問題の性質を十分に考慮し効率の良いアルゴリズムを考える必要があります。

アルゴリズムの効率とは

与えられた問題を解くためのアルゴリズムを考えるとき、そのアルゴリズムの効率を評価する「ものさし」が必要になります。アルゴリズムを考えてプログラムを実装するときには、まずその効率を測り、そのアルゴリズムの効率が与えられた問題を解くのに十分かどうかを確認する必要があります。この過程を無視すると、実装されたプログラムは使い物にならなかった、という失敗をしてしまいます。

効率の良いアルゴリズムに求められるものは、処理するデータの数が増加しても計算ステップ数が爆発的に（指数的に）増加しないという性質です。つまり、入力値によっては計算ステップ数が爆発的に増加し、事実上処理がストップしてしまうようなプログラムは使い物になりません。例えば、あるアルゴリズムがデータを100個処理するのに1秒しかかからなくても、データを10000個に増やすと数時間もかかる場合があります。アルゴリズムを実装したときに100個の入力データでテストし満足する結果が得られたとしても、実際にそのプログラムを使う人は10000個のデータを処理する必要があるかもしれません。コンピュータの処理能力は日々進歩していますが、処理するデータの量や処理の複雑さも日々増しています。コンピュータの計算能力が余っていれば使ってしまいたくなるのが人情です。ですから、後々まで通用する効率の良いアルゴリズムを追求しなければなりません。

アルゴリズム主に以下の２つの計算量で評価されます。

時間計算量（time complexity）
プログラムの実行に必要な時間を評価します。

領域計算量（space complexity）
プログラムの実行に必要な記憶領域で評価します。

時間計算量がよく用いられますが、どちらの評価が重要ということはなく、これらのバランスを考えてアルゴリズムを考えることが重要です。この効率の概念を無視してしまったら、これから学ぶアルゴリズムの意義も半減してしまいます。

Ｏ表記法

アルゴリズムとは

アルゴリズムとは「算法」「演算手順」などと直訳することができますが、広い意味では、「あることを達成するための手順」のことです。日常生活の例をとっても、朝起きて→着替えて→朝食を食べて→歯を磨いて→自転車で学校へ行く、という一連の行動も一種のアルゴリズムと考えることができます。一般的にコンピュータの世界ではデータ処理、数値演算、シミュレーションなどの問題を解決するための考え方や手法の事をアルゴリズムと言います。

さらに厳密に言えば、アルゴリズムとは「明確に定義された有限個の規則の集まりであって、有限回適用することにより"問題"を解くもの」です。世の中に存在する問題に応じて、アルゴリズムは無限に存在します。

問題とアルゴリズムの例：

アルゴリズムとは何かを具体的な問題の例を通して考えてみます。

問題：１０人分の生徒の名前と身長が記録されたデータを読み込んで、その中で身長が高い順に３人の名前を出力して下さい。類題

このような単純で中途半端な問題にも以下のようにいくつか解法が考えられます。

アルゴリズム１

1. １０人の中から身長が一番高い人を探して名前を出力する。
2. １０人の中から（１）ですでに選ばれた人以外から身長が一番高い人を探して名前を出力する。
3. １０人の中から（１）（２）ですでに選ばれた人以外から身長が一番高い人を探して名前を出力する。

アルゴリズム２

1. データを身長が高い順に整列する
2. データの最初の３人の名前を順番に出力する。

もちろんこれらはプログラムとして実装できるアルゴリズムです。この例では、データを整列する計算効率を考えればアルゴリズム１の方が優れているます。一方もしデータを整列するためのアルゴリズムを簡単に書けるまたは信頼できるプログラムが使えるのであれば、アルゴリズム２の方がプログラムが分かり易く簡潔になりかつエラーを出さずに実装できるかもしれません。

このように、与えられた問題には様々な解法が存在します。その解法がアルゴリズムであって問題の定義や性質、さらにプログラムで使うデータ構造などに応じて考えなければなりません。以下の一般化した問題は、どのようなアルゴリズムで解けるかを考えてみると良いかもしれません。

n 個の整数が与えられ、その中で値が大きい順にm 個出力して下さい。ただしn < 1000000、m < 1000 とします。