问题描述
我不确定以下问题：
是O中的log （n ） （log （n ））表示常量a，b？
当询问函数f（x）是否在O（g（x））中时，它实际上比较了这两个函数的增长率。 （请参阅Wikipedia：）
函数的常数因数被忽略，因此2x在O（x）中。同样，具有较低增长率的函数组件也被忽略，因此2x ^ 2 + x +1在O（x ^ 2）中。
所以问题是：loga n ^ b的增长率是否与logb n ^ a相似？
为解决这个问题，我们将应用几个令人敬畏的对数属性：
- log x ^ b = b log x
- loga x =（logb x）/（logb a）
首先要做的是修复大型文件通过比较上面的第一个属性，我们正在比较的O表示法不是最小的，我们得到：
O（logb n ^ a）= O（a logb n），因为常量系数从大的O表示法中删除了增长率的表示形式是：
O（logb n）。
现在将第一个标识应用于第一个公式：
loga n ^ b = b loga n
接下来，我们使用第二个属性更改基数：
loga n ^ b = b（logb n）/（logb a）
这也可以组织为： / p>
loga n ^ b =（b / logb a）logb n
请注意（b / logb a）是一个公司因此nstant系数（b / logb a）logb n在O（logb n）
所以问题的答案是肯定的。 loga n ^ b在O（logb n ^ a）中。
I am not sure about the following question:
Is log(n) in O(log(n)) for constants a, b?
When asked if a function f(x) is in O(g(x)) it really compares the rate of growth of those two functions. (see wikipedia: http://en.wikipedia.org/wiki/Big_O_notation)
Constant factors of the functions are ignored so 2x is in O(x). Also components of the function that have lower growth rates are similarly ignored so 2x^2 + x + 1 is in O(x^2).
So the question is: does loga n^b have a similar growth rate as logb n^a?
To solve this we will apply a couple of awesome properties of logarithms:
- log x^b = b log x
- loga x = (logb x) / (logb a)
First thing to do is to fix the big O notation we are comparing to as it is not minimal, by applying the first property above we get:O(logb n^a) = O(a logb n) because constant coeficient are removed from big O notations the real representation of the rate of growth is:O(logb n).
Now applying the first identity to the first formula we have:
loga n^b = b loga n
next we change the base using the second property we get:
loga n^b = b (logb n) / (logb a)
this can also be organized to look like:
loga n^b = (b / logb a) logb n
note that (b / logb a) is a constant coeficient therefore (b / logb a) logb n is in O(logb n)
So the answer to the question is yes. loga n^b is in O(logb n^a).
这篇关于这个功能复杂吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！