計算量 - ぼく用あれこれまとめ

計算量

• このwikiを編集してる人は頭がくるくるパーなのでこのページは参考になりません。

ランダウのO-記法

 int n;
 for(n回ループ){
   for(n回ループ){
     for(n回ループ){
       ;
     }
   }
 }

• 上の場合、実行時間は「nの3乗」に比例する。（ほんとに比例するかどうかは知りません。ごペンなさい。）
• このとき、実行時間を「O(n^3)」時間と書く。
  • この書き方をランダウのO-記法っていうらしい。

参考文献

• プログラミングコンテストチャレンジブック（秋葉 拓哉 (著), 岩田 陽一 (著), 北川 宜稔 (著) ）
• http://www.triplefalcon.com/Lexicon/Notation-BigO-1.htm
  • ぱっと見てとてもわかりやすかったので載せておきます。ぜひ参考に。