アルゴリズムの効率と時間計算量・領域計算量の定義

2019年11月20日2020年3月15日アルゴリズム概要入門

アルゴリズムの効率

アルゴリズムの効率というのは、「計算量」と呼ばれる2つの指標によって評価することができます。

プログラムを実装する前に、これら2つの計算量を見積もって、現実的にプログラムを解くことができるのかを評価する必要があります。

時間計算量とは、アルゴリズムの実行(計算)に必要な時間を表す、計算の複雑さのことです。

一般的に「計算量」というとこちらを指すことが多いです。それは、後述する領域計算量よりも、時間計算量の方が問題になることが多いからです。本サイトでも特に断りの無い限りこちらを指すことにします。

時間計算量は、コンピュータの計算が終了するまでにどれだけの命令数必要だったかで見積もることができます。例えば、足し算という命令を1000回行うアルゴリズムよりも、10回で済むアルゴリズムのほうが時間計算量が小さいということになります。

領域計算量とは、アルゴリズムの実行(計算)に必要なコンピュータのメモリを表す、計算の複雑さのことです。

たくさんの変数をメモリ内に保持しておかなければならないアルゴリズムは、領域計算量が大きいと言えます。逆に、それほどメモリを使わなければ領域計算量は小さいと言えます。

近年の技術の発展は凄まじいもので、パソコン内のメモリは昔に比べると大幅に増えました。領域計算量を気にすることも少ないでしょう。