アルゴリズムとは? 手順の工夫で計算が速くなるしくみ
アルゴリズムとは、問題を解くための手順のうち、終わりがあり、誰がたどっても同じ結果になるもののことです。同じ答えを出す手順でも、工夫しだいで手間は大きく変わります。順に並んだ100万件から1件を探すとき、端から見ると最大100万回比べますが、範囲を半分ずつ絞れば20回で済みます。
この記事でわかること
- アルゴリズムの意味と、料理のレシピとの似ている点・違う点
- 「探す」「並べ替える」で、手順の違いが何万倍もの差になる理由
- 計算量(オーダー記法)の読み方: O(n) や O(n²) は何を表すのか
- 速いコンピュータでも遠回りの手順は救えない理由と、GPU向けの手順の工夫
前提知識: 特にありません。掛け算と「2倍」「半分」がわかれば読めます。
身近なところでは
地図アプリに行き先を入れると、数秒で道順が出ます。検索サイトに言葉を入れると、膨大なページの中から役に立ちそうなものが上に並びます。動画アプリは、あなたが見そうな動画を勧めてきます。
ばらばらのトランプを、数字の順に並べる場面を考えてみましょう。一番小さいカードを探しては抜き出すか、いくつかの山に分けてから合わせるか。人は何かしらのやり方を選んでいて、やり方によってかかる時間がずいぶん違います。
こうした「答えを出すための手順」を、アルゴリズムと呼びます。ニュースでは「SNSのアルゴリズム」という言い方もよく見かけます。この記事では、アルゴリズムとは何か、なぜ手順の工夫で計算が速くなるのかを、数字で確かめていきます。
アルゴリズムは「終わりのある、はっきりした手順」
アルゴリズムは、ある問題を解くための段階を、順番に書き表したものです。材料(入力)を受け取り、決まった段階を踏んで、答え(出力)を出します。たとえば、数の並びから一番大きい数を探す手順は次のとおりです。先頭の数を仮の最大とし、次の数と比べて、大きければ仮の最大を入れかえます。これを最後の数まで続けます。
ただの「やり方」と違うのは、2つの条件です。1つ目は、どの段階も意味がはっきりしていて、誰がたどっても同じことをすること。2つ目は、どんな入力でも、いつかは必ず終わることです。計算機科学者ドナルド・クヌースは、有名な教科書でアルゴリズムの性質を5つ挙げました。この2つに、入力・出力・実際に行えることを加えた5つです。
コンピュータの中心の部品であるCPUは、「足す」「比べる」のような単純な命令を1つずつ実行するだけです。どの命令をどの順に並べれば答えが出るか、という手順の考え方がアルゴリズムです。CPUのしくみは「CPUとは?」で説明しています。
「アルゴリズム」という言葉は、9世紀の数学者アル=フワーリズミーの名前に由来します。彼が書いたインドの数字(今の算用数字)での計算法の本が、ラテン語に訳されてヨーロッパに広まりました。その訳で使われた名前の形が、言葉のもとになりました。
探し方の違い: 端から順に、か、半分ずつ、か
100万人の会員の名簿から、ある番号の人を探すとします。一番素直なのは、先頭から1件ずつ比べていく方法です。この方法を「線形探索」と呼びます。運が悪いと、最後の1件まで100万回比べることになります。
名簿が番号の順に並んでいれば、もっとよい方法があります。まず、真ん中の1件と比べます。探す番号のほうが大きければ前半には絶対にいないので、後半だけを残します。これをくり返すと、1回比べるごとに範囲が半分になります。この方法を二分探索と呼びます。
100万件を半分にし続けると、50万、25万…と減り、20回目の比較で必ず決着がつきます。2を20回掛けると1,048,576になり、100万を超えるからです。つまり二分探索なら、見つかっても見つからなくても、多くて20回で終わります。100万回と20回では、5万倍の違いです。
紙の辞書を引くとき、人は最初のページから順にめくりません。あたりをつけて開き、前か後ろかを見て絞っていきます。二分探索は、この絞り込みを「ちょうど真ん中」で、機械的にくり返す方法です。
ただし、二分探索には条件があります。データが前もって順に並んでいることです。ばらばらの名簿では、真ん中と比べても、どちら側にあるかわかりません。そのため、次に見る「並べ替え」も、大事な仕事になります。
並べ替えでも、何万倍もの差が出る
データを決まった順に並べ替えることを「ソート」と呼びます。ここでは2つのやり方を比べます。手間の目安として、「2枚のカードの大小を比べた回数」を数えます。
1つ目は素直な方法です。まだ並べていないカードの中から一番小さいものを探し、列の後ろに足していきます。一番小さいものを探すには、残りのカードをすべて見る必要があります。n枚なら、比べる回数は1回目がn−1回、2回目がn−2回…と1ずつ減ります。合計はおよそ「n×n÷2」回です(この方法は選択ソートと呼ばれます)。
2つ目は「マージソート」です。カードの山を半分に分け、それをまた半分に分けて、1枚ずつになるまで分けます。次に、小さな山を2つずつ合わせていきます。2つの山の一番上どうしを比べ、小さいほうを取ることをくり返すと、順に並んだ1つの山になります。
マージソートが速いのは、半分に分ける回数が少ないからです。100万枚でも、20回ほど半分にすれば1枚ずつになります。合わせる作業は、どの段でも全部のカードを1回ずつ見るだけです。そのため比べる回数は、およそ「枚数×半分にする回数」で済みます。「nを何回半分にすると1になるか」を log₂n と書くので、これは n×log₂n 回です。
| 枚数 | 素直な方法(約 n×n÷2 回) | マージソート(約 n×log₂n 回) | 差 |
|---|---|---|---|
| 52枚(トランプ1組) | 1,326回 | 約300回 | 約4倍 |
| 1万 | 約5,000万回 | 約13万回 | 約380倍 |
| 100万 | 約5,000億回 | 約2,000万回 | 約2万5,000倍 |
マージソートの欄は n×log₂n で出した目安で、実際に比べる回数はこれより少し少なくなります。トランプ1組なら差は4倍ほどで、手で並べるならどちらでもかまいません。しかし枚数が増えるほど、差はどんどん開きます。動きを目で見たい人は、ソートの動きを見るツールでいくつかの方法を比べられます。
計算量: 手間の「増え方」で比べる
ここまでの例で大事なのは、手間の「量」より「増え方」です。データが2倍になると、線形探索の手間は2倍になります。二分探索は1回増えるだけです。素直な並べ替えは4倍になります。
データの数に対して、手間がどのように増えるか。これを計算量と呼びます。同じ問題を解く手順どうしを、コンピュータの速さとは関係なく比べるための物差しです。
計算量は、O(n) や O(n²) のように「O(オー)」をつけて書きます。この書き方をオーダー記法と呼び、かっこの中の n はデータの数です。O(n²) なら「手間がおよそ n×n に比例して増える」という意味です。「÷2」のような係数は省きます。係数は、データが2倍のとき手間が何倍になるかを変えないからです。
| 書き方 | nが2倍になると | n=100万での回数の目安 | 例 |
|---|---|---|---|
| O(1) | 変わらない | 1 | 何番目かがわかっている場所を読む |
| O(log n) | 1回増える | 約20 | 二分探索 |
| O(n) | 2倍 | 100万 | 線形探索、合計を出す |
| O(n log n) | 2倍より少し多い | 約2,000万 | マージソート |
| O(n²) | 4倍 | 1兆 | 素直な並べ替え、すべての2つの組を比べる |
| O(2ⁿ) | nが1増えるだけで2倍 | (n=50でも約1,100兆) | すべての組み合わせを試す |
表の log は、さきほどと同じ「何回半分にすると1になるか」で数えています。O(n²) の欄が1兆で、前の表の5,000億と違うのは、係数の「÷2」を省いたためです。
一番やっかいなのは O(2ⁿ) です。50個の品物から「どれを選ぶか」の組み合わせをすべて試すと、2を50回掛けた約1,100兆通りになります。1秒に10億通り調べても、約13日かかります。品物が51個になれば、さらに倍です。数を変えて試したい人は、計算量(オーダー)の比較ツールで回数と時間を計算できます。
速いコンピュータでも、遠回りの手順は救えない
1秒に10億回比べられるコンピュータを考えます。話を簡単にするため、1回の比較にかかる時間はいつも同じとします。100万件を素直な方法で並べ替えると、約5,000億回の比較に約500秒、8分あまりかかります。マージソートなら約2,000万回で、0.02秒です。
では、100倍速いコンピュータに買いかえたらどうでしょう。素直な方法でも5秒になります。それでも、古いコンピュータでマージソートを使ったほうが250倍速いのです。
さらに、データが10倍の1,000万件に増えたとします。素直な方法は手間が100倍になるので、100倍速いコンピュータでも約500秒かかります。古いコンピュータのマージソートなら、約0.23秒です。O(n²) の手順では、100倍の性能も、データが10倍になるだけで使い切ってしまいます。
半導体の進歩によって、コンピュータは何十年も速くなり続けてきました(「ムーアの法則とは?」)。それでもアルゴリズムの研究が欠かせないのは、このためです。
歴史に残るアルゴリズム
ダイクストラ法(1959年): 一番近い道を探す
地点と、地点を結ぶ道の長さがわかっているとき、出発点から各地点への最短の道を求める方法です。出発点から近い地点の順に「ここまでの最短距離」を確定させ、その先の地点の距離を更新していきます。オランダのエドガー・ダイクストラが1956年に考え、1959年に論文で発表しました。この方法をダイクストラ法と呼びます。
ダイクストラは後に、アムステルダムのカフェで、紙と鉛筆を使わずに20分ほどで考えたと語っています。ネットワークの通信の経路を決めるしくみ(OSPF)でも、この方法で経路を計算します。
PageRank(1998年): ページの大事さを、リンクから測る
スタンフォード大学の大学院生だったセルゲイ・ブリンとラリー・ペイジが考えました。1998年の論文で、検索エンジンGoogleの試作とあわせて発表しています。多くのページからリンクされ、しかも大事なページからリンクされているページほど、大事だと考えます。Googleの公式の案内によれば、今の検索はPageRankを含む多くのしくみを組み合わせて順位を決めています。
RSA暗号(1977年): 「手間がかかる」ことを守りに使う
MITのリベスト、シャミア、エーデルマンの3人が1977年に報告し、1978年に論文誌に載りました。2つの大きな素数を掛けるのは簡単でも、掛けた結果から元の2つを見つけるのは、知られている手順ではとても時間がかかります。この手間の差を、RSA暗号は安全の土台にしています。くわしくは「暗号とは?」で説明しています。
迷路の探索(1961年): チップの配線を決める
1961年、C. Y. リーは、障害物をよけながら2つの点をつなぐ道を探す方法を発表しました。スタート地点から、隣のマス、その隣のマスと波が広がるように番号をつけ、ゴールに届いたら番号をたどって戻ります。回路基板や半導体チップの配線を自動で決める設計ソフトでは、この考えを発展させた方法が古くから使われています。
並列に動くチップのためのアルゴリズム
アルゴリズムは、それを動かす部品に合わせて選ぶことも大切です。GPUは、単純な計算回路を数千個以上も並べて、同時に動かすチップです。その力を生かすには、手順も同時に進める形に組み直す必要があります。
例として、1,024個の数の合計を考えます。1つずつ足していくと、足し算は1,023回で、前の答えを待ちながら1回ずつ順に進みます。並列にするなら、まず2つずつ組にして、512組の足し算を同時に行います。残った512個をまた2つずつ足すと256個になります。これをくり返すと、10回目で1つの合計になります。
足し算の回数は、どちらも1,023回で変わりません。変わるのは、前の答えを待つ回数です。順に足すと1,023回分待ちますが、並列なら10回分で済みます。GPUの会社NVIDIAの技術資料でも、GPUで多くの数を合計する基本の形として、この木の形の足し方を説明しています。
反対に、前の結果を見ないと次に進めない手順は、並列にしにくい性質があります。二分探索は、1回前の比較の結果で次に見る場所が決まるので、その代表です。AIの計算が、なぜ同時に進める形に向いているのかは「なぜAIにGPUが使われるの?」で説明しています。
よくある誤解
誤解: アルゴリズムとは、特定のプログラミング言語で書いたプログラムのこと
実際は、アルゴリズムは手順そのもので、書き表し方には左右されません。二分探索は、Pythonで書いてもC言語で書いても、紙と鉛筆で行っても、同じ二分探索です。プログラムは、アルゴリズムをある言語で書き表したもので、それをコンパイラなどが機械語に直してCPUが実行します(「コンパイラとは?」)。回路として作り込むこともできます。足し算の筆算の手順は、CPUの中では足し算の回路になっています(「コンピュータは0と1でどう計算するの?」)。コンピュータで動かすときは必ずプログラムの形になるので、両者は混同されやすいのです。
誤解: 新しい速いコンピュータなら、手順のよしあしは関係ない
実際は、データが多いと、100倍速いコンピュータでも O(n²) の手順は O(n log n) の手順にかないません。データが少ないうちは差が見えないので、問題に気づくのは、データが増えてからになりがちです。逆に、データがごく少ないときは、手順の単純な方法のほうが速いこともあります。計算量は増え方の目安で、省いた係数が効いてくるからです。
誤解: SNSの「アルゴリズム」は、1つの決まった計算式
実際は、たくさんの手順やAIのモデルを組み合わせたしくみ全体を、まとめてそう呼んでいます。Instagramの責任者アダム・モセリは2021年に、こう説明しました。見せるものを決める1つのアルゴリズムはなく、目的の違う多くのしくみを使っている、と。X(旧Twitter)が2023年に公開した推薦のしくみも、いくつもの段階に分かれています。候補を集める、AIで点数をつける、ルールで絞り込む、などです。中で使うAIのモデルは、人が1行ずつ手順を書くのではなく、データから自動で調整されます(「機械学習とは?」)。
数字で見る
| 項目 | 数字 | メモ |
|---|---|---|
| 100万件から線形探索 | 最大100万回 | 端から順に比べる |
| 100万件から二分探索 | 最大20回 | 2を20回掛けると1,048,576 |
| 100万件を素直な方法で並べ替え | 約5,000億回 | 1秒に10億回比べて約8分 |
| 100万件をマージソートで並べ替え | 約2,000万回 | 同じ速さで約0.02秒 |
| 50個の品物の選び方を全部試す | 約1,100兆通り | 1秒に10億通りで約13日 |
| 1,024個の数の合計(並列) | 10回分の時間 | 順に足すと1,023回分 |
| ダイクストラ法 | 1959年に発表 | 考えたのは1956年 |
| RSA暗号 | 1977年に報告 | 論文誌への掲載は1978年 |
| PageRank | 1998年の論文 | ブリンとペイジ |
上の回数は、1回の比較の時間を一定とした目安です。実際の時間は、メモリからデータを運ぶ速さなどでも変わります。
もっと詳しく学ぶ
- 試してみる: ソートの動きを見るツール、計算量(オーダー)の比較ツール、ダイクストラ法の計算ツール、二分探索木・ヒープの可視化ツール
- 違いを表で見る: 幅優先探索と深さ優先探索の違い、配列と連結リストの違い、CPUとGPUの違い
- 次の一歩の用語: 安定ソート、再帰、ハッシュテーブル、貪欲法、動的計画法
- 土台から読む: 「CPUとは?」、「コンパイラとは?」、「なぜAIにGPUが使われるの?」