algorithm - 时间复杂度和马斯特定理

Question

我正在努力更好地理解马斯特定理和时间复杂度。我在网上找到了一些我正在练习的例子。我的工作正确吗？

T(N) = 3T(N/3) + O(N)

时间复杂度为Θ(n)，因为log(base 3) 3 = 1。因此，Θ(n^1) + O(N)简化为Θ(n)。

T(N) = 3T(2N/3) + O(1)

这个我没看懂。我知道这是走狗排序算法，但如果使用大师定理，a 和 b 不会都是 3，使 log(base 3) 3 = 1，从而使这个 Θ(n)？我知道这是不正确的，但我很难理解大师定理。

T(N) = 4T(N/2) + O(N)

时间复杂度为Θ(n^2)，因为log(base 2) 4 = 2。那么，N^(log(base 2) 4) = N^2

T(N) = 2T(N/2) + O(N log(N))

这里我认为它只是 O(N log(N))，因为 log(base 2) of 2 是 1。

Answer 1

通过主定理:-

if 
T(n) = aT(n/b) + f(n^k)

if loga/logb > k  then T(n) = O(n^(loga/logb))

if loga/logb < k  then T(n) = O(n^k)

else T(n) = O(n*logn)

 1. a = 3 b = 3 k=0  loga/logb = 1 = k    hence T(n) = O(nlogn)
 2. a = 3 b = 3/2 k=0 log3/log(3/2) > 1 > k  hence T(n) = O(n^(log3/log(3/2)))
 3. a = 4 b = 2 k = 1 log4/log2 = 2 > 1  hence T(n) = O(n^2)