2018-04-22 12:42:55
概要アルゴリズムの演算性能をざっくりと計算するO記法と計算量の求め方についての前提知識をまとめる。
計算量(オーダー)とは
アルゴリズムの演算性能をデータ量の増加に対し、実行時間がどれくらい増加するかの割合で表した指標。
時間計算量
処理時間
空間計算量
メモリ使用量
Big O/Big θ/Big Ωそれぞれ計算時間を記述するものだが、学術的な意味の違いについてまとめる。
Big O
計算時間の上限
Big θ
計算時間の下限
Big Ω
OとΩの両方
最善/最悪/期待ケースアルゴリズムの実行時間を表す3パターンについてまとめる。
最善(best)ケース
計算...
アルゴリズムとデータ構造
O記法