アルゴリズムと計算量

アルゴリズム（algorithm）について

アルゴリズムとは

アルゴリズムとは、コンピュータで特定の目的を達成するための処理手順のことです。

プログラムは最適なアルゴリズムと最適なデータ構造を組み合わせることで実行性能が向上します。

アルゴリズム＋データ構造＝プログラム

アルゴリズムの性能（実行効率）

アルゴリズムの性能は、実行環境やハードウェア性能が異なれば、それぞれ異なる結果になるため、単純に経過時間で評価することは困難です。

そこで、アルゴリズムの性能は「計算量（complexity）」という抽象的な尺度を用いて表現します。

計算量は、同じ処理結果を求める複数のアルゴリズムがあった場合に、どのアルゴリズムが最も効率的であるか評価する指標となります。

計算量とは

コンピュータでは多くの場合に、メモリ容量を多く費やせば処理は速くなり、処理速度を犠牲にすればメモリを節約できるといった「時間と空間のトレードオフ」の関係が成り立ちます。

そこで、計算量は「時間計算量」と「領域計算量」に分けて算出されます。

時間計算量（time complexity）

時間計算量とは、あるアルゴリズムが問題を解くにあたって実行しなければならない処理や操作などの回数（ステップ数）のことです。

入力サイズの増加に対して、実行時間がどれくらいの割合で増加するかを表す指標となります。

領域計算量（space complexity）

領域計算量とは、アルゴリズム実行に必要な記憶領域（メモリ）の大きさに基づく計算量です。

計算量が少ないほど、より少ないメモリ容量で問題を解くことができます。

※空間計算量とも呼ばれます。

（備考）

最大計算量（worth case complexity）とは、計算量を求める際に最悪の手数となる入力データを用いた計算量のことです。

平均計算量（expected complexity）とは全ての入力データに対して平均となる計算量のことです。

O（オーダ）記法について

計算量の記述には、一般的に O記法 が用いられます。

この「O」はオーダー(Order)という単語に由来し、ランダウの記号とも呼ばれます。

O(n)とは

O（オーダ）は入力データのサイズ「n」の関数として表現します。

入力サイズ「n」の増大に対して計算量がどの割合で膨張するのかを示すものです。

O(n)のアルゴリズムは、アルゴリズムへの入力サイズ「n」に比例した回数の計算ステップを要することを意味します。

ループ処理などの全要素探索する(線形探索)ことを意味します。

    for (int i = 0; i < n; ++i) {
      // 処理 (なお、各 i に対する処理は軽いものとする)
    }

例えば、実行時間が入力の大きさ「nの2乗」に比例するアルゴリズムは「O(n^2)」と表現します。

2重ループを伴うアルゴリズムが該当します。

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        // 処理 (なお、各 i, j に対する処理は軽いものとする)
      }
    }

さらに、3重ループを伴う配列全体の走査（行列計算など）になれば、「O(n^3)」と表現します。

一般的には「O(n^3)」よりオーダの大きなアルゴリズムは実用にならないといわれています。

O(1)とは

O(1)はデータ量がどんなに増えても、常に一回しか処理を行わないことを意味します。

例えば、配列やハッシュテーブルなどの添字アクセスすることで一意にデータを取得できるアルゴリズムが該当します。

    print(array[0]);
    print(array[255]);
    print(hash["keyname1"]);
    print(hash["keyname2"]);

つまり、O(1)はどれだけデータ量が増えても計算量は一定であることを意味します。

（データ取得処理の実行環境に依存する要因は無視して時間計算量のみを考えます。）

対数オーダ

対数とは

対数とは、「〇を何乗すれば△になるか」を表す数のことです。

乗算は、「2を3乗したら x になる」ことを「2^3 = x」と表します。

対数は、「2を何乗すれば8になるか」を「log2(8) = x」と表し、「２を底とする８の対数は３」と答えます。

O(log n)

（※O(log n)は、一般的に計算量を求める場合は底を2として考えます。）

対数オーダは、データ量に対して、処理を繰り返しのたびに計算量が常に半分になっていきます。 （代表的には二分探索アルゴリズムが該当します。）

データ量が増えても計算時間がほとんど増えない特徴があります。

    for (int i = 1; i <= n; i = i * 2) {
      // 処理 (なお、各 i に対する処理は軽いものとする)
    }

O(n)とO(log n)の比較

O(n)は比例なので、nが2倍、3倍と増えると、計算量も同様に2倍、3倍となります。

O(log n)は、nが2倍、3倍と増えても、計算量は1、2と増える程度なのでデータ量が多い場合に有用です。

例えば、O(n)の代表として線形探索、O(log n)の代表として二分探索を比較してみます。

0 以上 32 未満の整数値から数字を当てる場合、大きな差はないですが、

→線形探索では最悪32回の試行が必要。

→二分探索では最悪5回の試行が必要。

65536 未満の整数値から数字を当てる場合、非常に大きな差が現れます。

→線形探索では最悪65536回の試行が必要。O(n) 回

→二分探索では最悪16回の試行が必要。O(log n)回

その他

O(sqrt(n))

入力サイズnにルート（平方根）を付けます。

例えば素数判定アルゴリズムでは下記のようになります。。

    bool is_prime(int n) {
        for (int i = 2; i*i <= n; ++i) {
            if (n % i == 0) return false;
        }
        return true;
    }

O(N!)

O(N!)は階乗時間（Nの階乗に比例した時間）と呼ばれ、全ての組み合わせによるNの階乗に比例するアルゴリズムです。

順列全探索nなどの要素の順番のすべての組み合わせを調べるような処理となります。

    void compute(int n) {
         if(n == 0){
             // 処理
             return;
         }
         for(int i = 0; i < n; ++i){
             compute(n - 1);
         }
     }

関連ページ

• ソフトウェア設計