計算量とは
アルゴリズムの良し悪しの指標として導入されたもの。一般に知られてるものとして$O-$記法です。
あくまで見積もりなので実際に計測（テスト)してみないとアルゴリズムの良し悪しは計れない。
以下、よく見る$O-$記法のチートシート。
表の上にいくほど良いアルゴリズムです。
| 計算量 | 例 |
|---|---|
| $O(1)$ | ハッシュ探索 |
| $O(\log n)$ | 二分探索やクイックソート |
| $O(n)$ | 線形探索 |
| $O(n\log n)$ | ヒープソート |
| $O(n^2)$ | 挿入ソート |
$O(1)$になるのが理想で、無理ならその次が$O(\log n)$それも無理なら…という風に設計しましょう。
自作アルゴリズムをオーダー記法で評価
線形計算量のアルゴリズム
以下の例は$O(n)$のアルゴリズムです。
for文で NankaNoSyori()という関数が$n$回呼ばれるので$O(n)$です。
for(int i=0;i<n;i++){
NankaNoSyori();
}
では次のコードではどうでしょう
for(int i=0;i<n;i++){
NankaNoSyori();
}
NankaNoSyori();
結果として、このアルゴリズムの計算量は$O(n)$です
これはNankaNoSyori()という関数が$n+1$回呼ばれるのですが$n$が例えば1000の時、
この+1の部分は小さいので無視します。
僕たちは1001個をわざわざ1001個とは呼ばず、1000個と呼びますがそんな感じです。
すなわち、NankaNoSyori()が$n$に依存しないとき、$O$記法ではこれを無視します。
$$O(n+1) = O(n)$$
不思議に思うかもしれませんががこの後ループを使わずにNankaNoSyori()を1000回書いても
$O(n+1000) = O(n)$となります。
for(int i=0;i<n;i++){
NankaNoSyori();
}
NankaNoSyori();
NankaNoSyori();
NankaNoSyori();
...
NankaNoSyori();
1000が$n$に依存しないからです。
これが計算量があくまでもアルゴリズムの見積もりである理由です。
入子構造
以下のアルゴリズムの評価は$O(n^2)$です。NankaNoSyori()を$n^2$回呼んでいるので理解しやすいと思います。
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
NankaNoSyori();
}
}
このコードを次のように少し変えてみましょう。
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
NankaNoSyori();
}
Nankanosyori();
}
合計で$n^2+n$回、NankaNoSyori()が呼ばれています。
オーダーは悪い方へ合わせます。見積もりは悪い方へ少しマージンをとりますよね。
なので
$$O(n^2+n) = O(n^2)$$
となります。
比例定数は無視する
オーダー記法では比例定数も無視します。
$$O(5n) = O(n)$$
これはなんの意味があるのでしょうか？
以下のグラフは$O(n)$に比較的近い$O(n\log n)$と比較してみました。
$n=５０$程度で差が開き始め、$n=100$で200程度も違いが生まれました。
$n=100$程度ではアルゴリズムを見積もる事ができたなんて到底言えません。
よって、係数は無視します。
オーダー記法の計算方法
1.一番悪い項を残す
2.係数を消し去る
この法則に則り次の計算をして見ると、
$$O(9n \log n + 7n^2 + 3n^3) = O(n^3)$$
となります。右辺の$n^3$が一番強いので$O-$記法ではこれ以外の影響は無視します。
どの項が悪くてどの項が良いか分からない時があります。最初の表を見てくれれば良いのですが、
微分など使いこなせるならロピタルの定理を思い出すといいかもしれません。
ロピタルの定理は
$$\lim_{x \to \infty} \cfrac{f(x)}{g(x)} = \lim_{x \to \infty} \cfrac{f'(x)}{g'(x)}$$
というものでした。
よく分かんなかったら微分して比較してみようという考えです。（大雑把過ぎる考えだが）
$O$記法に適応してもうまくいきます。
$O(n^2) ...(1)$と
$O(n\log n)...(2)$どちらが悪いのでしょうか？
どちらも微分して見ると
$(1)...O(2n) = O(n)$
$(2)...O(\log n+1) = O(\log n)$
よって(1)が悪い事がわかります。
実用例
以下バブルソートの実装例です。
int BubSort(int x[ ], int n){
for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
if (x[j - 1] > x[j]) { //比較する
int temp = x[j]; //交換する
x[j] = x[j - 1];
x[j - 1]= temp;
}
}
}
}
「比較回数」は、高々$n(n-1)/2$回$\to O(n^2)$
交換回数は一回のスキャンで平均$n/2$回なので、全体では平均$n(n-1)/4$回$\to O(n^2)$
$O$記法を使う際は「処理」と「変数$n$」について明言しておかないといけません。
ex1.配列のサイズ$n$で交換回数の計算量は$O(n^2)$だ
ex2.配列のサイズ$n$で比較回数の平均計算量は$O(n^2)$だ
平均計算量はこのように使います。
面白い計算量
以下のソースコードを見てみましょう。
bool xJudge(int x[],int n){
for(int i=0;i<n-1;i++){
if(x[i] > x[i+1]) return false;
}
return true;
}
void swap(int &x,int &y){int temp = x;x = y;y = temp;}
int BakaSort(int x[], int n){
while(1){
if(xJudge(x) == true) break;
swap(x[MyRand()%n],x[MyRand()%n]);
}
return 0;
}
MyRand() :完全乱整数生成関数と仮定します。STLにはこれが用意されています。
ループ毎にランダムに交換してるだけです。
最悪の場合、$\infty$秒たってもソートが終わらない可能性があります。
よって最悪計算量は$O(\infty)$です。
最良の場合、１回の交換でソートが終わる可能性もあります。
よって最良計算量は$O(1)$です。
メモリにも使ってみる
メモリの使用量にもこの考え方は利用できます。
$n$個のデータを格納するには$n$サイズの配列が必要なので$O(n)$だと言えます。
乱雑なデータなら$O(n)$以上の方法はないです。
しかし、何かしらの規則のあるデータなら、これより圧縮する方法があります。
乱数を格納
例えば乱数は数列ですが、rand()に$2^{32}-1$個の配列が格納されているとは到底思えないですよね。
（中学の時乱数表なるものを習いました。あの表が格納されているとも考え難い）
普通に乱数を出力しようと思うと$O(n)$の配列が必要です。
24までの乱数を表す乱数列${X_n}$は
$$X_{{n+1}}=\left(13 X_{n}+5 \right)\ {\bmod \ }24$$
という漸化式でかけます。
$X_n$だけ格納しておけば乱数を出力してくれます。
よって、擬似乱数生成におけるメモリ量は$O(n)\to O(1)$となります。
余談ですが何かしらの規則があるから圧縮できているわけです。完全な乱数ではなく
擬似乱数と呼ばれている理由はこれです。