苦しんで覚えるＣ言語

苦しんで覚えるＣ言語

アルゴリズムとは、ある問題を解くための手順、すなわち、公式のことです。
もう少し厳密には、明確で有限個の手順を有限回繰り返す計算方法のことです。


明確な手順とはその通りの意味です。
第0部でも説明したように、コンピュータは明確な命令を必要とします。
「冷蔵庫からキムチを取ってきて」は不明確な命令であり、
「18度回転、182センチ前進、36度回転、腕を90度上昇・・・」は明確な命令です。

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

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

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

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

コンピュータは純粋な理論の世界なので、現実世界と異なり、物理的な制約がありません。
そのため、同じ問題を解く場合でも、実にさまざまな方法を考えることができます。
しかし、当然、さまざまな方法の中にも優れた方法とそうでない方法があります。


ここで、どこで優れた方法と判断するか、つまり、性能評価が問題になります。
アルゴリズムの性能を比べる基準としては、次の基準がよく使われます。


この中でももっとも注目すべき点は、なんといっても計算量です。
というもの、そのほかの基準は、アルゴリズムによる差がさほど大きくないのですが、
計算量だけは、アルゴリズムが違うと天と地ほどの差があるのです。

これを示すおもしろい例として、安定した結婚という問題があります。
この問題は、簡単に説明すると次のような問題です。


この問題を、コンピュータで解く方法について、考えてみましょう。

最初に思いつくのは、すべての組み合わせについて浮気相手がいないか確かめる方法です。
この方法でも、もちろん答えを出すことができます。
しかし、お見合いする男女の人数が増えるほど時間がかかるようになり、
10人なら数秒ですが、14人では30分以上、15人を超えると一日以上、
20人になるともはや人類が生存している間は計算が終わりません。

なぜ、これほど時間がかかるかというと、すべての組み合わせを調べているためです。
男女の組み合わせの総数は、人数の階乗で求めることができます。


また、浮気確認では、人数の2乗だけ浮気を確認しなくてはなりません。
そうなると、このアルゴリズムは「人数の階乗×人数の2乗」回の計算が必要です。
これを元に、人数と計算回数を表にしてみます。

人数	計算回数
1	1
5	3000
10	362880000
12	68976230400
14	17086945080000
15	294226732800000
20	973160803300000000000

人数が増えると、信じられないほど極端に計算回数が増えることがわかります。

何百万年も計算が終わらないのでは困ります。
計算量を減らすことで、もっと早く計算が終わるようにすることはできないのでしょうか？

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

このアルゴリズムでは、N人の男性がN人の女性に求婚するので、計算回数は人数の2乗です。
これを元に、人数と計算回数を表にしてみます。

人数	計算回数
1	1
5	25
15	225
25	400
50	2500
100	10000

先ほどと比べものにならないほど計算回数が減っていますね。
このアルゴリズムなら、100人という大規模のお見合いでも数秒で計算できます。

このように、アルゴリズムが異なると、数秒で終わるのか、数百万年かかっても終わらないのか。というのほどの差がでます。
このため、アルゴリズムの性能では計算量が最重視されるのです。

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

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

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

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

このような理由から、アルゴリズムの計算量にはO(オー)記法が使われます。


O記法では、n個のデータに対して繰り返し回数がnに比例するならO(n)と表します。
ただし、n個のデータに対して繰り返し回数が2nとなる場合でもO(n)と表します。
2乗などに比べ整数倍の影響はたかがしれているため、整数倍は無視します。
O記法では、データ件数が非常に大きい場合の増加の度合いを最重視するためです。

たとえば、前項のアルゴリズムをO記法で表すと、前者はO(n!)、後者はO(N^2) です。


前者の計算回数は「人数の階乗×人数の2乗」回でしたが、
階乗に比べれば二乗はたいしたことがないので、2乗は無視してしまいます。

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



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

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

データ構造とは、一見アルゴリズムと関係がなさそうな言葉に聞こえます。
しかし、データ構造とアルゴリズムは切っても切れない関係にあります。


データ構造とは、情報を記憶するときにどのような形を取るかを意味します。
実は、すでに説明済みのデータ構造があります。それは配列と構造体です。
配列は、同じ型の変数を複数並べることで、複数の情報を表現します。
構造体は、異なる型の変数をまとめて、関連性のある情報を表現します。
これらは単純なデータ構造ですが、いずれも普通の変数では表現が難しい情報です。

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