情報ラボ ＞ アルゴリズム
同じ答えにたどり着くのでも、手順が違えば速さがまったく変わります。
同じ処理でも、手順によって必要な回数が大きく変わります。
データの個数を n としたとき、処理にかかる回数がどう増えるかを表す書き方を オーダー記法といい、O(n) のように書きます。 細かい係数は無視して、増え方の性質だけを見るのが特徴です。 データが少ないうちは差が出なくても、大きくなると決定的な違いになります。
ある問題を解くための、決まった手順のことをアルゴリズムといいます。料理のレシピに似ています。同じ料理でも、作り方は何通りもあり、手際のよい手順とそうでない手順があります。
コンピュータのプログラムも同じです。同じ答えを出すのでも、手順の選び方で処理時間が何百倍も変わることがあります。だからアルゴリズムを学ぶ意味があるのです。
アルゴリズムに求められる条件は3つです。手順が明確であること、必ず終わること、正しい答えが出ることです。
最も素直な方法です。先頭から順に、1つずつ調べていきます。見つかったら終了、最後まで見つからなければ「ない」と答えます。
単純で、どんなデータにも使えるのが利点です。並んでいなくても構いません。ただし、データが多いと時間がかかります。1000個のデータなら、最悪1000回調べることになります。
データが小さい順に並んでいるとき使える方法です。手順はこうです。
1回調べるごとに、探す範囲が半分になります。これが決定的な差を生みます。
1000個のデータでも、たった10回で見つかります。線形探索なら最悪1000回かかるところです。データが100万個になると、線形探索は100万回、二分探索は20回。差は歴然です。
ただし条件があります。あらかじめ並んでいることです。並んでいないデータには使えません。辞書や電話帳で目的の項目をすぐ探せるのは、五十音順に並んでいるからです。
二分探索を使うには、まず並べる必要があります。この並べかえを整列（ソート）といいます。
となり合う2つを比べ、順序が逆なら入れかえます。これを繰り返すと、大きい数が泡のように後ろへ移動していきます。
仕組みが分かりやすい反面、効率はよくありません。n個のデータに対して、比較の回数はおよそ n² に比例します。
まだ並んでいない範囲から最小のものを探し、先頭と交換します。次は2番目から同じことを繰り返します。
入れかえの回数が少ないのが特徴です。比較は多いものの、交換は最大でもn回で済みます。
トランプを手札に並べるときの動きに似ています。左から順に、すでに並んでいる部分の適切な位置へ差し込んでいきます。
すでにある程度並んでいるデータに対しては、非常に速く動きます。
実用的なプログラムでは、クイックソートやマージソートといった方法が使われます。データを分割して個別に処理する考え方（分割統治法）を使い、n log n に比例する回数で並べられます。
データが100万個のとき、n² なら1兆回ですが、n log n なら約2000万回です。5万倍の差になります。
アルゴリズムの効率を表すのに、計算量という概念を使います。データの個数 n が増えたとき、必要な処理回数がどう増えるかを見ます。
| 記法 | 増え方 | 例 |
|---|---|---|
| O(1) | データが増えても変わらない | 配列の何番目かを取り出す |
| O(log n) | とてもゆっくり増える | 二分探索 |
| O(n) | 比例して増える | 線形探索 |
| O(n log n) | やや速く増える | クイックソート |
| O(n²) | 急激に増える | バブルソート |
大切なのは、データが少ないうちは差が出ないという点です。10個程度なら、どのアルゴリズムでも一瞬で終わります。違いが表れるのは、データが大きくなったときです。
現代では、扱うデータが膨大になっています。検索エンジンは数百億のページを、SNSは数十億の利用者を扱います。この規模になると、アルゴリズムの選択が実現できるかどうかを決めてしまいます。
アルゴリズムは、日常のあちこちで動いています。
どれも、単に計算が速いコンピュータがあれば済む話ではありません。賢い手順があってこそ、現実的な時間で答えが出せるのです。
手順を人に伝えるには、書き表す方法が必要です。いくつかの方法があります。
| 方法 | 特徴 |
|---|---|
| 流れ図（フローチャート） | 記号と矢印で処理の流れを図にする。全体像がつかみやすい |
| 擬似言語 | プログラムに近い書き方だが、特定の言語には縛られない |
| アクティビティ図 | 並行する処理も表現できる |
流れ図では、記号の意味が決まっています。長方形は処理、ひし形は条件による分岐、平行四辺形はデータの入出力です。共通テストでも、擬似言語を使った問題が出題されています。
どんなに複雑なプログラムも、3つの構造の組み合わせで書けることが知られています。
この3つだけで足りるという事実は、構造化定理として証明されています。だから、まずこの3つを確実に理解することが、プログラミングの土台になります。