Big O notation の計算原理について調べてみた - 医学生わくばの欲張り技術ブログ

　どうも、わくばです！

　アルゴリズムをいくつか勉強しているうちにBig O notationに関してだいぶ適当だったと感じてのでちゃんと調べてみました。が、結局わりと適当でオッケーみたいですね笑

　MITのサイトや各種プログラミング学習サイトから引用しながら地味&&ラフに説明させていただきます。

　まず気になっていたのが、\(\Theta()\)とか\(\Omega()\)とかの記号です。\(O()\)しか見聞きしたことなかったので一旦調べてみました。

　freeCodeCampの記事では以下のようにありました。

Big O: “f(n) is O(g(n))” iff for some constants c and N₀, f(N) ≤ cg(N) for all N > N₀
Omega: “f(n) is Ω(g(n))” iff for some constants c and N₀, f(N) ≥ cg(N) for all N > N₀
Theta: “f(n) is Θ(g(n))” iff f(n) is O(g(n)) and f(n) is Ω(g(n))
Little O: “f(n) is o(g(n))” iff f(n) is O(g(n)) and f(n) is not Θ(g(n))

ラフに解釈すると\(O(n)\)は上界、\(\Omega(n)\)は下界、\(\Theta(n)\)はジャスト、\(o(n)\)は\(O(n)\)よりもっと上に吹っ飛んでる感じですかね。なんとなくわかります笑

　数式の表現もあったのでこちらも紹介します。

f:id:PYEcracker99:20210120071306p:plain — ・Complexityの数式による定義

　個人的にこっちの方がわかりやすいと感じました。特に\(o(n)\)や\(\Theta(n)\)とかはこちらのほうが明解ですよね。\(o(n)\)は0に収束させ、\(\Theta(n)\)は実数値に収束する(無限のスケールで等価)。

　対して\(O(n)\)は発散さえしなければ良いというわけですから、結構雑です。結局極限の話なので雑でいいわけですが(数学屋に怒られそう)。

　ただ、あんまり厳密な使い方をされることは少ないようで、\(O(n)\)という表現は多くの場合\(\Theta(n)\)を意味したいたりするようです。

　僕の記事ではもう\(O(n)\)だけでいいかなと思っています。

　計算の仕方

　Big O notationなどは時間計算量と表現されることもありますが、定義からもわかる通り計算値と言うよりあくまで定性的な概念であって「カテゴリー」という解釈が適切です。したがって計算の仕方といっても型があり、コード1行1行の型を考えればBig O notationはわかるようになっています。

　型は調べた限り6つくらいでした。一つ一つ説明していきます。

・Sequence of statement

　　Statementというのは要するにコード1行のことです。JavaScriptだとセミコロンやブロック単位ですかね。これらの合計が定数なら\(O(1)\)(constantと呼ぶ)に該当し、無限スケールではほぼ無視できます

・If - Then - Else

　これらがあるとプログラムの分岐が生じるので、Worst-caseを考えるのであれば、分岐で生じるパスのうち、より長い方を採用することになります。

・Loop

　ループの中に例えば5つStatementがあるとするとそれがn回ループするので5nの計算量になります。これは単に直線的に増加しているのであって、その点だけわかれば良いので定数係数の5は省いて\(O(n)\)と表現します。ちなみにアルゴリズムの数学的な議論ではwhileループはforループとして考えるそうです。

・Nested loops

　Complexityに一番大きな影響を持つ構造です。パターンとしては内側のループが外側のループに依存しないタイプと、依存するタイプがあります。

　2つのループが依存しない場合例えば外側がN回、内側がM回とすると合計\(O(N*M)\)の計算量になります。NやMはarrayの長さなどに依存することが多いので、これは無限のスケールで考えるとおおよそ\(O(n^2)\)にカテゴライズできます

　2つのループが依存する場合は以前投稿したInsertion Sortがわかりやすいので添付します。

function selectionSort(array, size){
    const { length } = array;
    for (let i=0; i< length; i++){
        let minIdx = i;
        for(let j =i+1; j < length; j++){
            if(array[i]>array[j]){
                minIdx = j;
            }
        }
        [array[i], array[minIdx]] = [array[minIdx], array[i]];
    }
    return array;
}