最近、アルゴリズムの勉強を本格的に始めました。以前から、優秀なエンジニアになるにはアルゴリズムの理解は必須だと何度も言われていたのですが、どうしてもやる気がでませんでした。というのも、最近のコンピューターの性能はどんどん進化しており、最適なアルゴリズムを追求していくことに対してあまり意味が感じられなかったからです。力技でどうにかなるんじゃないかと思っていました。
しかし、具体的に勉強を初めて、「なんて愚かな考えだったんだろう。。。」と感じさせる例があったので、紹介したいと思います。
この “Introduction to Algorithms”という本によると、アルゴリズムはテクノロジーです。最新のハイスペックなハードウェア（テクノロジー）を選ぶようにアルゴリズムも選択していかなければいけません。
Insertion Sort と Merge Sort を例に取ると、
Insertion Sort の場合、n 個の要素をソートするのに約 c1 * n^2 かかります。 それに対して、 Merge Sort の場合は、c2 * n lg n です。 c は要素数に依存しない定数です。
こういう例は今まで勉強していて何度も聞いていたのですが、しっかりきていませんでした。もっと具体的に考えると、
Insertion Sort を使い、 優秀なプログラマー が実装します。その結果、処理を完了するのに 2 * n^2 必要なプログラムができたとします。そして、このプログラムを 10 million 個の要素をそうとソートします。このプログラマーは、10 billion instructions / per second の能力のある ハイスペック なコンピューターをしようすると、
[ 2 * ( 10^7 )^2 instructions ] / [ 10^10 instructions / per second ] = 20000 seconds = 5.5 hours
そして Merge Sort を使い、 凡庸なプログラマー がコードを書いた結果、50 * n lg n instructions かかるプログラムを作成したとします。そしてこの 凡庸なプログラマー が、 優秀なプログラマー よりも処理能力が ロースペック なコンピューターをします。10 million instructions / per second とします。その結果、
[ 50 * 10^7 lg 10^7 instructions ] / [ 10^7 instructions / per second ] = 1163 seconds = 20 hours
たとえ、 優秀なプログラマー が、 処理能力の高いコンピューター を使おうとも、最適なアルゴリズムを選択しなければ、 凡庸なプログラマー が ポンコツのコンピューター を使った場合でも負けてしまうのです。
そのことからアルゴリズムはハードウェア等と同じテクノロジーの一種であり、しっかり勉強しなければならないという教訓でした。
