T(n) = 3(logn)^6 n^3 + 7n^4+n+7=O()?
时间: 2023-12-25 14:06:34 浏览: 25
We can simplify the expression as follows:
T(n) = 3(logn)^6 n^3 * 7n^4
T(n) = 21(logn)^6 n^7
Now we can see that the dominant term is n^7, so we can simplify further:
T(n) = O(n^7)
Therefore, T(n) is bounded by a constant multiple of n^7, so we can say that T(n) is O(n^7).
相关问题
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) = 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)。