algorithm - 対数の複素数分析

Question

f(n)=log ₂ n と g(n)=log ₁₀ n の 2 つの関数があります。f(n) が O(g(n)) か、Ω(g(n)) か Θ(g(n)) かを判断しようとしています。n が無限大になるので、制限 f(n)/g(n) を取るべきだと思います。また、制限は一定なので、f(n) は Θ(n) でなければならないと思います。

私は正しいですか？

Answer 1

log ₂ n = log ₁₀ n / log ₁₀ 2 (ここから)

したがって、f(n) = g(n) / log ₁₀ 2

そのため、f(n) と g(n) は一定の係数だけ異なります (log ₁₀ 2 は一定であるため)。

したがって、O(x)、Ω(x)、および Θ(x) の定義から、次のように言えます。

f(n) ∈ O(g(n)),
f(n) ∈ Ω(g(n)),
f(n) ∈ Θ(g(n))

Answer 2

はい、あなたは正しいです。複雑さの観点から (少なくとも大きな O の観点から)、それが log ₂か log ₁₀かは問題ではありません。

f(n) は O(g(n)) であり、f(n) は Ω(g(n)) であり、f(n) は Θ(g(n)) です。

Answer 3

制限は一定であるため、f(n) ∈ Θ(g(n)) は正しいです (質問にタイプミスがあると仮定します)。もちろん g(n) ∈ Θ(f(n)) です。

ところで: 比率の限界が一定であるだけでなく、log ₂ n/log ₁₀ n は常に定数 (log ₂ 10) です。