どうもみなさんこんにちは！最近お外が寒すぎて、外に出ると必ず耳と頭が痛くなるフジワラです。
今回は、テスト勉強と、オーダ記法が分からないよぉ～ ふぇぇ～な友達のためにわかりやすくオーダ記法を開設したいと思います。（ふぇぇ～言うやつは大体オタク
主に、数学ではなく情報工学の内容です。
- オーダ記法ってそもそも何？
- オーダ記法活用の場所
- オーダ記法の具体的な書きかた
- オーダ記法の練習問題
注意：間違ってるかもしれませんので鵜呑みにしないでください責任は取りかねますm(_)m
オーダ記法ってそもそも何？
今回は、無限大での場合だけで考えます。
オーダ記法というのは、計算量などの上下界を評価するときにつかいます。
これだけだとよくわからないと思うので、イメージとしては、nこの処理をするのに、n+100時間、かかるプログラムがあるとすると、ｎが∞個の処理をしようとしたときにかかる時間はだいたい、n時間、処理に時間がかかるっていうことです。(数学の極限です。nが無限大になったときは、100を無視しても構わないというやつです。)
この、「n+100時間かかる処理は、n時間で近似して評価できる」というのが、オーダ記法です。
オーダ記法活用の場所
主に、情報工学の分野でアルゴリズムの計算量を評価するときに使います。
特に、アルゴリズムでは、時間計算量と領域計算量があって、最近はパソコンの性能がものすごく上がったので、領域計算量よりも時間計算量のほうが圧倒的に重視されています。
オーダ記法の具体的な書きかた
まず、オーダ記法には3種類の数式があります。
- \(T(n)=O(f(n))\)
- \(T(n)=\Omega(f(n))\)
- \(T(n)=\Theta(f(n))\)
1.\(T(n)=O(f(n))\)の意味
\(O(f(n))\)の読み方は、「オーダf(n)」です。
では、
\(T(n)=O(f(n))\)の意味は\(T(n)\)の発散の速度はだいたい\(f(n)\)と同じくらいという意味です。例:\(n^5+n+8=O(n^5+n)\)といった感じ。
詳しくは
\(T(n)=O(f(n))\Leftrightarrow \exists n_0 , c(>0) , s.t. \forall n \geq n_0 , T(n) \leq cf(n)\)
です。
2.\(T(n)=\Omega(f(n))\)
\(\Omega(f(n))\)の読み方は、「オメガf(n)」です。
\(T(n)=\Omega(f(n))\)の意味は\(T(n)\)の発散の速度はだいたい\(f(n)\)と同じくらいという意味です。例:\(n^5+n+8=\Omega(n^5)\),\(n^5+8=\Omega(n^4)\)といった感じ。
詳しくは、\(T(n)=O(f(n))\Leftrightarrow \exists n_0 , c(>0) , s.t. \forall n \geq n_0 , cf(n) \leq T(n) \)
3.\(T(n)=\Theta(f(n))\)
\(\Theta(f(n))\)の読み方は、「シータf(n)」です。
\(T(n)=\Theta(f(n))\)の意味はT(n)の発散速度はだいたいf(n)と同じくらいという意味です。
詳しくは、\(T(n)=￥Theta(f(n))\Leftrightarrow T(n)=O(f(n)) かつ T(n)=\Omega(f(n)) \) です。
時間計算量でよく出てくる関数
上記の、オーダ、オメガ、シータと、\(n, n^2, n^3, n\log n, \sqrt{n}, \log{2}n\)などがよく時間計算量を評価するときに使われます。
一般的に、現代のPCは性能が昔の何千何万倍と違うので、領域量はほとんど気にされません。
圧倒的に、時間計算量が重視されます!!
どんなアルゴリズムがいいとされるの?
ざっくりまとめると\(O(n^k)\) (kは定数)の形で表されるものがいいです。
\(O(k^n)\)のように(kは定数)指数関数的に増えていくアルゴリズムはよろしくありません。
次回は、基本的なデータ構造についてまとめます。