Post

O記法

2018-04-22 12:42:55

O(オーダー)記法とアルゴリズムの計算量の求め方

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

プログラミング

O記法 アルゴリズム