一尘不染

关于对数的大O表示法

algorithm

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

f(x)=对数5(x)

f(x)= log(x 5)

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

f(x)=对数(log x)

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


阅读 509

收藏
2020-07-28

共1个答案

一尘不染

  1. log 5 x与编写log log log log log x 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不同,则可能是他误会了,或是您忘记了这个问题(一直在发生)。

2020-07-28