計算量とランダウ表記について
概要
- 計算量を示す記号
- 線形ならば
O(n)
有名なアルゴリズムとbig-O
- アルゴリズム
- 定数
O(1)
- 二分探索
O(log n)
- ヒープソート
O(n log n)
- 挿入ソート
O(n^2)
- 巡回セールスマンの厳密解
O(2^n)
- 2つの理論式の同型判定
O(n!)
- 定数
計算量の視覚的見積もり
- colabなどでmatplotなどでplotして確認できる
log n
の計算量削減効果は凄まじいことが確認できる
厳密な定義
f(x) <= g(x)
が成り立つとき,f(x) = O(g(x))
である- つまり、現実のコンピュータのオーバーヘッドを考慮すると増加速度が記号より少し遅いぐらいが実際のプログラムの実装になる