數學 - 2算法的關係

Question

兩個A和B的表達：

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

正如我需要指明A是否大-OH，大歐米茄，或B的大-θ ， 是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，在限劣和限制優越相等：

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