計算量(O記法)の考え方まとめ

2024年も半年が経ちました。
外も暑くなり、夏の訪れを感じる人も増えてきたのではないでしょうか。

夏といえばお祭りです。
ということで、今日は 計算量祭りをやろうと思います。

＊この記事は夏に実施される編入学試験の対策も兼ねています

この記事でわかること

この記事は、「計算量？なにそれおいしいの？？」状態の人向けです。この人たちが読むと

・計算量は食べ物ではないことがわかる
・プログラムの計算量を見積もることができる。

以上の成長が期待できます。

①計算量とは

(1-1)計算量とは

実は、計算量には二種類あります。一つ目は時間計算量、もう一つは空間計算量です。
ほとんどの場合は、"計算量"といえば前者を指します。（最初のうちは）

時間計算量は、プログラムが実行される際にかかる時間を指しています。時間計算量が大きければ大きいほど、
そのプログラムの実行にかかる時間は大きくなります。

この記事も前者について話を進めます。

もし、時間的に効率の良いプログラムを作りたいと思ったら、まずこの時間計算量を小さくする工夫をしてみましょう。

(1-2)計算量の表し方

計算量はランダウのO記法を用いて大雑把に表します。
ランダウのО記法↓

関数$${f(x)}$$と関数$${g(x)}$$について、
$${ \lim_{x \to \infty} { \frac{f(x)}{g(x)} }=c }$$
となる実数$${c}$$が存在するとき（極限値が存在するとき）
ランダウのO記法を使って
$${ f(x)=O(g(x)) }$$
と表すことができる。

ここで$${ f(x) }$$はプログラムの計算の手数を関数として表したもの、
$${ g(x) }$$はそれを大雑把に表現したものです。
$${ g(x) }$$は$${ f(x) }$$から形を見積り、$${ \frac{f(x)}{g(x)} (x \to \infty) }$$が収束するようにします。

$${ g(x) }$$ は以下の二つの法則にしたがって見積もります。

i)最も次数の高い項以外は無視する
ii)係数は無視する

ここで$${ f(x)=3x^2+1000x+500 }$$という具体的な関数を用いて$${ g(x) }$$を見積もってみましょう。

i)最も次数の高い項以外は無視する

データ量が非常に大きい場合には、最も大きい次数以外が与える影響は小さいです。$${ f(x)=3x^{2} }$$と $${ f_2(x)=3x^{2}+1000x+500 }$$を比べてみましょう。

<$${ x=10^9 }$$のとき>
$${ f(x)=3000000000000000000 }$$
$${ f_2(x)=3000000100000000500 }$$

このようにしてみると、データが非常に大きいとき、$${ f(x) }$$と$${ f_2(x) }$$は、違いはあるものの、その差は全体に比べて非常に小さいものであることがわかると思います。このようなことから、最も大きい次数以外が与える影響は小さいと考えることができるため、無視できます。

ii)係数を無視する。

①で最大次数以外の項を無視しましたが、さらに大雑把にしていきます。
$${ f(x) }$$を$${ 3x^{2}}$$と見積もりましたが、実はこの係数である$${ 3 }$$も、$${ x }$$が非常に大きいとき、全体に与える影響が小さいので無視することができます。
$${ f_3(x)=10x^2 }$$と比べてみましょう。

十分に大きい$${ x }$$について極限を考えると、
$${ \lim_{x \to \infty} \frac{f(x)}{f_3(x)}= \frac{3}{10} }$$

この極限が収束したということは、ざっくりいうと、十分に大きい$${ x }$$について$${ f(x) }$$と$${f_3(x)}$$は大きな違いがないと考えることができます。
したがって係数部分の差が全体に与える影響は、大きくないと考える事が出来るので、係数部分は無視できます。

以上のi)、ii)のステップを踏むと、$${ g(x) }$$は$${ x^2 }$$と見積もることができます。実際に

$$
\lim_{x \to \infty} \frac{f(x)}{g(x)}= \lim_{x \to \infty} \frac{3x^2+500x+1000}{x^2}=3
$$

となり、
任意の実数に収束したので

$${ f(x)=O(g(x))= O(x^2) }$$

と考えることができます。

(1-3)プログラム全体の計算量を見積もる際の注意点

i)全体の計算量は、最も大きいものを選ぶ

例えば、
操作Ⅰ：$${ O(N) }$$
操作Ⅱ：$${ O(N^2) }$$
操作Ⅲ：$${ O(N) }$$

というプログラムがあるとき、全体の計算量は最も大きいものを選ぶので$${ O(N^2) }$$となります。

$${ O(N)+O(N^2)+O(N) }$$
$${ =max(O(N),O(N^2),O(N)) }$$（計算量の最大値）
$${ =O(N^2) }$$です。

ii)掛け算の場合は普通に掛け算する。

例えば

操作Ⅰ：$${ O(N) }$$
操作Ⅱ：操作Ⅰの操作を$${ N }$$回行う　$${ O(N) }$$

といった場合には、全体の計算量は
$${ O(N) \times O(N) }$$
$${ =O(N^2) }$$となる。

iii)異なる変数同士の足し算は、普段の足し算と同じ結果になる。

操作Ⅰ：$${ O(N) }$$
操作Ⅱ：$${ O(K) }$$
といった場合には、
$${ O(N)+O(K)=O(N+K) }$$
となる。

②各種アルゴリズムの時間計算量

次に各種アルゴリズムの時間計算量を紹介します。

個人的な意見ですが、プログラムの時間計算量は、ある程度有名なものについてだけはなんとなく覚えておいて、それ以外の場合は自分で考えて導出するものだと思います。異論は認めます。（ ※異論は認めます。）

ここではその”ある程度有名なもの”について紹介しているつもりです。網羅はしていないと思うのでご容赦ください。
載せてほしいアルゴリズムがある場合には、お手数ですが私に連絡をしていただくか諦めてください。

※データの量は$${ N }$$とします。
※”計算量”は、時間計算量、最悪時間計算量、計算複雑度を含みます。

i)挿入ソート： O(N^2)

挿入ソート：$${O(N^2)}$$
ソート済みの配列の末尾にデータを挿入し、昇順の状態になるまで交換を繰り返す。

＜導出＞
長さ$${ k }$$の数列にデータを挿入するとき、交換回数の最大値は$${ k }$$である。
これより、長さ１の状態から$${ n-1 }$$の状態まで、

$${ 1+2+3+ }$$・・・$${ (n-2)+(n-1) }$$
$${ =\sum_{k=1}^{n-1}k }$$

$${ =\sum_{k=0}^{n-1}k }$$

$${ =\frac12(n-1)n }$$

$${ =\frac12(n^2-n) }$$

$${ =O(n^2) }$$

＜特徴＞
このあと登場するバブルソート、選択ソートとは違い、ソート前の配列の状態によっては計算量が小さくなる可能性がある。実際に計算量が$${ O(N^2) }$$となるのは、ソート前の配列が 単調減少数列（降順）であるときである。

ii)バブルソート： O(N^2)

バブルソート：$${O(N^2)}$$
数列の後方から順にデータを比較して並べ替える。
ソート前の配列の並び方にかかわらず、交換回数はデータの長さに依存している。

＜導出＞
挿入ソートと同じ。

＜特徴＞
・同じ要素どうしが並んでいるとき、データの交換は行われないので、バブルソートは 安定ソートである。（ただしこれは交換条件を $${ a_{i-1}>a_i }$$としたとき。$${ a_{i-1}≧a_i }$$と実装した場合は...あっ（不安定））
・バブルソートの交換回数には、$${ 反転数 }$$という名前がついている。反転数は列の乱れ具合を示し、反転数が大きいほど列が乱れている。（厳密には、自分より添え字が低い数字の中で要素が大きい数字の組数。）

iii)選択ソート：O(N^2)

選択ソート：$${ O(N^2) }$$
配列の先頭から順に配列中の最小値と交換する。
例えば、長さ$${ n }$$の配列の$${ i }$$番目（$${ i }$$番目より前の要素についてはソート済み）を決定するとき、{$${ a_i,a_{i+1}, }$$ ・・・ $${ a_{n-1},a_n }$$}の中の最小値と$${ a_i }$$を交換する。

＜導出＞
挿入ソートと同じ

＜特徴＞
・選択ソートは離れた要素同士を交換するので、不安定なソート（安定ではない）である。
・一回の交換で選ばれた最小値の位置は確定する。

iv)マージソート：O(NlogN)

マージソート：$${ O(NlogN) }$$
マージソートは、この後紹介するクイックソートと共に分割統治法の考え方が用いられています。非常に速いです。長い配列に対して、小さい配列に分けてソートを考えようということです。「困難は分割せよ」ってこの前デカルトが言ってました。
マージソートはまず配列を半分に分け、分けられた配列についてそれぞれソートを行った後、分けた配列をマージ（統合）して元に戻します。

＜導出＞
※この方法は厳密ではないかもしれません。厳密な考え方を知りたい方は他の方の記事をご覧ください。
マージソートは以下の操作で成り立っています。

①配列を分ける操作：$${ O(1) }$$
（配列の要素がそれぞれ１つになるまで繰り返す。）：$${ O(logN) }$$回
②二つの配列を要素が小さい順に統合する。同じ長さの配列の統合回数を合わせると$${ O(N) }$$
③②にの操作を、配列が元の長さに戻るまで続ける。：$${ O(logN) }$$

②と③より$${ O(N) }$$の操作が$${ O(logN) }$$回行われ、この大きさは支配的なので
全体の計算量は$${ O(N)\times O(logN)= O(NlogN) }$$となる。

＜特徴＞
・どのような数列に対しても計算量は$${ O(NlogN) }$$となる。これは、配列の分け方配列の内容によらないからである。
・二つの配列を統合するときに、統合用の数列を別に用意する必要がある。このことから、メモリの使用量が非常に大きいというデメリットがある。（このようなソートを、外部のメモリが必要ということで 外部ソートという。）
・マージソートは安定なソートである。

v)クイックソート：O(NlogN) or O(N^2)

クイックソートの計算量は$${O(NlogN)}$$ or $${O(N^2)}$$
マージソートと同じ分割統治法に基づくソートです。速いか遅いかと言われたら非常に早いです。ソートが上手くいった場合には計算量は$${ O(NlogN) }$$となり、あのマージソートよりも早いです。ただ、上手くいかなかった場合は計算量が$${ O(N^2) }$$となって、 バブルソートなどと同じくらいの速さまで落ちてしまいます。
ソートが上手くいくか行かないかは ピポット（枢軸）の選び方に託されています。

＜導出＞
クイックソートの各操作と計算量を考えます。

①与えられた配列について、partitionを行う。：$${ O(N) }$$
②parititonによって与えられたピポット（枢軸）を中心にして、配列を二つに分ける。：$${ O(1) }$$
③②で作られた配列について、①の操作を繰り返す。：②操作が上手くいった場合：$${ O(logN) }$$/いかなかった場合$${ O(N) }$$

（partitionとは、ある要素を中心にそれ以上の数字と未満の数字に分ける操作の事を指します。partitionでは、中心となる数字とそれ以外の数字の比較を線形的に行うので$${ O(N) }$$です。）

③の通り、計算量$${ O(N) }$$のpartitionを、$${ O(logN) }$$or$${ O(N) }$$回行うので、計算量は$${ O(NlogN) }$$or$${ O(N^2) }$$となります。
枢軸として中央値を選ぶことができると、分割したときに、枢軸以上と枢軸未満の数字の個数が丁度半分になるので③の操作が$${ O(logN) }$$となります。一方で枢軸として最大値もしくは最小値を選んでしまうと、分割はほとんどできていないので、$${ O(N) }$$となってしまいます。（ソート前に配列が降順に並んでいると、計算量は$${ O(N^2) }$$となります。）

vi)計数ソート：O(N+K)

計数ソート：$${O(N+K)}$$
計数ソートは、配列中の要素の出現回数を記録し、その累積和を求めて、それを元にソートしたい配列の後方の要素からソート後の位置を確定させるソートです。

導出にあたって出てくる文字を説明しておきます。
$${ N }$$：ソートしたい配列の要素数
$${ K }$$：要素数の出現回数を記録する配列の長さ

＜導出＞
①要素の出現回数を記録する。：$${ O(N) }$$
②出現回数の累積和を求める。：$${ O(K) }$$
③②で作成した累積和を元にして、配列をソートする。：$${ O(N) }$$

①と②で行われる操作では、操作回数が違います。（②は$${ N }$$に依存しません。）
このことから$${ N }$$と区別するために$${ K }$$を用いて計算量を考えています。

以上より、全体の計算量は$${ O(N+K) }$$となります。

vii)幅優先探索、深さ優先探索： O(V+E)

幅優先探索、深さ優先探索：$${O(V+E)}$$
幅優先探索と深さ優先探索の説明はここでするには厳しいので省略します。
簡単にざっくりいうと、皆さんが迷路から抜け出すときにする考え方と似ています。

今回の計算量は、「与えられた始点から終点にたどりつくことは出来るか」といった問題に幅優先探索、深さ優先探索を適用したときの計算量を想定しています。

$${ V }$$：点（節）の数
$${ E }$$：道（辺）の本数

＜導出＞
この二つの探索は、一度訪れた点を再度訪れることはありません。探索にもっとも時間がかかるときは、全ての点と道を調べるときなので、計算量は$${ O(V+E) }$$となります。

＜特徴＞
競プロでよく出てきます。迷路を解くときによく使われるそうです。幅優先探索の考えは、カーナビの最短経路を求める際に使われているようです。

最後に

いかがだったでしょうか。最初は難しく感じたり鬱陶しく感じると思いますが、慣れてくると、コードを書く際に非常に便利に感じると思います。この記事を普段の学習に役立てていただけたら幸いです。

「ここ違うよ！」などのご指摘をくださると大変ありがたいです。
不明な点などの質問も、私でよければお待ちしております。

計算量祭り、まだ始まったばかりですyo。