当被问及函数f(x)是否在O(g(x))时,它确实比较了这两个函数的增长率.(参见维基百科:http://en.wikipedia.org/wiki/Big_O_notation)
忽略函数的常数因子,因此2x在O(x)中.此外,具有较低生长速率的函数的组件也被忽略,因此2x ^ 2 + x + 1在O(x ^ 2)中.
所以问题是:loga n ^ b的增长率是否与logb n ^ a相似？
为了解决这个问题,我们将应用几个令人敬畏的对数属性:
首先要做的是修复我们正在比较的大O符号,因为它不是最小的,通过应用上面的第一个属性我们得到:O(logb n ^ a)= O(logb n),因为常量系数从大O符号表示增长率的实际表示为:O(logb n).
现在将第一个身份应用于我们的第一个公式:
loga n ^ b = b loga n
接下来我们使用我们获得的第二个属性更改基数:
loga n ^ b = b(logb n)/(logb a)
这也可以组织成如下:
loga n ^ b =(b/logb a)logb n
注意(b/logb a)是一个常数系数因此(b/logb a)logb n在O(logb n)中
所以这个问题的答案是肯定的.loga n ^ b在O(logb n ^ a)中.
| 归档时间： |
|
| 查看次数： |
161 次 |
| 最近记录： |