algorithm - 关于对数的大 O 表示法

Question

我被问到一个面试问题，希望我辨别几个对数函数的 Big-O 表示法。功能如下：

f(x) = log ⁵ (x)

f(x) = log(x ⁵ )

f(x) = log(6*log x)

f(x) = log(log x)

有人告诉我，第一个和第二个的 Big-O 不等价，第三个和第四个不等价，因为我错误地猜测相反。谁能解释为什么它们不相等以及它们的 Big-O 是什么？

Answer 1

1. log ⁵ x 和写 log log log log log x 一样，是 x 的一个增长很慢的函数。
2. 这相当于 5 log x（将 log 内的幂重写为外部的乘法），相当于 log x。
3. 这相当于log 6 + log log x，相当于log log x。
4. 这只是 log log x。

所以你有 O(log log log log log x)、O(log x)、O(log log x) 和 O(log log x)，三个不同的 Big-O 类。

如果你的面试官说 3 和 4 不同，要么是他弄错了，要么你记错了问题（经常发生）。

Answer 2

这是一个数学问题：

1. f(x) = log ⁵ (x)
2. f(x) = log(x ⁵ ) = 5 * log x
3. f(x) = log(6*log x) = log 6 + log(log x)
4. f(x) = log(log x)

所以大O是

1. O(log ⁵ (x))
2. O(log x)
3. O(log (log x))
4. O(log (log x))

所以 (1) 和 (2) 不等价，但 (3) 和 (4) 是等价的（尽管它们与 (1) 和 (2) 都不同）

Answer 3

f(x) = log^5(n)
f(x) = log(n^5) -> 5 log(n)
O(5 log(n)) < O(log(n)^5)

f(x) = log(6*log n) -> log(6)+log(log(n))
f(x) = log(log n) 
log(log n) < log(6) + log(log(n)) 

, 虽然 log(6) 是一个常数，所以它们有相同的 O

Answer 4

我假设你的意思是f(n)，不是f(x)。对于 1 和 2，log^5(n)等价于O(log log log log log(n)), 而log(n^5) = 5 log(n) = O(log n).

对于3和4，我不同意。log(6*log n) = log(6) + log(log n) = O(log log n)，与 4 - 相同O(log log n)。