2018-04-22 12:42:55
概要アルゴリズムの演算性能をざっくりと計算するO記法と計算量の求め方についてまとめる。
計算量（オーダー）とは
アルゴリズムの演算性能をデータ量の増加に対し、実行時間がどれくらい増加するかの割合で表した指標。
時間計算量
処理時間
空間計算量
メモリ使用量
O（オーダー）記法
O記法
計算理論における名称
概要
O(₁)
定数時間
データ量が増加しても処理時間が増加しない
O(log n)
対数時間
データ量が増えても計算時間がほとんど増えない
O(n)
線形時間
データ量が増加した分だけ処理時間が増える
O(n log n)
準線形、線形対数時間
O(n...
アルゴリズムとデータ構造
O記法
Algorithm