O記法

CourseraのAlgorithms: Design and Analysis, Part 1の復習。別に毎週書くつもりはないんだけどこの記法しょっちゅう使うくせに厳密な定義を知らなかったので(入力nに対する計算量くらいしか知らなかった)、ちょっとメモ。

形式的な定義： T(n) = O(f(n)) iff there exists constants c*n₀ > 0 such that T(n) ≦ c*f(n) for all c ≧ n₀
ここで問題になるのがc*n₀の存在で(実際これにはまった)、具体的には以下のような点n₀を指す。

ここはc = 2となりT(n)と2f(n)が交差する点がn₀となる。っでO(n)が適用されるのはn₀以降になるのが味噌。逆に言うと、n
< n₀まではT(n) = O(f(n))ではないということになる。
上記ではまったと書いたのだけど、これではまるのは例えば実際に計算量の増加率が高い順に並べるとかいうのをやった際に、nがかなり巨大にならないと反転しない場合(n₀=10^13とか)。

ここからは適当な感想というか、考察というかになるんだけど、例えばO(2^(2^log(n)))なアルゴリズムとO(n^2 * log(n))なアルゴリズムがあった場合(底は10とするw)、nが10^5までは前者で10^6からは(もう少し前からだが)は後者のアルゴリズムを使う必要があるということになる。定義的には前者の方が計算量が少ないことになるんだけど、現実的にはねぇっていう話。

ついでにアルゴリズム的には計算量少なくても使用する空間が大きいと実装した際には速度出ないということはまぁ言わずもがなだわね。divide and conquerって使用する空間のこと考えないと涙出るし。こういうの書くと自分は以下に計算機科学の基礎(とか理論)ができてないのかがわかって凹むが、まぁ凹んだ部分は今からでも埋めればいいかと開き直ることにする。