x*log(x)与x ^ a有一个渐近极限,其中a是(1,2)？

Question

我知道,O(x) < O(x*logx)和O(x^2)>O(x*logx),但我们有什么可以说的 O(x^a) ? O(x*logx),其中a是1和2之间.

Answer 1

分析这个的最简单方法是声明y=log(x)并重写我们的表达式:

1. x^a = (2^y)^a 
2. x*log(x) = (2^y)*y

现在取两者的对数:

1. log ((2^y)^a) = y * a
2. log ((2^y)*y) = y + log(y)

减去y,你得到这个:

1. y * (a-1)
2. log(y)

从中可以看出,对于所有a > 1表达式1线性增长,表达式2以对数方式增长,这意味着O(x^a) > O(x*logx)对于所有a> 1.