アルゴリズムとは、ある問題を解くための手順、すなわち、公式のことです。
もう少し厳密には、明確で有限個の手順を有限回繰り返す計算方法のことです。
明確な手順とはその通りの意味です。
［ アルゴリズム ］
明確に定義された有限個の規則の集まりであって、
有限回適用することによって問題を解くもの。
(JIS(日本工業規格)より)
有限個の手順とは、少々不思議な表現です。
手順が無限になることは一般には考えづらいので、あまり気にしなくても良いでしょう。
有限回繰り返す計算とは、すなわち、いつかは必ず計算が終わる、ということです。
いつまでも終わらない計算を延々と繰り返していたのではキリがありません。
無限に続く円周率の計算も、ある程度まで計算した段階で強制的に終了させてしまいます。
これらの条件は、コンピュータに計算させて問題を解く場合には必ず必要です。
普段、人間が問題を解く場合には、ある程度は経験やカンに頼っているのですが、
コンピュータにはそのような機能はないため、明確な手順は必ず必要になります。
なお、アルゴリズムは原則としてプログラミング言語に依存しません。
CでもJavaでもBASICでも、同じアルゴリズムを使うことができます。
コンピュータは純粋な理論の世界なので、現実世界と異なり、物理的な制約がありません。
そのため、同じ問題を解く場合でも、実に様々な方法を考えることができます。
しかし、当然、様々な方法の中にも優れた方法とそうでない方法があります。
ここで、どこで優れた方法と判断するか、つまり、性能評価が問題になります。
［ コンピュータと宗教 ］
実は、コンピュータ業界は宗教的なところがあります。
というのも、物理的な制約を無視し、実に様々な考え方ができるからです。
そのため、同じことをやるにしても人によって方法が全く異なり、
場合によっては、どの方法を信じるのか、というレベルの争いになるためです。
計算速度(早く終わるほど優秀)この中でも最も注目すべき点は、なんといっても計算速度です。
メモリ使用量(少なく済むほど優秀)
計算の精度(正確に計算できるほど優秀)
プログラムの作りやすさ(簡単に作れるほど優秀)
これを示すおもしろい例として、安定した結婚という問題があります。
この問題は、簡単に説明すると次のような問題です。
具体的なプログラムコードまでは紹介しませんが、簡単に説明していきます。
［ 安定した結婚 ］
独身男女各何人かが集団見合いをし、各相手に対する好感度を出しました。
彼らは、お互いが、自分の結婚相手より好感度が高いと浮気してしまいます。
彼らの全員が浮気する心配のない結婚の組み合わせを見つけてください。
なぜ、これほど時間がかかるかというと、全ての組み合わせを調べているためです。
男女の組み合わせの総数は、人数の階乗で求めることができます。
また、浮気確認では、人数の2乗だけ浮気を確認しなくてはなりません。
［ 階乗 ］
1x2x3x4x5x6x7x8x9x10..... という計算のこと。
数が多くなるとねずみ算以上に膨大な数になる。
| 人数 | 計算回数 |
|---|---|
| 1 | 1 |
| 5 | 3000 |
| 10 | 362880000 |
| 12 | 68976230400 |
| 14 | 17086945080000 |
| 15 | 294226732800000 |
| 20 | 973160803300000000000 |
では、これを高速化することを考えてみましょう。
そもそも、全ての組み合わせを調べる必要はありません。
まず、男性は第一希望の女性に求婚します。
このとき、女性に相手がいないか、いても好感度が低い場合は新しい男性と婚約します。
そして、フラれた男性は、先ほど求婚した女性よりも1ランク下の女性に求婚します。
つまり、男性はランクを落としながら、女性はランクを上げながら相手を決めていくのです。
このアルゴリズムでは、N人の男性がN人の女性に求婚するので、計算回数は人数の2乗です。
これを元に、人数と計算回数を表にしてみます。
| 人数 | 計算回数 |
|---|---|
| 1 | 1 |
| 5 | 25 |
| 15 | 225 |
| 20 | 400 |
| 50 | 2500 |
| 100 | 10000 |
このように、アルゴリズムによっては、計算速度が電卓とスパコンほどの差がでます。
［ 超高性能ゲーム機・ファミコン ］
完全な余談になりますが、実は、ファミコンは超高性能なゲーム機でした。
ファミコン登場の少し前に、ゲームウォッチが流行したことを考えれば、
その性能の差がわかると思います。
解像度256x224(アドバンスより大)、16色で、音楽と効果音が同時に鳴らせます。
スプライト(キャラの重ね合わせ処理)もハードウェアで搭載しています。
ゲームが大きな産業でなかった時代にこれほどのハードを出せたのは奇跡です。
是非とも、プロジェクトXで特集してもらいたいものです。
［ 他の基準について ］
メモリ使用量もアルゴリズムによって異なります。
高速なアルゴリズムでは2〜3倍必要ですが、速度ほど差はありません。
計算の精度もアルゴリズムによって異なりますが、
ほとんどのアルゴリズムでは正確で、速度ほど差はありません。
意外に重要なのがプログラムの作りやすさです。
高度なアルゴリズムほど時間がかかりバグも増えやすいので、
無視できる程度の速度差しかなければ簡単な方が使われます。
前項では、アルゴリズムの計算速度を比較するために、計算回数を比較しました。
コンピュータで実行して実際にかかった時間で比べた方が直感的なのに、
何故、わざわざ計算回数などで比較したのでしょうか。
これは、当然実行するコンピュータによって時間が変わるからです。
性能の高いコンピュータと低いコンピュータでは、当然高い方が速く計算できます。
常に同じコンピュータで比べるという方法もあるのですが、
日進月歩のコンピュータの世界では、同じ性能のコンピュータを使い続けられません。
それに、コンピュータとアルゴリズムの相性もあるため、不公平になります。
そこで、アルゴリズムの比較では、計算回数を元にして比較します。
ただし、一行ごと正確に計算される回数を求めてもそれほど意味がありません。
アルゴリズムの計算で、時間がかかるのは繰り返して処理している部分であり、
繰り返しを行っていない部分の時間は非常に短いため、無視できてしまいます。
つまり、繰り返し回数を比較すれば、アルゴリズムの計算時間はだいたいわかるのです。
しかし、前項のアルゴリズムのように、計算元のデータが増えると、
繰り返し回数が莫大に増加するようなアルゴリズムもあります。
従って、繰り返し回数自体を比較するよりも、
計算元のデータの増加に対して、繰り返し回数がどれだけ増加するかが重要になります。
このような理由から、アルゴリズムの計算速度にはO(オー)記法が使われます。
O記法では、n個のデータに対して繰り返し回数がnに比例するならO(n)と表します。
［ O(オー)記法 ］
データ件数に対して繰り返し回数の増加を、漸近的に求めた値。
例えば、前項のアルゴリズムをO記法で表すと、前者はO(n!)、後者はO(N^2) です。
前者の計算回数は「人数の階乗×人数の2乗」回でしたが、
［ 2乗の記号 ］
コンピュータ文字では2乗を表しにくいので、^2 という記号を使います。
O記法で計算速度を求めると、主に次のような値になります。
1、log2n、n、nlog2n、n^2、2^n、n!右のアルゴリズムほど、データ件数が増えると計算が爆発的に遅くなることを意味します。
O記法を使用すると、コンピュータで実行せずともアルゴリズムの性能がわかります。
しかも、データ件数が増えるとどれだけ計算が遅くなるのかがわかるため、
アルゴリズムの性能判断に非常に役に立ちます。
［ 最悪の計算 ］
ここまでは計算時間と書いてきましたが、正確には最大計算時間です。
同じアルゴリズムであっても、その計算時間はデータによって変わります。
例えば、全てを調べる遅いアルゴリズムで２０人の結婚を計算した場合でも、
もしも解答が組み合わせのすぐ始めにあったとしたら、一瞬で答えがでます。
逆に、解答が組み合わせの最後の方にあるとしたら、何千年もかかります。
アルゴリズムでは、最大計算時間を重視しています。
最大計算時間が遅いと、計算が終わらない最悪の事態になりかねないためです。
なお、平均的な計算時間を数学的に求めることは困難です。
データ構造とは、一見アルゴリズムと関係がなさそうな言葉に聞こえます。
しかし、データ構造とアルゴリズムは切っても切れない関係にあります。
データ構造とは、情報を記憶するときにどのような形を取るかを意味します。
［ データ構造 ］
情報の表現方法のこと。
アルゴリズムでは、データを計算して答えを出さなければなりませんが、
この時に、どんな方法でデータを記憶するかは非常に重要です。
不自然な形でデータを記憶すると、その扱いに時間がかかってしまいます。
場合によっては、データ構造自体がアルゴリズムである場合すらあるのです。
