关于对数的大O表示法 [英] Big-O Notation regarding logarithms

问题描述

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

I got asked an interview question that wanted me to discern the Big-O notation of several logarithmic functions. The functions were as follows:

f（x）= log ⁵ （x）

f(x) = log⁵(x)

f（x）= log（x ⁵ ）

f(x) = log(x⁵)

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

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

f（x）= log（log x）

f(x) = log(log x)

我被告知第一和第二个Big-O错误地猜出了相反的意思之后，第三个和第四个不相等。谁能解释为什么它们不相等以及它们的Big-O是什么？

I was told that the Big-O for the first and second are not equivalent and the third and fourth are not equivalent after mistakenly guessing the opposite. Can anyone explain why they are not equivalent and what their Big-O are then?

推荐答案

1. log ⁵ x与编写log log log log log log x相同，它是x的非常缓慢增长的功能。


2. 这等效于5 log x（将日志内部的乘幂重写为外部乘法），等效于log x。


3. 这等效于log 6 + log log x，等效记录日志x。


4. 这只是日志x。

1. log⁵ x is the same as writing log log log log log x, which is a very slow-growing function of x.
2. This is equivalent to 5 log x (rewriting exponentiation inside the log as multiplication outside), which is equivalent to log x.
3. This is equivalent to log 6 + log log x, which is equivalent to log log x.
4. This is just log log x.

所以你有O （log log log log log x），O（log x），O（log log x）和O（log log x）这三个不同的Big-O类。

So you have O(log log log log log x), O(log x), O(log log x) and O(log log x), three distinct Big-O classes.

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

If your interviewer said 3 and 4 were different, either he was mistaken or you've misremembered the question (happens all the time).

这篇关于关于对数的大O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！