アルゴリズムの計算量について

1年ちょい前に基本的なソートと探索は研修で実装したんだけど(written in Perl)
その頃はなんだか分からないまま実装してた感あったので計算量もちゃんと意識やってみる
それにあたって計算量の基本の確認

計算量の評価

計算量の評価は時間計算量と領域計算量の2つから成る

  • 時間計算量
    • プログラムの実行に必要な時間の評価
      • CPUをどれだけ使うか
  • 領域計算量
    • プログラムの実行に必要な記憶領域の評価
      • メモリをどれだけ使うか

時間計算量が問題になることが多いので、計算量といわれるとき大抵は時間計算量

O表記法

  • オーダ表記法
  • O(n)やO(n²)のように表記する
  • nを入力値とし、nを用いた()内の式に計算量が比例することを表す
    • 例1) O(n)の場合
      • 入力値nが5倍になれば計算量も5倍になる
    • 例2) O(n²)の場合
      • 入力値nが5倍になれば計算量は(5²=)25倍になる

参考