Big-O記法
big-O notation
$ f(x)=O(g(x))と書いた時、$ g(x)が$ f(x)の上界であることを表す 例
$ f_1(n)=5n^3+2n^2+22n+6=O(n^3)
「=」じゃないよなmrsekut.icon
なにか良い繋ぐ記法ないかな
普通に$ \toでいいのかな
$ f_1(n)=5n^3+2n^2+22n+6\to O(n^3)
定義
2つの関数$ f,g: \mathbb{N}\rightarrow\mathbb{R}^+に対し、すべての整数$ n\ge n_0に対して、正整数$ cと$ n_0が存在して、$ f(n)\le cg(n)であるならば、$ f(n)=O(g(n))
$ n_0は$ \exist n_0\in \mathbb{N}
$ \mathbb{R}^+は0より大きい実数の集合
この条件で、$ g(n)は$ f(n)の漸近的上界という
雑に言うと、$ f_1(n)=5n^3+2n^2+22n+6に対して
$ O(n^4)や$ O(n^5)は上界になるが、$ O(n^2)はそうはならない
もうちょいちゃんと書くなら
$ c=6,n_0=10とすれば、どんな$ n\ge10に対しても、$ g(n)=6n^3は$ f(n)以上になる
polynomial bound
exponential bound
参考