[解決済み] ビッグはO(logn)log base eか？

質問

バイナリサーチツリー型のデータ構造について、ビッグオー表記は通常O(logn)と表記されていますね。 log の小文字の 'l' で、これは自然対数によって記述される対数底 e (n) を意味するのでしょうか? 単純な質問で申し訳ありませんが、私はいつも異なる暗黙の対数を区別するのに苦労しています。

どのように解決するのですか？

big-O()記法で表現すれば、どちらも正しいです。 しかし 導出 の場合、O()多項式を導出する際に 二項 検索では、ログ ₂ が正しいです。 この区別が、そもそものご質問の直感的なひらめきだったのだと思います。

また、個人的な意見として、O(log ₂ N)と書く方が、アルゴリズムの実行時間の導出をよりよく伝えることができるので、あなたの例には適していると思います。

big-O()記法では、定数係数は削除されます。 ある対数基底から別の基底への変換は、定数因子の乗算を伴います。

つまり、O(log N)はO(log)と同等です。 ₂ N)の定数要因によるものです。

しかし、簡単にタイプセットできるのであれば、ログ ₂ Nと簡単に書けるなら、そうする方が教育的です。二分木探索の場合、logは正しく ₂ N は big-O() ランタイムの導出時に導入されます。

結果をbig-O()表記で表現する前に、この違いが非常に重要です。 big-O記法で伝えるべき多項式を導出する際、この例ではlog以外の対数を使うのは不正確です。 ₂ N以外の対数を使用することは、O()表記を適用する前に、この例では正しくありません。多項式が big-O() 記法で最悪の場合の実行時間を伝えるために使用されるとすぐに、どの対数が使用されるかは問題ではありません。