「6さいからのプログラミング」第11話は、目的を達成するにはどのような処理をさせればよいかという「アルゴリズム」について解説します。「アルゴリズム」とは、ある目的を達成するための手順のことです。英和辞典を渡されて「『Egg』を探せ」と言われたときに、1ページ目から順に開いていけばいつかは『Egg』の項目にたどり着きます。この場合、「1ページ目から順に開く」という手順が「『Egg』を探す」ことの1つのアルゴリズムになります。目的を達成するまでにかかる手順の回数を、そのアルゴリズムの「計算量けいさんりょう」といい、計算にどれくらい時間がかかるかの目安にします。オーダエヌ」であるといいます。ちなみに先頭から順番に探すこのアルゴリズムは「線形探索せんけいたんさく」と呼ばれます。1.2より速いアルゴリズムさて「英和辞典の『Egg』を探す」という問題に対し、より計算量が少なくなるアルゴリズムを考えてみましょう。ここで本の中間のページを開き(全100ページの辞典なら50ページ目を開く)、そのページの左右のどちら側に『Egg』の項目があるかを判断して、『Egg』がある側の中間のページを開き同様の操作を繰り返す方法を考えます(図1-1)。二分探索このアルゴリズムを「二分探索にぶんたんさく」といいます。先ほどの線形探索では見つかるまですべてのページを探す必要がありましたが、二分探索では探す必要のないページを半分ずつ切り捨てていくためより高速になります。オーダログエヌ」であるといいます。ほかにも様々な計算量が存在します。主な計算量とその大小関係を図1-2にまとめました。値によらず、常に手順の回数が一定であるものです。」に比例するものです。超えると実用的でないほど計算に時間がかかるためあまり見かけません。」という表記は数学的に厳密に定義されていますが、アルゴリズムの大まかな計算量を扱う用途では厳密な定義を知らなくても問題ありません。計算量を専門的に扱うときには調べると良いでしょう。速いアルゴリズムを考案することは容易ではなく、アルゴリズムを競う大会もあるほどです。試しに、図1-3の問題のアルゴリズムを考えてみましょう。抜け落ちたカードぱっと思いつくのは、図1-4のアルゴリズムです。」のカードが存在するかどうか、1枚ずつ探して確認する。」のカードを順番に探す。存在しなかったカードが抜け落ちたカードである。抜け落ちたカードのアルゴリズム1確かにこの方法で、抜け落ちたカードが判ります。カードが1,000枚あった場合、最悪1,000,000回程度確認しなければなりません。この問題に対する速いアルゴリズムは図1-5の通りです。