big-o - アルゴリズムの目的のための対数の底は何ですか?

Question

時間の複雑さを O(log(N)) と考える場合、対数の底は何ですか?

Answer 1

すべての対数は、何らかの定数によって関連付けられています。(したがって、基数変換式)。通常、複雑さの分析では定数を無視するため、基数は重要ではありません。

通常、アルゴリズムを導出するとき、基数は 2 と見なされます。merge sortのようなソートを考えてみましょう。そこからツリーを作成できlog₂ nます。各ノードには 2 つのブランチがあるため、ツリーの高さはです。

Answer 2

使用するベースに関係なく、相対的な複雑さは同じです。

Answer 3

それを考える 1 つの方法は、O(log ₂ X) = O(log ₁₀ X) = O(log _N X)です。