O(log N)の底は何なのか

1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...

アルゴリズムの計算量を評価するときに、O記法がよく用いられます。
O(log N)は、Nが十分に大きければ、その関数はlog Nに比例するということを意味します。

ところで、このlogの底は何なんでしょうか?

答え

気にしなくても良い。

対数の底の変換公式を使うと、以下のように変形できるので、底については気にしなくても良いです。

\begin{align}
\log _a b &= \frac{1}{\log a} \times \log b \\
&= O(\log b)
\end{align}


1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...
      この投稿は審査処理中  | 元のサイトへ