計算量とランダウ表記

概要

• 計算量を示す記号
• 線形ならばO(n)

有名なアルゴリズムとbig-O

• アルゴリズム
  • 定数
    • O(1)
  • 二分探索
    • O(log n)
  • ヒープソート
    • O(n log n)
  • 挿入ソート
    • O(n^2)
  • 巡回セールスマンの厳密解
    • O(2^n)
  • ２つの理論式の同型判定
    • O(n!)

計算量の視覚的見積もり

• colabなどでmatplotなどでplotして確認できる
  • colab
• log nの計算量削減効果は凄まじいことが確認できる

厳密な定義

• f(x) <= g(x)が成り立つとき,f(x) = O(g(x))である
  • つまり、現実のコンピュータのオーバーヘッドを考慮すると増加速度が記号より少し遅いぐらいが実際のプログラムの実装になる