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

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

アルゴリズムの効率とは

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

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

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

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

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

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

Ｏ表記法