主方法 当f(n)=nlogn怎么办

如果你要求主方法的时间复杂度，假设主方法的时间复杂度为T(n)，则有：

T(n) = 2T(n/2) + nlogn

这个递归式可以使用主定理来解决。根据主定理，我们可以得到：

a = 2, b = 2, f(n) = nlogn

因为 f(n) = nlogn = Θ(nlogn) = Θ(n^logb(a))，所以根据主定理，主方法的时间复杂度为 Θ(f(n)logn) = Θ(nlognlogn)。

如果你要对这个递归式进行求解，可以使用递归树或主方法等技巧，得到T(n) = Θ(nlog^2 n)。

相关问题

f(n)=nlogn的tight bound

f(n)=nlogn的tight bound是O(nlogn)和Ω(nlogn)。

证明如下：

O(nlogn)证明：

对于任意n>1，由于logn是单调递增的，因此有

nlogn ≤ nlogn + nlogn + … + nlogn (共logn个nlogn)

= nlogn

因此，f(n)=nlogn是O(nlogn)的。

Ω(nlogn)证明：

我们需要找到一个常数c和一个整数n0，使得对于所有的n≥n0，都有f(n)≥c⋅nlogn。

考虑取c=1/2，n0=2。对于n≥n0，有：

f(n) = nlogn = logn^(n) ≥ log2^(n) = nlog2

又因为log2是一个常数，因此有

f(n) ≥ 1/2⋅nlogn

故f(n)=nlogn是Ω(nlogn)的。

f(n)=nlogn的渐进下界

f(n)=nlogn的渐进下界是Ω(nlogn)。

这是因为当n趋近于无穷大时，函数f(n)的值必须大于或等于一个常数乘以nlogn，才能被视为其渐进下界。即使在最坏的情况下，f(n)也必须要达到这个下界。

对数函数的增长非常缓慢，所以nlogn的增长速度是非常快的，因此可以成为f(n)的渐进下界。