O（log_2（n））= O（log_10（n））？

Question

說O（log_2（n））中的算法是否也在O（log_10（n））中是真的嗎？我會說yes，因爲log_2（n）= log_10（n）/ log_10（2）和1/log_10（2）是一個常數。

在這種情況下，如果我們考慮一個d進制堆在heapify操作所依賴的樹，爲什麼所有我看過的文件中指定的複雜性日誌基數而d的高度不取決於輸入大小？

Answer 1

你是對的。談到漸近行爲時，對數的基數可以忽略，證明正是你提供的。

我相信你提到的論文包括更清晰的基礎（儘管顯然它也可能令人困惑）。

Answer 2

當考慮big O notation ,

log₁₀(x) = log₂(x)/log₂(10)和1/log₂(10)是一個常數，因此可以從asymptotic analysis被省略。

任何對數的底數可以從a更改爲b（均爲constant wrt. n）。

O(log₁₀(n))相同O(log₂(n))，O(ln(n))等