2つの変数を持つBig-O表記

Question

にサイズmとnのプログラムを書き込んだのは、それぞれO(log(m + n))の時間の複雑さです。

私はO(log(m) + log(n))の解決策を考え出すことができます。それは上記の時間要件を満たしていますか？

私はので、それは肯定的だと思う。別の言い方をすれば

log(m) + log(n) = log(m*n) <= log((m+n)^2) = 2*log(m+n) = O(log(m+n))

、k = 2とm0 = n0 = 1が存在します。 m > m0 and n > n0の場合、log(m*n) <= k*log(m + n)があります。

欠陥がありますか、それとも正しいですか？ a一定の与えられたより一般的に

、我々は同じ理由でlog(n^a) = O(log(n))は言うことができますか？

---

Davidの回答に感謝します。 これは、ウィキペディアにBig-O notationで言及されています

"We may ignore any powers of n inside of the logarithms. The set O(log n) is exactly the same as O(log(n^c))."

Answer 1

はい、あなたはすべてのカウントで正しいです。ログはゆっくりと成長し、漸近クラスは内部の関数にあまり敏感ではない。