アルゴリズム勉強会 計算量

Last-modified: 2014-12-18 (木) 18:34:39
 

計算量とは

計算量とは、アルゴリズムを評価する指標で、どのくらい計算に時間がかかるかを表したものです。
「O(N)」のように表記し、「オーダー N」と読みます。

せっかく考えたアルゴリズムでも、非現実的な時間がかかってしまっては意味がありません。
プログラムを書くときは、常に計算量のことを念頭に置いておく必要があります。

計算量の概念

大雑把にいうと、計算量はプログラム中のループ回数に一致します。

たとえば、次のプログラムを見てください。

for(i = 0; i < n; ++i){
    printf("nya-\n");
}

このプログラムの計算量は O(n) です。
n が増加するに従って、計算時間は一次関数的に増加します。

次のような、二重ループを持ったプログラムはどうなるでしょうか。

for(i = 0; i < n; ++i){
    for(j = 0; j < n; ++j){
        printf("myu-\n");
    }
}

このプログラムの計算量は O(n^2) になります。
n が増加するに従って、計算時間は二次関数的に増加します。

もう少し厳密な定義

計算量は、プログラムのループ回数になることは先程説明しました。
もう少し詳しく言うと、プログラムに対する入力が増加したとき、プログラムの実行時間がどのように増加するかを表した式になります。

たとえば、O(n^2) のアルゴリズムに対して、ある入力を与えたら実行時間が 1 秒かかったとします。
その場合、2倍の入力を与えたら 4 秒 (= 2^2)、3倍の入力を与えたら 9 秒 (= 3^2) かかると考えることができます。

このように、O(n^2) のアルゴリズムは、入力が増加した場合に実行時間が急激に増加します。このように、O(n^2) のアルゴリズムはあまり良いアルゴリズムとは言えません。

O(n^2) のアルゴリズムとして、有名なものにバブルソートがあります。
このように、バブルソートは非常に効率の悪いアルゴリズムであり、実用レベルではまず使われません。

計算量を求める際の注意

次のようなプログラムの計算量はどうなるでしょうか。

for(i = 0; i < n; ++i){
    for(j = 0; j < 10; ++j){
        printf("u-\n");
    }

    for(j = 0; j < 10; ++j){
        for(k = 0; k < n; ++k){
            printf("nya-\n");
        }
    }
}

単純に考えると、O( n(10+10n) ) = O( 10n^2 + 10n ) となります。
この時、複数の項がある場合は最大指数項のみを残し、係数を省きます。

つまり、この場合、O(n^2) となります。

まとめ

  • 計算量は、アルゴリズムを評価する為に使用する
  • 計算量は、大体の場合はループの回数と一致する
  • 計算量は、最大指数項のみを残し係数は省く

課題

次のプログラムを、計算量を考えながら解きなさい。

 

考察1

各問題の計算量を考えなさい。

 

考察2

問題 3「組み合わせ」において、n = 15 の場合、プログラムを実行したらどうなるか。
(プログラムの実行は終了するかどうか。)