苦しんで覚えるC言語

アルゴリズムの概要


アルゴリズムとは


アルゴリズムとは、ある問題を解くための手順、すなわち、公式のことです。
もう少し厳密には、明確で有限個の手順を有限回繰り返す計算方法のことです。
アルゴリズム
明確に定義された有限個の規則の集まりであって、
有限回適用することによって問題を解くもの。
(JIS(日本工業規格)より)
明確な手順とはその通りの意味です。
第0部でも説明したように、コンピュータは明確な命令を必要とします。
「冷蔵庫からキムチを取ってこい」というのは不明確な命令であり、
「18度回転、182センチ前進、36度回転、腕を90度上昇・・・」は明確な命令です。

有限個の手順とは、少々不思議な表現です。
手順が無限になることは一般には考えづらいので、あまり気にしなくても良いでしょう。

有限回繰り返す計算とは、すなわち、いつかは必ず計算が終わる、ということです。
いつまでも終わらない計算を延々と繰り返していたのではキリがありません。
無限に続く円周率の計算も、ある程度まで計算した段階で強制的に終了させてしまいます。

これらの条件は、コンピュータに計算させて問題を解く場合には必ず必要です。
普段、人間が問題を解く場合には、ある程度は経験やカンに頼っているのですが、
コンピュータにはそのような機能はないため、明確な手順は必ず必要になります。

なお、アルゴリズムは原則としてプログラミング言語に依存しません。
CでもJavaでもBASICでも、同じアルゴリズムを使うことができます。

目次に戻る

アルゴリズムの性能


コンピュータは純粋な理論の世界なので、現実世界と異なり、物理的な制約がありません。
そのため、同じ問題を解く場合でも、実に様々な方法を考えることができます。
しかし、当然、様々な方法の中にも優れた方法とそうでない方法があります。
コンピュータと宗教
実は、コンピュータ業界は宗教的なところがあります。
というのも、物理的な制約を無視し、実に様々な考え方ができるからです。
そのため、同じことをやるにしても人によって方法が全く異なり、
場合によっては、どの方法を信じるのか、というレベルの争いになるためです。
ここで、どこで優れた方法と判断するか、つまり、性能評価が問題になります。
アルゴリズムの性能を比べる基準としては、次の基準がよく使われます。

計算速度(早く終わるほど優秀)
メモリ使用量(少なく済むほど優秀)
計算の精度(正確に計算できるほど優秀)
プログラムの作りやすさ(簡単に作れるほど優秀)
この中でも最も注目すべき点は、なんといっても計算速度です。
というもの、そのほかの基準は、アルゴリズムによる差がさほど大きくないのですが、
計算速度だけは、アルゴリズムが違うと天と地ほどの差があるのです。

これを示すおもしろい例として、安定した結婚という問題があります。
この問題は、簡単に説明すると次のような問題です。
安定した結婚
独身男女各何人かが集団見合いをし、各相手に対する好感度を出しました。
彼らは、お互いが、自分の結婚相手より好感度が高いと浮気してしまいます。
彼らの全員が浮気する心配のない結婚の組み合わせを見つけてください。
具体的なプログラムコードまでは紹介しませんが、簡単に説明していきます。
最初に思いつくのは、全ての組み合わせについて浮気相手がいないか確かめる方法です。
この方法でも、もちろん答えを出すことができます。
しかし、お見合いする男女の人数が増えるほど時間がかかるようになり、
10人なら数秒ですが、14人では30分以上、15人を超えると一日以上、
20人になるともはや人類が生存している間は計算が終わりません。

なぜ、これほど時間がかかるかというと、全ての組み合わせを調べているためです。
男女の組み合わせの総数は、人数の階乗で求めることができます。
階乗
1x2x3x4x5x6x7x8x9x10..... という計算のこと。
数が多くなるとねずみ算以上に膨大な数になる。
また、浮気確認では、人数の2乗だけ浮気を確認しなくてはなりません。
そうなると、このアルゴリズムは「人数の階乗×人数の2乗」回の計算が必要です。
これを元に、人数と計算回数を表にしてみます。
人数計算回数
11
53000
10362880000
1268976230400
1417086945080000
15294226732800000
20973160803300000000000
人数が増えると、信じられないほど急激に計算回数が増えることがわかります。

では、これを高速化することを考えてみましょう。
そもそも、全ての組み合わせを調べる必要はありません。
まず、男性は第一希望の女性に求婚します。
このとき、女性に相手がいないか、いても好感度が低い場合は新しい男性と婚約します。
そして、フラれた男性は、先ほど求婚した女性よりも1ランク下の女性に求婚します。
つまり、男性はランクを落としながら、女性はランクを上げながら相手を決めていくのです。

このアルゴリズムでは、N人の男性がN人の女性に求婚するので、計算回数は人数の2乗です。
これを元に、人数と計算回数を表にしてみます。
人数計算回数
11
525
15225
20400
502500
10010000
先ほどと比べものにならないほど計算回数が減っています。
このアルゴリズムなら、100人という大規模のお見合いでも数秒で計算できます。
ファミコンでこのアルゴリズムを使った場合と、
プレステ2で前回のアルゴリズムを使った場合では、
ファミコンのほうが明らかに速く計算できるという程の差になっています。
超高性能ゲーム機・ファミコン
完全な余談になりますが、実は、ファミコンは超高性能なゲーム機でした。
ファミコン登場の少し前に、ゲームウォッチが流行したことを考えれば、
その性能の差がわかると思います。
解像度256x224(アドバンスより大)、16色で、音楽と効果音が同時に鳴らせます。
スプライト(キャラの重ね合わせ処理)もハードウェアで搭載しています。
ゲームが大きな産業でなかった時代にこれほどのハードを出せたのは奇跡です。
是非とも、プロジェクトXで特集してもらいたいものです。
このように、アルゴリズムによっては、計算速度が電卓とスパコンほどの差がでます。
このため、アルゴリズムの性能では計算速度が最重視されるのです。
他の基準について
メモリ使用量もアルゴリズムによって異なります。
高速なアルゴリズムでは2~3倍必要ですが、速度ほど差はありません。
計算の精度もアルゴリズムによって異なりますが、
ほとんどのアルゴリズムでは正確で、速度ほど差はありません。
意外に重要なのがプログラムの作りやすさです。
高度なアルゴリズムほど時間がかかりバグも増えやすいので、
無視できる程度の速度差しかなければ簡単な方が使われます。

目次に戻る

O(オー)記法


前項では、アルゴリズムの計算速度を比較するために、計算回数を比較しました。
コンピュータで実行して実際にかかった時間で比べた方が直感的なのに、
何故、わざわざ計算回数などで比較したのでしょうか。

これは、当然実行するコンピュータによって時間が変わるからです。
性能の高いコンピュータと低いコンピュータでは、当然高い方が速く計算できます。
常に同じコンピュータで比べるという方法もあるのですが、
日進月歩のコンピュータの世界では、同じ性能のコンピュータを使い続けられません。
それに、コンピュータとアルゴリズムの相性もあるため、不公平になります。

そこで、アルゴリズムの比較では、計算回数を元にして比較します。
ただし、一行ごと正確に計算される回数を求めてもそれほど意味がありません。
アルゴリズムの計算で、時間がかかるのは繰り返して処理している部分であり、
繰り返しを行っていない部分の時間は非常に短いため、無視できてしまいます。
つまり、繰り返し回数を比較すれば、アルゴリズムの計算時間はだいたいわかるのです。

しかし、前項のアルゴリズムのように、計算元のデータが増えると、
繰り返し回数が莫大に増加するようなアルゴリズムもあります。
従って、繰り返し回数自体を比較するよりも、
計算元のデータの増加に対して、繰り返し回数がどれだけ増加するかが重要になります。

このような理由から、アルゴリズムの計算速度にはO(オー)記法が使われます。
O(オー)記法
データ件数に対して繰り返し回数の増加を、漸近的に求めた値。
O記法では、n個のデータに対して繰り返し回数がnに比例するならO(n)と表します。
ただし、n個のデータに対して繰り返し回数が2nとなる場合でもO(n)と表します。
2乗などに比べ整数倍の影響はたかがしれているため、整数倍は無視します。
O記法では、データ件数が非常に大きい場合の増加の度合いを最重視するためです。

例えば、前項のアルゴリズムをO記法で表すと、前者はO(n!)、後者はO(N^2) です。
2乗の記号
コンピュータ文字では2乗を表しにくいので、^2 という記号を使います。
前者の計算回数は「人数の階乗×人数の2乗」回でしたが、
階乗に比べれば二乗はたいしたことがないので、2乗は無視してしまいます。

O記法で計算速度を求めると、主に次のような値になります。

1、log2n、n、nlog2n、n^2、2^n、n!
右のアルゴリズムほど、データ件数が増えると計算が爆発的に遅くなることを意味します。
o(1)のアルゴリズムの場合、データ件数がどんなに多くても同じ時間で計算できます。
o(n)のアルゴリズムの場合、計算時間はデータ件数に正比例します。
o(n~2)のアルゴリズムの場合、計算時間はデータ件数の2乗に正比例します。

O記法を使用すると、コンピュータで実行せずともアルゴリズムの性能がわかります。
しかも、データ件数が増えるとどれだけ計算が遅くなるのかがわかるため、
アルゴリズムの性能判断に非常に役に立ちます。
最悪の計算
ここまでは計算時間と書いてきましたが、正確には最大計算時間です。

同じアルゴリズムであっても、その計算時間はデータによって変わります。
例えば、全てを調べる遅いアルゴリズムで20人の結婚を計算した場合でも、
もしも解答が組み合わせのすぐ始めにあったとしたら、一瞬で答えがでます。
逆に、解答が組み合わせの最後の方にあるとしたら、何千年もかかります。

アルゴリズムでは、最大計算時間を重視しています。
最大計算時間が遅いと、計算が終わらない最悪の事態になりかねないためです。

なお、平均的な計算時間を数学的に求めることは困難です。

目次に戻る

データ構造


データ構造とは、一見アルゴリズムと関係がなさそうな言葉に聞こえます。
しかし、データ構造とアルゴリズムは切っても切れない関係にあります。
データ構造
情報の表現方法のこと。
データ構造とは、情報を記憶するときにどのような形を取るかを意味します。
実は、すでに説明済みのデータ構造があります。それは配列と構造体です。
配列は、同じ型の変数を複数並べることで、複数の情報を表現します。
構造体は、異なる型の変数をまとめて、関連性のある情報を表現します。
これらは単純なデータ構造ですが、いずれも普通の変数では表現が難しい情報です。

アルゴリズムでは、データを計算して答えを出さなければなりませんが、
この時に、どんな方法でデータを記憶するかは非常に重要です。
不自然な形でデータを記憶すると、その扱いに時間がかかってしまいます。
場合によっては、データ構造自体がアルゴリズムである場合すらあるのです。

目次に戻る