ランダウの記号(計算量について)

landau.png

計算時間の見積り方

  • 一番実行される部分を探して、その大体の計算時間を調べる。

たとえば、

(1)
\begin{equation} O(nm) \end{equation}

は、計算時間が大体nmに比例しますよという意味で使う。
厳密に言うと、

  • 上からの漸近的な上階をわかりやすい関数で表すのに使う記号

となる。
もっとテキトーにいうと、

  • 最悪でもn×m回くらいの計算しかしないで大丈夫

くらいの意味にとらえておけばok

無視出来るもの

  • 定数の係数
  • 変数が十分に大きくなったら無視出来る項

たとえば、

(2)
\begin{equation} O(4n^2+3n5) \end{equation}

(3)
\begin{equation} O(n^2) \end{equation}

にしてもよい。
なぜ無視出来るか?
ランダウの記号は、nが増えた時に、どれくらいの勢いで計算時間が増えていくかという点に主眼をおいているから。
ただし、係数などは計算時間に影響しないわけではない。
ある行の実行回数が
$10^8$回あったら、2秒の制限を超えてアウトになるらしい。

2分探索の場合

(4)
\begin{equation} a=log_{2}N \end{equation}
N
最初の入力値
a
最終的な計算回数

なぜそうなるのか?

(5)
\begin{align} 1=N\frac{1}{2}^a \end{align}

1つの答えが出るまで$\frac{1}{2}$ずつ絞っていくのが2分探索。
この式を変形するとこうなる。

(6)
\begin{align} 2^a=N\\ a=log_{2}N \end{align}

なので

(7)
\begin{equation} O(logN) \end{equation}

計算機の世界ではlogの底は2がデフォルト。

計算量の予測の難しいもの

  • 計算量に平方根が含まれる(たとえば、ループを抜ける条件がi*iである、素数判定等)
  • logが含まれる。(例、bitがいくつ立ってるか調べる。)
  • 再起処理のからむもの。$O(2^n)$と考えておけばいい。正確には$O((\frac{1+\sqrt(5)}{2})^n+1)$

サポートサイト Wikidot.com