比较 n^a * log(n)^b 和 n^c*log(n)^d 的运行时复杂度
Comparing runtime complexities for n^a * log(n)^b and n^c*log(n)^d
我正在解决一个问题，我得到 f(n) = n^2 * (log(n))^-1 和 g(n) = n(log(n))^2 , 并要求确定 f=O(g)、f=omega(g) 或两者 (f=theta(g)).
这个问题可以概括为 (n^a)*log(n)^b 和 (n^c)*log(n)^d
我知道任何多项式支配任何对数，例如 n 支配 log(n) 而且 n^2 支配 nlog(n) 但是我不确定如何使它适应更复杂的问题，例如：
- f = (n^2)*log(n)^-1000, g = (n)*log(n)^1000
或更好：
- f = n^.01, g = log(n)^10
多项式项是否总是确定 f 是否支配 g，反之亦然？如果是这样，为什么？如果没有，如何解决问题？
谢谢！
答案：如果a > c，n^a * log(n)^b支配n^c * log(n)^d。换句话说，你只需要看多项式部分。 （当然 a=c 除外，在这种情况下，您可以查看 polylog 部分。）
这是因为多对数函数总是渐近地小于多项式函数。更准确地说，如果 p(n) = a*(log n)^b（p 在 n 中是多对数的），那么 p(n) = o(n^epsilon) 对任何 epsilon > 0（见 this Wikipedia page for the formal statement, and this answer 证明）。
因此，对于任何 epsilon > 0，我们都有 n^a * log(n)^b = o(n^(a + epsilon))。由此应该很容易得出上面的答案。
我正在解决一个问题，我得到 f(n) = n^2 * (log(n))^-1 和 g(n) = n(log(n))^2 , 并要求确定 f=O(g)、f=omega(g) 或两者 (f=theta(g)).
这个问题可以概括为 (n^a)*log(n)^b 和 (n^c)*log(n)^d
我知道任何多项式支配任何对数，例如 n 支配 log(n) 而且 n^2 支配 nlog(n) 但是我不确定如何使它适应更复杂的问题，例如：
- f = (n^2)*log(n)^-1000, g = (n)*log(n)^1000
或更好：
- f = n^.01, g = log(n)^10
多项式项是否总是确定 f 是否支配 g，反之亦然？如果是这样，为什么？如果没有，如何解决问题？
谢谢！
答案：如果a > c，n^a * log(n)^b支配n^c * log(n)^d。换句话说，你只需要看多项式部分。 （当然 a=c 除外，在这种情况下，您可以查看 polylog 部分。）
这是因为多对数函数总是渐近地小于多项式函数。更准确地说，如果 p(n) = a*(log n)^b（p 在 n 中是多对数的），那么 p(n) = o(n^epsilon) 对任何 epsilon > 0（见 this Wikipedia page for the formal statement, and this answer 证明）。
因此，对于任何 epsilon > 0，我们都有 n^a * log(n)^b = o(n^(a + epsilon))。由此应该很容易得出上面的答案。