ビッグなオー
2008/03/22
計算量
正直、計算量なんてまともに考えたことがなかったです...Orz....
まず、O記法なるものを使用して表現します。
ビッグオーとかオー記法といったりするようです。
で、調べはじめると、きりがなさそうなので、大雑把な理解ぐらいでいいのかなと...
コードを書くうえで、なんとなくイメージできるレベルで。
順番は、
O（log n）＜O（n）＜O（n log n）＜O（nk）＜O（kn）＜O（n!）
あと、O（nk）以下のものを、多項式時間でとけるもの。O（kn）以上でとけるものらしくて、指数関数時間は、実用的ではないらしい。
自分なりにまとめてみたかったけど、よくわからないので、こつこつこつこつ考えていこう。
参考
「計算量のオーダ」の説明については、Short Coding ~職人達の技法~がよかったです。
: