谁能帮我检查正确性，并解释原因
What is the asymptotic running time of T(n) = 3T(n/3) + O(n) with T(1) = 1 _______ .
我的答案是 nlog33 。
最佳答案
您似乎误用了 Master Theorem .
我们有T(n) = a T(n/b) + O(n)，其中a, b = 3。
因为这里的递归函数是O(n)，它的形式是O(nc logk(n )) c = 1 和 k = 0。
因此，我们处于 c = loga(b) = 1 的情况。
那么根据大定理，复杂度为O(nc logk+1(n))，即< em>O(n log(n)).
关于algorithm - 的渐近运行时间是多少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52807568/