T(n) = 9T(n/3) + n^2logn的asymptotically tight bound

根据主定理，对于递归式T(n) = 9T(n/3)，有a=9，b=3，d=logb(a)=2。

因为d=logb(a)，所以T(n)的渐近复杂度为O(n^dlogn) = O(n^2logn)。

因此，T(n)的渐近紧密界为O(n^2logn)。

相关问题

T（n）=2*T(N/2)+n*logn的时间复杂度

根递归关系 T(n = 2T(n/2) + nlogn，可以使用主定理（Master Theorem）来求解时间复杂度。

首先，观察递归关系式中的形式，我们可以发现 a = 2，b = 2，f(n) = nlogn。根据主定理的第三种情况，如果 f(n) = Θ(n^clog^k(n))，其中 k ≥ 0，则时间复杂度为 T(n) = Θ(n^clog^(k+1)(n))。

在这个递归关系中，f(n) = nlogn，所以 c = 1，k = 0。代入到时间复杂度公式中，得到 T(n) = Θ(n^1log^(0+1)(n)) = Θ(nlogn)。

因此，根据给定的递归关系 T(n) = 2T(n/2) + nlogn，其时间复杂度为 Θ(nlogn)。

T(n) = 2T(n/2) + nlogn的tight bound

通过主定理（Master Theorem），可得T(n)=O(nlogn)。因为a=2, b=2, f(n) = n^log_ba = n^log_22 = n。根据主定理，当f(n) = O(n^log_ba-ε)时，复杂度为O(n^log_ba)；当f(n) = Θ(n^log_ba)时，复杂度为O(n^log_ba * logn)；当f(n) = Ω(n^log_ba+ε)且af(n/b) <= cf(n)时，复杂度为O(f(n))。 因为n = Ω(n^ε)，且2(n/2) <= cn，所以满足上述条件。故复杂度为O(nlogn)。