关于对数的大O表示法

Question

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

f（x）=对数⁵（x）

f（x）= log（x ⁵）

f（x）= log（6 * log x）

f（x）= log（log x）

在错误地猜测相反的情况后，我被告知第一和第二个Big-O不相等，而第三和第四个Big-O不相等。谁能解释为什么他们不相等以及他们的Big-O是什么？

Answer 1

1. log ⁵ x与写入log log log log log x相同，这是x的非常缓慢的增长功能。
2. 这等效于5 log x（将日志内部的乘幂重写为外部乘法），这等效于log x。
3. 这等效于日志6 +日志x，这等效于日志x。
4. 这只是日志x。

因此，您有O（log log log log log x），O（log x），O（log log x）和O（log log x）这三个不同的Big-O类。

如果您的面试官说3和4不同，则可能是他误会了，或者您忘记了这个问题（一直在发生）。