アルゴリズム

もしかして? → アルゴリズムたいそう / アルゴリズムこうしん

アルゴリズムとは、「問題を解くための手順」である。

概要

アルゴリズムとは、「問題を解く手順(解き方)」のことである。

現代ではもっぱら「コンピューターの計算手順の最適化方法」を指すが、たとえば「ニコニコ大百科の読者が、一覧の一覧の編集履歴から、ストーリーを一行で語るの一覧が追加された日付を調べる手順」のように、コンピューター以外のものが処理できる手順についてもアルゴリズムと呼ぶことができる。

「いかに問題の解き方を工夫するか」というのが、アルゴリズムの研究と言ってほぼ間違いない。

例1

たとえば、1から100まで足し算することを考えてみよう。

1に2を足したら3、3に3を足して6、6に4を足して……と99回の足し算を手作業でがんばる人もいるかもしれない。実際、昔の人はそうやって足し算していた。しかし、この問題は、等差数列の和の公式を使えば(1+100)*100/2 = 5050と四則演算をたった3回するだけで答えが出る。

例2

次に概要で挙げた「ニコニコ大百科の読者が、「一覧の一覧」の編集履歴から、「ストーリーを一行で語るの一覧」が追加された日付を調べる手順」について検討してみようと思うが、長くなるので二分探索の記事に委ねることとする。

→ 二分探索

で、結局アルゴリズムって何の役に立つの？

つまり、アルゴリズムが優秀であれば、計算量を減らすことができるのだ。

ただし、手順が異なるだけであり、同じ問題を解決するのであるから、アルゴリズムの優劣によらず答えは一致している必要がある。

答えが同じなのに計算量を減らすのが何の役に立つって？ と思われるかもしれないが、これは非常に重要な問題で、第二次大戦以前からずーーーーっと脈々と研究が続けられてきた。なぜなら、計算する量が少なければ少ないほど、コンピュータが短い時間で答えを出せるからだ。

実用例1: 動画再生

たとえば、古いパソコンでニコニコを見ているとき、動画がカクカクしてイラッとしたことはないだろうか？ これも、コンピュータの処理能力が、計算量より低かったから生じる問題だ。つまり、ニコニコ動画が使っている「アルゴリズム」がさらにパワーアップすれば、古いパソコンでもヌルヌル字幕を動かせたりすることができるのだ。

実用例2: 暗号

それだけではない。たとえば現在広く使われているRSA暗号は、「コンピュータに解読させようとすると、あまりに時間がかかりすぎる」という理由で安全性が保たれている。 → P≠NP予想

つまり、「どんなRSA暗号でも速く解読するアルゴリズムを手に入れたぜ！」と宣言し、しかもそれが正しいと認められたなら、莫大な富と尊敬を得られる……かもしれない。いやむしろ、真っ先にFBIやらインターポールやらペンタゴンやらMI6やらがやってきて、映画「マーキュリー・ライジング」の登場人物のような運命が待っているのだろうか。とにかく全世界が震撼するのは間違いない。

アルゴリズムの評価方法

上述のように、計算量が少ないアルゴリズムが優秀なアルゴリズムということになるが、それだけでは比較しにくい。そこで、比較の際には計算回数(手順)がアルゴリズムで取り扱う対象の数の増加に合わせてどのような増え方をするかで評価を行う。

たとえば、上記例1においてnまでの総和を求めるために、地道に足し算する場合の足し算の回数はn-1で、和の公式を用いる方法なら四則演算の回数は常に3である。

別の例をとると、nチームで優勝者を決める場合、総当たり戦なら試合数はn(n-1)/2であり(優勝決定戦が必要になる可能性を除く)、トーナメント戦であれば試合数はn-1(優勝者以外は必ず1敗するため)である。

このようにn, n², n³,...など、計算や手順の実施回数が、対象となるnのべき乗の和(多項式)で表せるものを、多項式時間で解けるアルゴリズムと表現し、多項式時間(より短い時間)で解けるアルゴリズムが存在する問題を、多項式時間で解ける問題と表現する。

それに対して、計算回数が2ⁿなど、nが大きくなると多項式時間より大きくなる式(指数関数など)で表される場合は、多項式時間で解けないということになる。

逆(逆関数的)に計算回数がlog(n)に比例するアルゴリズムは、かなり優秀なアルゴリズムであると言える。例1で挙げた等差数列の和の公式は、計算回数はnが増えても増加しないので最高に優秀なアルゴリズムということになる。

条件により計算回数が一定しない場合は、計算回数の期待値や、最大値、最頻値のようなもので評価する場合もある。

関連動画

関連記事

• 数学
• コンピューター
• ユークリッドの互除法
• 再帰
• ライフゲーム
• boid
• 遺伝的アルゴリズム
• 二分探索(バイナリーサーチ)
• 動的計画法
• 線形計画問題
• 最短経路問題
• 最大流問題
• ソート
• P≠NP予想
• エンコード
• 暗号
• プロトコル
• 組合せ爆発
• プログラミング関連用語の一覧