第5章計算量

計算量とは

計算量とは、プログラムが問題を解くために必要なリソースの量を表す指標の一つです。このリソースは主に「時間」（処理にかかる時間）と「空間」（使用するメモリ）の二つに分けられます。それぞれを時間計算量、空間計算量と呼びます。

計算量を理解することは、プログラムが大規模なデータや複雑な問題に対して効率的に動作するかを評価するのに非常に重要です。

時間計算量：アルゴリズムが問題を解くのに必要な時間を示します。具体的には、アルゴリズムが実行する基本的な操作の回数のオーダーを表します。一般的には、Big O表記を使用して表されます。例えば、線形探索アルゴリズムの時間計算量はO(n)（nは配列の要素数）、バイナリサーチの時間計算量はO(log n)などです。
空間計算量：アルゴリズムが問題を解くのに必要なメモリ容量を示します。入力データだけでなく、アルゴリズムの実行中に追加で必要となるスペースも含まれます。この計算量もBig O表記を用いて表すことが一般的です。

アルゴリズムの時間計算量と空間計算量はトレードオフの関係にあることが多いです。つまり、一方を改善すると他方が悪化することがあります。例えば、データをメモリにキャッシュしておくことで計算時間を短縮できますが、その分、メモリ使用量が増えます。このようなトレードオフを考慮しながら、タスクの要求を満たす最適なアルゴリズムを選択することが求められます。

時間計算量

時間計算量は、あるアルゴリズムが問題を解くために必要なステップ（操作）の数を示しています。この数は入力の大きさ（n）に依存します。たとえば、n個の要素を持つリストをソートするために必要な時間、n個のノードを持つグラフでの探索時間などです。

計算量は通常、ビッグオー表記法（Big O notation）を使って表されます。これは最悪ケースの計算時間を示します。以下にいくつかの一般的な時間計算量を示します。

O(1): 定数時間

入力サイズにかかわらず、常に一定の時間がかかります。例えば、配列の特定の要素にアクセスする操作がこれに該当します。

function getItem(array, index) {
    return array[index];
}

O(n): 線形時間

入力サイズに直接比例する時間がかかります。例えば、配列の全ての要素を一度に一つずつ見ていく操作がこれに該当します。

function findMax(array) {
    let maxVal = array[0];
    for (let i = 1; i < array.length; i++) {
        if (array[i] > maxVal) {
            maxVal = array[i];
        }
    }
    return maxVal;
}

O(n^2): 二次時間

入力サイズの二乗に比例する時間がかかります。これは通常、二重ループの中で操作が行われるときに見られます。バブルソートや選択ソートなどの基本的なソートアルゴリズムがこれに該当します。

function bubbleSort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

O(log n): 対数時間

二分探索などがこれに該当します。データが倍になると、必要なステップ数は1つだけ増えます。。

function binarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (array[mid] === target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

空間計算量

空間計算量は、あるアルゴリズムが問題を解くために必要なメモリ（ストレージ）の量を示しています。この量も入力の大きさ（n）に依存します。たとえば、n個の要素を持つリストをソートするために必要なメモリスペースなどです。

計算量は通常、ビッグオー表記法（Big O notation）を使って表されます。以下にいくつかの一般的な空間計算量を示します。

O(1): 定数空間

入力サイズにかかわらず、常に一定のメモリが必要です。例えば、数値のインクリメントや特定の要素へのアクセスなどがこれに該当します。

function increment(x) {
    return x + 1;
}

O(n): 線形空間

入力サイズに直接比例するメモリが必要です。例えば、入力と同じサイズの新しいデータ構造を作成する場合がこれに該当します。

function copyArray(array) {
    let newArray = [];
    for (let i = 0; i < array.length; i++) {
        newArray[i] = array[i];
    }
    return newArray;
}

O(n^2): 二次空間

入力サイズの二乗に比例するメモリが必要です。これは通常、二次元配列を作成するときなどに見られます。

function createMatrix(n) {
    let matrix = [];
    for (let i = 0; i < n; i++) {
        matrix[i] = [];
        for (let j = 0; j < n; j++) {
            matrix[i][j] = 0;
        }
    }
    return matrix;
}

その他

O(n log n)

時間計算量: マージソートは一般的にO(n log n)の時間計算量を持つアルゴリズムです。

空間計算量: マージソートでは追加の配列を作成するため、空間計算量もO(n)となります。

function mergeSort(list)
    if length(list) <= 1
        return list
    middle = length(list) / 2
    left = mergeSort(list[0..middle-1])
    right = mergeSort(list[middle..end])
    return merge(left, right)

O(n^3)

時間計算量: 一般的な行列の乗算アルゴリズムはO(n^3)の時間計算量を持つ。

空間計算量: このアルゴリズムの空間計算量はO(n^2)です。なぜなら、3つのn x n行列を保存する必要があるからです。

function matrixMultiply(matrixA, matrixB)
    create an empty matrixC of size n x n
    for i from 0 to n-1
        for j from 0 to n-1
            for k from 0 to n-1
                matrixC[i][j] += matrixA[i][k] * matrixB[k][j]
    return matrixC

O(2^n)

時間計算量: フィボナッチ数列を再帰的に計算するアルゴリズムはO(2^n)の時間計算量を持つ。

空間計算量: このアルゴリズムの空間計算量はO(n)です。なぜなら、再帰的に関数を呼び出す際にスタックを使用し、その深さがnになるからです。

function fibonacci(n)
    if n <= 1
        return n
    return fibonacci(n-1) + fibonacci(n-2)

O(n!)

時間計算量: 全順列を生成するアルゴリズムはO(n!)の時間計算量を持つ。

空間計算量: 上記のアルゴリズムはO(n)の空間を使用します。再帰の深さがnで、各ステップで新たなリストを生成しないためです。

function permute(list, l, r)
    if l == r
        print list
    else
        for i from l to r
            swap(list[l], list[i])
            permute(list, l+1, r)
            swap(list[l], list[i]) // backtrack

第5章 計算量