ドキュメント
Computer Science
アルゴリズム
基礎理論
Asymptotic Analysis

Asymptotic Analysis

漸近(ぜんきん) 解析(かいせき) - アルゴリズムの時間(じかん) と空間(くうかん) 計算量(けいさんりょう) の分析(ぶんせき)

良いコードとは

  • Readable（可読性(かどくせい) ）
  • Scalable（スケーラブル）の測定(そくてい) は:
    1. 空間計算量(くうかんけいさんりょう) (Space Complexity)：アルゴリズム実行(じっこう) に必要(ひつよう) なメモリ空間(くうかん)
    2. 時間計算量(じかんけいさんりょう) (Time Complexity)：アルゴリズム実行(じっこう) に必要(ひつよう) な時間(じかん)

Big O は異(こと) なるアルゴリズムの時間計算量(じかんけいさんりょう) を測定(そくてい) するために使用(しよう) され、 処理(しょり) するデータ量(りょう) が増加(ぞうか) するにつれて、プログラム実行時間(じっこうじかん) が増加(ぞうか) する割合(わりあい)

Asymptotic Notation

  • 漸近(ぜんきん) 記法(きほう)
  • 分析結果(ぶんせきけっか) は最悪(さいあく) ケース、最良(さいりょう) ケース、平均(へいきん) ケースなどに分類(ぶんるい) できる
    • Big-O ( Ο )：アルゴリズム時間関数(じかんかんすう) の上限(じょうげん) (Upper bound)、つまり最悪(さいあく) の場合(ばあい) の実行回数(じっこうかいすう)
    • Omega ( Ω )：アルゴリズム時間関数(じかんかんすう) の下限(かげん) (Lower bound)
    • Theta ( θ )：アルゴリズム時間関数(じかんかんすう) の上限(じょうげん) と下限(かげん) の間(あいだ)

Time of Complexity

  • 時間計算量(じかんけいさんりょう)
ComplexityNameDesc.
O(1)Constant配列(はいれつ) の特定要素(とくていようそ) へのアクセス
O(N)Linear配列要素(はいれつようそ) のループ処理(しょり)
O(log N)Logarithmic配列要素(はいれつようそ) の検索(けんさく)
O(N²)Quadratic配列(はいれつ) の各(かく) インデックスを2回(かい) 参照(さんしょう)
O(2^N)Exponentialフィボナッチでの二重再帰(にじゅうさいき)

Big-O Complexity Chart

O(1)

  • 定数(ていすう) 時間(じかん)
    • 配列(はいれつ) 要素(ようそ) へのランダムアクセス
    • 連結(れんけつ) リストの先頭(せんとう) への挿入(そうにゅう)
  • 配列読(はいれつよ) み取(と) り
  • ループがなく、実行時間(じっこうじかん) は入力(にゅうりょく) データ量(りょう) の増加(ぞうか) に影響(えいきょう) されない

O(log n)

  • 対数(たいすう) 時間(じかん)
  • Binary Search（二分探索(にぶんたんさく) ）
    • ソート済(ず) みの配列(はいれつ) で目標値(もくひょうち) の位置(いち) を見(み) つける探索(たんさく) アルゴリズム
    • 各(かく) ステップで配列(はいれつ) の半分(はんぶん) が除外(じょがい) される

O(n)

  • 線形探索(せんけいたんさく) : コレクションの要素(ようそ) を1つずつ反復処理(はんぷくしょり)
    • 配列要素(はいれつようそ) のループ処理(しょり)
    • 連結(れんけつ) リストの探索(たんさく)

O(n log n)

  • 準線形(じゅんせんけい) 時間(じかん)
    • Quick Sort
    • Merge Sort : マージソート(まーじそーと)
    • Heap Sort
  • 通常(つうじょう) 、ソート操作(そうさ) で使用(しよう) される

O(n²)

  • 二乗(にじょう) 時間(じかん)
    • Insertion Sort : 挿入(そうにゅう) ソート
    • Selection Sort : 選択(せんたく) ソート
    • Bubble Sort

O(2^n)

  • 指数(しすう) 時間(じかん)
  • 通常(つうじょう) 、再帰(さいき) アルゴリズムで発生(はっせい)
  • 例(れい) : フィボナッチ数列(すうれつ)

O(N!)

  • 階乗(かいじょう) 時間(じかん)
  • 巡回(じゅんかい) セールスマン問題(もんだい)

Space of Complexity

  • 空間計算量(くうかんけいさんりょう)
  • サイズ n の配列(はいれつ)
a=[a0,a1,…,an] a = [a_{0},a_{1},\dots,a_{n}]
  • 行列(ぎょうれつ) = サイズ n * n の配列(はいれつ)

定数を除去 - 最も影響を与える項目を残す

Drop Constant

O(2N)→O(N) O(2N) \rightarrow O(N)

Drop Non Dominant Terms

O(N2+N)→O(N2)O(N+log⁡N)→O(N)O(2⋅2N+1000N100)→O(2N) \begin{aligned} O(N^2 + N) &\rightarrow O(N^2) \\ O(N + \log N) &\rightarrow O(N) \\ O(2 \cdot 2^N + 1000N^{100}) &\rightarrow O(2^N) \end{aligned}

Runtime の増加、乗算

Runtime Multiply and Plus

Big-Oを使用した時間計算量の測定

Calculate Big O

再帰アルゴリズムの時間計算量計算

Calculate Recursion Big O

Calculate Recursion Big O 2

Calculate Recursion Big O 3

Cheat Sheet