ビッグ・オー記法についての勉強メモ

ビッグ・オー(Big O)記法について勉強をはじめました。

ビッグ・オー記法とは、アルゴリズムの性能を記述するための方法。

プログラムを作成→そのプログラムを実行することでどれくらいの時間や計算量がかかるかを簡単に表現することでプログラムが効率的かなどが大まかに把握でき評価できるというもの。

ビッグ・オー記法によって、自分で作ったプログラムが速いのか、遅いのか、処理するn数が増えると計算量がめっちゃ多くなるなどが判断できるようになる。

表現の方法：O(n)、O(1)のように書く。

このプログラムはO(n)だみたいに、プログラムの内容から自分で判断しないといけないので、判断を間違えやすそう。

ビッグ・オー記法を使いこなすためには、プログラムを目で見て、計算時間や計算量がどうなるのかをちゃんと判断できる見方を身につける必要がありそう。

時間計算量とは

ビッグ・オー記法のO(1)やO(n)そのものが意味するもの。

ファイルのサイズをsとすると、そのファイルを送信するためにかかる実行時間は、ファイルサイズが大きくなるほど実行時間も増える。実行時間をビッグ・オー記法で表すと、O(s)と表すことができる。

O(s)という表現から、sが大きくなるほど計算にかかる時間も増えるので、線形で増加することが読み取れる。

ビッグ・オーは計算時間の上限を表す。

計算時間が速いことよりも、遅いことの方が注意すべきなので、計算時間の下限よりも上限のほうがプログラムを判断するときに重要になってくる。

逆に計算時間の下限が分かっても、あまり役に立たないため。

計算時間の下限を表す指標もあって、それはビッグ・オメガ(Ω)という。

ビッグ・シータ(Θ)という指標もあって、それは上限と下限の両方を表している。つまり、計算時間の下限、上限の境界を表している。

空間計算量とは｜アルゴリズム(プログラム)は計算時間だけでなく空間計算量(メモリの使用量)も重要

プログラムの実行にかかる時間だけでなく、メモリの使用量も重要。

再帰的な関数を使う場合、関数の呼び出しごとにスタックに積まれる(保存する)ため、メモリの消費が大きくなる。

計算量(時間)とメモリ使用量はそれぞれ分けてビッグオー記法を考える。

“このプログラムの実行はO(n)の時間とO(1)のメモリ使用量する。”-

のように、それぞれ分けて考える。

ビッグ・オー記法は定数を切り捨てて考える

例えば、O(2n)だとすると、2を切り捨ててO(n)と表す。

nが小さくても大きくなっても2は一定なので無視する。

ビッグ・オー記法は単に計算量増加の割合(増え具合)を表しているため。

2nもnも増え具合で考えると変わらないので、2を切り捨てる。

プログラムAはO(1)の実行時間

プログラムBはO(n)の実行時間

だとすると、直観的にみるとO(1) のほうが実行時間が速いと思ってしまうけど、O(1)のほうがO(n)よりも速いとは限らないことに注意が必要。

たとえばO(1)は一定時間で実行できるけど、その時間がめっちゃ長いかもしれないなど。

影響が少ない項も切り捨てる

例）O(N^2 + N)
N^2とNではNの影響は小さいので切り捨てて考えて、

O(N^2)とみなす。

理由：

O(N^2 + N^2) -> O(2N^2)で、定数の2は切り捨てる。

ということは、O(N^2 + N)のNは切り捨てるということ。 

正直ここはあまり納得できない気がするけど、まずはそのようになることを覚えておこうと思う。

計算量の増加量の多い順の例

O(x!) > O(2^x) > O(x^2) > O(x log x) > O(x) > O(log x)

階乗は計算量の増加が著しく、グラフにすると急こう配になるけど、上記はあくまで一例で、これよりももっと計算量の増加が多くなるものもあるらしい。

プログラムが複数のパートを持つ場合の計算時間の考えかた

実行時間を足す場合と、実行時間を掛ける場合がある。

実行時間が足し算になる例： O(A + B)

int main() {
//for文A
for(){ print(a); } 
//for文B
for() { print(b); }
}

Aの処理が終わったあとにBの処理をしているので、計算量は足し算になる。

→Aが終わったらBを行う。という処理の計算量は足し算になる。

実行時間が掛け算になる例： O(A*B)

int main(){
  for(int i; i < N; i++){
    for(int j; j < M; j++){
      A(i) + B(j);
    }
  }
}

2重ループのように、Aの要素のそれぞれに対してBの処理を行うような処理の計算量は掛け算O(A*B)になる。

→Aを行うごとにBを行う。という処理の計算量は掛け算になる。

償却計算量とは

配列に要素を追加していき、配列のサイズがいっぱいになったら元の配列を要素も込みでコピーすることで元の配列の2倍の配列を作ることで動的にサイズを増やす配列の場合を考える。

上記のように配列に要素追加していくプログラムの場合、頻度は高くはないけど、配列がいっぱいになったときだけ発生するケースについても考慮した実行時間を考える必要がある。

要素数Nの配列がいっぱいになったとき、新しい要素を１個追加するには、O(N)の実行時間がかかる。

コピーの操作自体、1要素ずつコピーするのでO(N)の実行時間がかかると解釈しました。

コピーする -> [a, b, c, d, e] [a, b, c, d, e]

一方、配列が要素でいっぱいになってないときは、配列に1個の要素を追加するだけなので実行時間はO(1)

このO(N)とO(1)を考慮することを償却計算量と呼ぶ。

償却計算量という考え方を利用することで、たまに発生する配列の生成とコピーといった計算時間が最悪となるケースについて記述することができる。

しかし、最悪ケースは通常の要素の追加と比べてめったに発生しないので、実行時間としては通常の要素1個の挿入にかかる時間を意味するO(1)の方をメインとする。

-> たまに発生する最悪ケースを考慮するという意味で償却計算量という。

例）3個の要素でいっぱいになる配列の場合

例は、こんな感じかなみたいな、あくまで動作のイメージです。

[a, b, c]  <-- 3個の要素でいっぱいになった配列

要素dを追加したい。

[1, 2, 3, 4, 5, 6] <-- 要素数6個のサイズの配列を生成(数字は添字を表している)

[a, b, c] <-- この要素をすべて添字4、5、6に一つずつ上記の生成した配列内に追加する。そして空文字で初期化する。

[a, b, c, d, 5, 6] <-- 要素dを追加(5、6は添字であと2個分サイズに余裕あり)

→上記から、通常は要素追加するだけなら実行時間はO(1)だけど配列がいっぱいになるたびにO(3(=N))の実行時間が必要になる。

償却計算量の例｜配列リスト

要素を挿入するとき、配列のサイズが2の累乗になるときに配列のサイズが2倍になるという配列の仕様のケース

→x= 8個の要素を入れる場合、配列のサイズを1, 2, 4, 8のように倍にしていく。

感覚的には違和感があり、上記は4回しかサイズを倍にしていないように思えるけど、実際は8回と同じ。なぜなら、サイズを増やす操作となっているので、サイズが増えれば増えるほどメモリの確保量やコピー操作の負荷も比例して高くなるからと考えればよさそう。

ここでは、8個分の要素を増やすので、1個×8回分の配列のサイズを増やす操作が発生するのと同じ。

コピー操作についても結局要素8個分の負荷がかかる。

要素数1,2,4,8,16,32,64,128,...xと増えていくにつれて結局元の要素のx回配列サイズ増加の負荷がかかり、要素のコピペもx回かかると考えればいいのかも。

なので、x回+x回=2x回, つまりx個の要素を挿入するにはO(2x)の計算時間がかかる。

要素を挿入していって、最終的に要素数x=8で1,2,4,8までサイズ確保とコピー操作を行うという具体例で考えてみると、

x=8に対して1+2+4+8=17 ≒ ２x

x=8なので、２xが意味するのは、8個の要素を挿入するのに（8回分のサイズ確保）＋（8回分のコピー操作）＝２xなので、約O(２x)の時間がかかることが計算からも分かる。

上記から一般化すると、x個の要素の挿入にはO(2x)の時間がかかって、挿入ごとの償却計算量(要素を1個挿入する計算量)はO(1)となる。

配列がいっぱいになって倍に増やす操作が発生する頻度は低いけどそれも考慮することが償却計算。

Log N 実行時間 | O(log N)

2分探索を行う例で考えてみる。
昇順ソート済みの要素数がNの配列で考えてみる。
N個の配列から一つの要素xを探すとする。

2分探索なので、配列の要素を2つに分ける。

真ん中の要素とxを比較し、xの方が大きい時は真ん中より右の要素に分割する。
次に、分割した要素の真ん中の要素とxを比較する。
…以降、xになるまで、または要素数が1になるまで(=xの要素)分割と比較を繰り返す。

→要素数Nの配列が、毎回半分になる。

1回目：N個
2回目：N/2個
3回目：N/4個
……

→
N = 16
N = 8  // 2で割る
N = 4  // 2で割る
N = 2  // 2で割る
N = 1  // 2で割る

逆にみると、２を毎回かけていることになる。

２を何回かけると16になるかを考える。

2を4回かけると16になる。

この4回のステップを実行することが、totalの実行時間になる。

2 x 2 x 2 x 2 = 2^4 , 2^4 = 16

→

2^k = N となるkを求める。何回２をかけたかを表すステップ数がkだから。

上記のkを求めるときに使うのが対数。

2^4 = 16 
log2 16 = 4
log2 N = k より、左辺と右辺を分かりやすく入れ替えて k = log2 N
ステップ数は、log2 N回。

以上から、2分探索のように、要素数が毎回半分になっていくようなプログラム実行には、実行時間はO(log N)かかる。なぜ基数を無視するのかは↓。

対数の基数を無視する理由

ビッグオー記法では対数の基数を無視する。
基数が異なる対数は、定数倍の差でしかないため。
ビッグオー記法では定数は切り捨てるのが理由。

上の図の左辺は基数が10、右辺は基数2。左右がイコール。基数2の対数に掛け算したものが基数10になるので、基数変換では数字を掛け算しているのと同じ。なので、ビッグオー記法では無視する。と解釈。間違ってる可能性もあり。。

再帰の実行時間

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

f(4)を呼び出した場合、f(3)は2回呼び出される。f(3)からf(2)が2回呼び出される。f(2)からf(1)が2回呼び出される。

上記のような再帰的な関数を実行したらどのような実行時間になるのかをgoodnoteにまとめたので、下図を参照。

訂正：上の図の深さの書き方を間違っていた。深さは2^0の0から始まるので深さは0、1、2、3となる。

ノードの数＝呼ばれる関数の回数となる。

枝が2で深さがnの時、ノードの数は2の0乗〜2のn乗までの和に等しい。これは、2の0乗から2のn+1乗までそれぞれの項を足して、１を引いた値となる。

(2^n+1)-1

上の図のノードは15個。枝の数は2、nは3なので、このケースを上の計算式に当てはめると、(2^3+1) - 1 = 2^4 - 1 = 16 - 1 = 15

基数の差を無視できない。指数における基数は。指数では、基数が違うと全然違う値となり、対数の基数とは違ってただの定数倍と言えないくらい違ってくるため。

基数が2、指数が3だと2^3=8
基数が3、指数が3だと3^3=27といった感じで全然違う値になってくるので指数の場合は基数を無視しないようにする。

この関数での空間計算量(メモリ確保量)は、O(N)となる。

合計ではO(2^N)のノードができるけど、関数の呼び出し一度に発生するノードは最大でO(N)しかないため。

実例のコードで実行時間がどのくらいになるのか確認

for文が多重ループになっていない場合は、実行時間はO(N)で、2重ループの場合は実行時間はO(N^2)。あくまで下記のコードを読み解いたらそうなるというだけなので、2重ループだからこうなるみたいに固定的に覚えようとするのは危険。

void printUnorderedPaires(int[] array) {
    for (int i = 0; i < array.length; i++) {
       for (int j = i + 1; j < array.length; j++) {
            System.out.println(array[i] + “,” + array[j]);
       }
    }
}

上記コードの二重ループでは、外側のループ1回目に対し内側のループはN-1回実行され、内側のループ2回目に対し内側のループはN-2回実行されるという形になっている。

そのため、この二重ループが実行される合計回数は、

(N-1) + (N-2) + (N - 3) + … + 2 + 1
= 1 + 2 + … + (N - 1)
つまり、1からN-1までの連続する整数の和の合計になっている。

上記の整数の和の合計はN(N-1)/2で計算できる。

N*(N-1)=N^2-Nで、割り算の分母の2はN(N-1)*1/2と書けるので、定数倍として省略できる。N^2-NのNも省略できるので、

ビッグＯ記法で実行時間はO(N^2)となる。
これは、繰り返しの回数に着目して実行時間を計算していることになる。

ループの平均回数という、上記と違う視点でみることもできる。個の視点だと、
外側のループは固定回数なのでN回。外側の各々のループに対して内側のループの回数は変化する。具体的には、外側のループの回数が増していくほど、内側で実行されるループの回数は段々減っていく。

外側のループ1回目に対しては内側のループは10回行ったけど、
外側のループ10回目に対しては内側のループは1回みたいなイメージ。
そうすると、結局内側のループは何回実行したのかというとき、使えるのが平均値という考え方。

1〜10までの平均値は5なので、外側のループ10回の各々に対して、平均すると5回内側のループを実行したと考えることができる。

同じように考えて、内側のループ1〜N回までの平均値はN/2回となる。

なので、外側のループN回 x 内側のループN/2回 

= N^2/2 = N^2*(1/2) = O(N^2) が実行時間と計算される。

2つの異なる配列がある場合

void printUnorderdPaires(int[] array A, int[] array B){
          for(int i = 0; i < arrayA.length; i++){
               for(int j = 0; i < arrayB.length; j++){
                    if(arrayA[i] < arrayB[j]){
                        System.out.println(arrayA[i] + “,” + arrayB[j]);
                    }
               }
          }
}

if文の中身の実行時間はN数に関係なく、常に一定の定数時間なので、O(1)となる。

ループの回数については、異なる配列が2個なので、配列が一個の時と実行時間が違ってくることに注意が必要。配列が1個の時の二重ループの回数の合計は自然数の和となるので、O(N^2)となるけど、

異なる配列の場合、違ってくる。
例）
配列A = {1, 2, 3, 4, 5}
配列B = {6, 7 8}
Aが外側のループ、Bが内側のループとすると、
A = 1の時、Bループは6, 7, 8の3回
A = 2の時、Bループは6, 7, 8の3回
・‥・
A = 5の時、Bループは6, 7, 8の3回
となり、ループの合計回数は5x3=15回
配列Aのループ回数をa、配列Bのループ回数をbとおくと、
上記から、ループの合計回数はa*bとなる。
よって、ループの実行時間はO(ab) となる。

各文字列をソートし、その後配列全体をソートするアルゴリズムの実行時間

・一番長い文字列の長さをsとする
・配列の長さをaとする

{"aaa", "ba", "edc", "fghijklmn"}のような配列の場合、

sは10、aは4となる。

文字列をソートする実行時間： O(n log n)を前提にしている。

ソートのアルゴリズムに何を選択するかによって実行時間が全然違ってくるので、ここではクイックソートの実行時間を前提にしている。

要素が8個の場合は、8 = 2^3

要素を半分ずつ分割してソートしていくと3回の分割でソートが完了する。8 = 2^3を対数で表すと、

log2 8 = 3　

となる。

ステップ数3回=log2 8であるから、ステップ数はlog2 8であることを表してる。つまりこれが計算時間。

要素数8個のソートを行うためにlog2 8の計算時間がかかるということ。なので、一般化すると、n個のソートを行う計算時間は

log2 nということになる。これをビッグＯで表すとO(log n)となる。

この各々のステップ毎に、分割した要素を比較する操作が要素の個数分必要になってくる。要素の個数はnなので、

（分割後に行う要素の比較n回） x （ステップ数）

クイックソートの計算時間になる。

よって、計算時間はO(n * log n)となる。

→分割毎に要素n個分の比較が必要ということが分からなかったので、なかなか理解できなかったけど、以上でなんとかO(n * log n)の根拠がざっくり理解できた感じ。

ここまでで、配列の要素を並び替える計算時間がわかった。

次は、個々の要素の文字列をソートする計算時間を考える。

全体でa個の文字列（要素）をソートするので、すべての要素の文字列をソートする実行時間はO(a*s log s)

acb, fdeg,...すべての各文字列をabc, defg...などと並び替える時間

a個の文字列をソートする実行時間は、O(a log a)

一つの要素の中の文字に対してもクイックソートを適用するので、

O(a log a)となる。例えば、一つの要素13254を12345に並び替えるのにクイックソートを適用するイメージ。

a個の文字列をソートする際の文字列比較の実行時間は１要素あたりO(s)

よって、a個の文字列をソートする実行時間O(s*a log a)

このアルゴリズムの全体としての実行時間は、

O(a*s log s)+O(s*a log a)の足し算となる。

各要素の文字列のソートは、配列の要素のソート実施→要素の文字列のソート

のように独立して分けて行われるので、掛け算にはならないことに注意。

O(a*s log s)+O(s*a log a) = O(a*s(log s) + a*s(log a))

整理すると、O(a*s(log s + log a)) これがソートの計算時間になる。

続きはまたア]ップデートします。