algorithm - 的渐近运行时间是多少

Question

谁能帮我检查正确性，并解释原因

What is the asymptotic running time of T(n) = 3T(n/3) + O(n) with T(1) = 1   _______ .  

我的答案是 n^log₃3 。

Answer 1

您似乎误用了 Master Theorem .

我们有T(n) = a T(n/b) + O(n)，其中a, b = 3。

因为这里的递归函数是O(n)，它的形式是O(n^c log^k(n )) c = 1 和 k = 0。

因此，我们处于 c = log_a(b) = 1 的情况。

那么根据大定理，复杂度为O(n^c log^k+1(n))，即< em>O(n log(n)).