時間計算量と空間計算量

アルゴリズムを実行する際には一般的に入力変数に依存してアルゴリズムの実行時間と使用するメモリの量が変化する。それぞれを以下のようによぶ。

計算量の表記法

ある計算の上限・下限時間などを表記する方法として O, Ω, Θ 表記法がある。これらを漸近表記法とよぶ。

計算量の分類

計算は一般的に入力に依存して実行時間が変化するがそれぞれの入力に対して以下の 3 つに分類できる

計算量の比較

計算量 $O(f(n))$ について n が非常に大きくなった場合、$f(n)$ の 最も増加率高い項の影響が支配的 となり定数項や次数の低い項、係数は無視することができる。たとえば $O(8n^3 + 4n^2 + 1)$ という計算量について増加率が最も高い項は $8n^3$ となり n が非常に大きいときに $O(n^3)$ と考えても差し支えない。

項の影響力の大きさを表す 増加率 は以下のとおり

償却計算量（ならし解析）

一般的な可変長配列は通常 $O(1)$ で要素の追加が可能だが、例えば配列の要素数が 1, 2, 4, 8, 16, ... であるタイミングで要素を追加する際に 2倍のメモリを確保したのち、すべての既存の配列要素をコピーする処理が走るため $O(n)$ の計算が必要となる。連続して要素の追加を行う際の各回の計算は次のような形となる。

上記から可変長配列への要素の追加における計算量は定数項を無視できるので $O(n)$ とできる。しかしながら最良時計算量と最悪時計算量の差が大きく、n が十分おおきいときに最悪時となるケースの頻度は低下するため実態を反映しきれていない状況でもある。

ところで一連の n 回の計算に対する時間平均実行時間は次のように表せる: $(O(1) + O(n) + O(n) + O(1) + O(1) + O(n) + O(1) + ...) / n \sim O(\dfrac{n}{n}) = O(1)$。これを 償却計算量 とよぶ。

時間計算量の具体例

ループの時間計算量

1重ループの時間計算量は $O(n)$ となる。

for (int i = 0; i < n, i++) {
  doSomething()
}

2重ループの時間計算量は $O(n^2)$ となる。

for (int i = 0; i < n, i++) {
  for (int j = 0; j < n; j++ ) {
    doSomething()
  }
}

連続文の時間計算量

連続文の時間計算量はそれぞれの文の時間計算量の和となる。下記の例においては $O(n + n) = O(2n) \sim O(n)$

for (int i = 0; i < n, i++) {
  doSomething()
}

for (int j = 0; j < n, j++) {
  doSomething2()
}

if 文の時間計算量

if then A else B 文があったとき最悪時計算量は A, B どちらかの大きいほう、最良時計算量は小さいほうとなる。下記の例においては最悪時計算量 $O(n log(n))$、最良時計算量は $O(n)$

if (condition) {
  doOrderN()
} else {
  doOrderNLogN()
}

再帰の時間計算量

for 文や while 文に展開できる単純な再帰の場合は展開後にどのような計算量となるか考えれば再帰の計算量も導ける。例えば下記の例では単純に $O(n)$ となる。

int f(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + f(n - 1);
}

下記の例では return 文の箇所を 2 * f(n - 1) と最適化すればやはり $O(n)$ の計算となるが、ベタに実行するとなると再帰が深くなるごとに 2 のベキ乗回の計算が走る。よって計算量は $O(2^n)$ となる。

int f(int n) {
    if (n <= 0) {
        return 0;
    }
    return f(n - 1) + f(n - 1);
}

やや複雑な計算量となるアルゴリズムの実例

log (n) の計算量

例えば下記の例においては i が n を超えない範囲にてループのたびに 2 分割されていくため、ループを抜けるタイミングにおいて 2^i = n となる。i を n の関数として表現するため両辺に 2 を底とした対数をとると、計算量は $log_2 (n)$ となることがわかる。

for (int i = 1; i <= n, i = i * 2) {
  doSomething()
}

あるいは 10 個の要素を持つソート済み配列 as = {1, 3, 6, 9, 13, 23, 31, 35, 40, 43} から 3 を 二分探索(binary search) で抽出するシチュエーションを考えたとき as[5], as[2], as[1] と探索していき、合致したインデックス 1 を返す流れとなり、このアルゴリズムの計算量は配列の要素数 n に対して $log_2 (n)$ となる。

int as[] = {1, 3, 6, 9, 13, 23, 31, 35, 40, 43};

int find(int input[], int target, int startIndex, int endIndex) {
    int n = (startIndex + endIndex) / 2;
    int extracted = input[n];
    if (extracted == target) {
        return n;
    } else if (extracted > target) {
        return n == endIndex ? -1 : find(input, target, startIndex, n);
    } else {
        return n == startIndex ? -1 : find(input, target, n, endIndex);
    }
}

なお、ある関数 $f(n)$ の底の異なる対数 $x = log_{a} f(x)$ および $y = log_{b} f(x)$ を比較すると対数の定義よりそれぞれ $f(x) = a^x$ および $f(x) = b^y$ と書ける。したがって $a^x = b^y$ とでき両辺に例えば常用対数をとれば

となり、$f(n)$ の底の異なる対数同士は定数倍の違いでしかないことがわかる。したがって 計算量を考えるとき対数の底は切り捨てて考えることが可能 となる。

n log (n) の計算量

TODO

参考文献