よいアルゴリズムとは:アルゴリズムの基礎知識2

アルゴリズムの基礎知識

更新日:2022年12月2日(初回投稿)
著者:東京都立大学 経済経営学部 経済経営学科 准教授 森口 聡子

前回は、アルゴリズムの導入として、身近なアルゴリズムについて解説しました。現代では、アルゴリズムはコンピュータと密接に関係しているものの、アルゴリズム自体の歴史はコンピュータの登場よりもずっと古いこと、また、高校の数学でもアルゴリズムを用いていたことに触れました。今回は、アルゴリズムの性能について解説します。

1. よいアルゴリズムとは

コンピュータでアルゴリズムを使うとき、できればよいアルゴリズムを選びたくなるでしょう。ではよいアルゴリズムとは何でしょうか? 何でもできる、どんな問題でも解ける、汎用性の高いアルゴリズムでしょうか? それとも、とにかく高速に結論を出してくれるアルゴリズムでしょうか? どちらも兼ね備えた何でもできて、速いアルゴリズムがよいかもしれません。よいアルゴリズムを思い浮かべるとき、つい欲張りに考えてしまいます。

ところが、どんな問題でも最速で解くアルゴリズムは存在しません。汎用性と速さ、あるいは精度と速さには、トレードオフの関係があります(図1)。

図1:速度と汎用性のトレードオフの関係
図1:速度と汎用性のトレードオフの関係

高性能なコンピュータを用意して、同じアルゴリズムを用いたときの実行時間を短くすることはできるかもしれません。そして、同じ時間内に実行できることも増えるでしょう。コンピュータの性能を上げることで、速くする・精度を上げる・汎用性を増す、などを実現することは可能であっても、コンピュータ(ハードウェア)の性能差など、アルゴリズム自体の性能以外に起因することが含まれており、アルゴリズムの性能を論ずる際には、切り分けて考えなければなりません。

そして、どんなに処理能力が高く記憶容量が多いコンピュータとはいえ、その性能には上限があります。また、入力データが少ないときは処理が早く終わっても、データが多ければ処理に時間がかかってしまうというように、アルゴリズムを実行する際に必要なデータ量の選択によっても、結果を得るまでの時間に差が出てきます。そこで、アルゴリズム自体の性能を評価する尺度が必要になってきます。

実行時間は、コンピュータの記憶容量にも左右されます。メインメモリは、アクセスが速いけれどコストがかかる。外部メモリは、コストがあまりかからないけれどアクセスはより遅くなる。そういう観点から、遅いけれどメモリを食わないアルゴリズムか、速いけれどメモリを大食いするアルゴリズムか、という選択を迫られることもあります。これは、時間と空間のトレードオフの関係によるものです。従って、アルゴリズムと、それにマッチした的確なデータ構造を選択して、はじめて性能評価が可能になるということにも気を付けなければなりません。スーパーコンピュータで遅いアルゴリズムを用いるより、パソコンで速いアルゴリズムを用いる方が結果的に速いということも起こり得るものの、無意味な比較であることに気付くでしょう。アルゴリズムの性能評価をする際には、アルゴリズム自体の性能以外の条件をそろえた上で比較できなければなりません。

2. アルゴリズムの計算量

同じ目的を達成するためのアルゴリズムは、唯一とは限りません。一般に、複数の、多くのアルゴリズムがあり得ます。汎用性をさて置き、同じ目的のために、どのアルゴリズムを用いるのがよいかを判断する基準について説明します。

まず重要視されるのは、手続きを実行し始めてから終了するまでの計算時間でしょう。この計算時間を知るには、どうすればいいでしょうか。素朴な方法として、評価したいアルゴリズムそれぞれをコンピュータプログラムに実装し、実際にコンピュータで実行し、時間を測定すればいい、と思うかもしれません。しかし、前章で触れたとおり、条件をそろえるためには全て自分で実装する必要があったり、他人のこれまでの結果と比較できなかったりして、現実的には正確な評価や判断ができそうにありません。また、そもそもアルゴリズムを評価・比較する目的は、どのアルゴリズムをプログラム化すべきか決めるためであり、プログラム化する前にどのアルゴリズムがよいのかを事前判断しておきたいので、そのために実際に自分で全部プログラム化するというのは避けたいものです。

ここで登場するのが、計算量または複雑度と呼ばれる概念と、オーダと呼ばれる、いわゆるものさしです。アルゴリズムがどのような速さで目的の処理を実行するか、入力の大きさを関数の形で表現するものであり、実際にプログラムを作って実装することなく、事前に判断できるところが便利です。アルゴリズムに与える入力の大きさ(問題の大きさ)をnとして、アルゴリズムが結果を出すまでに要する処理時間を、nの関数f(n)として表します。nがどんどん大きくなると、f(n)も大きくなっていくことが分かります。また、f(n)が大きくなるスピードに着目することで、環境によらない評価ができるようになります。

計算量には、時間計算量と空間計算量の2つがあります。時間計算量は、実行が始まってから終わるまでの、命令が実行された回数(ステップ数)を表します。空間計算量は、アルゴリズムを解くときにどれほどの空間(メモリ)を使うかを表します。

・時間計算量と空間計算量

時間計算量では、1ステップ=アルゴリズム中の四則演算(+-×÷)や数値の大小比較を計算の基本単位として、アルゴリズムを終了するまでに基本単位を何回実行したかで、計算時間を見積もります。

前回の最大値を求めるアルゴリズムを例に見てみましょう。最大値を求める問題では、与える実数の個数nが入力の大きさ(問題の大きさ)です。このアルゴリズムのステップ2では、要素i>yかどうかを調べる大小比較をn-1回(n-1ステップ)行っています。ステップ数であれば、どの環境で実行した場合も変わらないことに着目しましょう。

環境によって、ステップ1での要素1を読み込んでyに格納する作業時間、ステップ2での大小比較1回当たりの時間、ステップ2でのy=要素iとする代入にかかる時間、ステップ3でのyを出力するのにかかる時間は異なり、nによらない定数です。最も時間がかかる最悪の場合を想定すると、

f(n)=「ステップ1での要素1を読み込んでyに格納する作業時間」

+(n-1)×「ステップ2での大小比較1回当たりの時間」

+(n-1)×「ステップ2でのy=要素iとする代入にかかる時間」

+「ステップ3でのyを出力するのにかかる時間」

のように見積もることができます。この結果を、もう少し簡略化してみます。nを大きくしていったとき、(n-1)がかけられた項は当然大きくなるものの、入力によらない定数の項は変わりません。式のうち、nの変化による影響を受けない部分を削除して、分かりやすくf(n)=O(n)と表します。ここで、Oは重要な項以外は無視するという意味が込められた記号で、オーダと読みます。O(n)はステップ数で、最悪nの定数倍に抑えられるということを意味します。

f(n)=O(p(n))は、nを大きくしていったとき、f(n)は、たかだかp(n)に比例するスピードでしか大きくならないことを意味します。この表記によって、アルゴリズムの計算量を直感的に把握することができるようになります。時間と同じように、アルゴリズムの中で使われる記憶領域の大きさもオーダで見積もることができます。これを空間計算量、あるいは空間複雑度と呼びます。時間計算量(時間複雑度)と空間計算量(空間複雑度)を合わせたものを、計算量または複雑度といいます。

3. 計算量の爆発

続きは、保管用PDFに掲載中。ぜひ、下記よりダウンロードして、ご覧ください。