数学 - 2算法的关系

Question

A 和 B 的两个表达式：

A = 2^(3(log_3 n))
B = 6(n^2)

因为我需要指出 A 是 B 的 big-Oh、big-Omega 还是 big-theta，是 A=O(B) 吗？

如何解决这个问题？

Answer 1

让我们做一个简单的数学运算（log(x, b)代表以b为底的对数；log(x) = log(x, 2)是二进制对数）：

A = 2 ** (3 * log(n, 3)) = 
    2 ** (log(n ** 3, 3)) = 
    2 ** (log(n ** 3) / log(3)) = 
    n ** (3 / log(3)) =
    n ** (log(2 ** 3, 3)) =
    n ** (log(8, 3)) ~
    n ** 1.8928...

何时

B = 6 * n**2

最后，算法 A 的复杂度比 B 更好（1.8928… < 2）：

A = O(n**(log(8, 3)) ~ O(n**1.8928)
B = O(6 * n**2) = O(n**2)

Answer 2

我想放大已经给出的答案：我们可以重写函数 A(n)=2^(3(log_3 n)):

A(n) = 2^(3*(log_3 n))
     = exp( ln(2^(3*(log_3 n))) )
     = exp( 3*(log_3 n)*ln(2) )
     = exp( 3*ln(n)/ln(3)*ln(2) )
     = exp( 3*ln(2)/ln(3)*ln(n) )
     = n^(3*ln(2)/ln(3))

其中 ln 是自然对数。所以我们得到 A(n)/B(n) = 1/6 * n^(3*ln(2)/ln(3)-2) 与 3*ln(2)/ln(3)-2<0 因此

lim_{n to inf} abs(A(n)/B(n)) = 0 < inf

即A=O(B)

由于A收敛，所以limt、limit inferior和limit superior相等：

liminf_{n to inf} abs(A(n)/B(n)) = 0 (!>0)

即A!=Omega(B) 因此也 A!=Theta(B)

有关定义，请参阅 https://en.wikipedia.org/wiki/Big_O_notation

数学 - 2算法的关系

Math - Relation of 2 algorithm

algorithm

performance

math

relation

asymptotic-complexity