f(n)=n³ n logn渐进上界。
时间: 2023-05-28 10:02:00 浏览: 81
根据定义,若存在正常数C和n0,使得对于所有n≥n0, 有f(n)≤Cn³nlogn,则f(n)是O(n³nlogn)。
我们可以利用以下结论来证明:
对于所有n≥2,有nlogn≤n²
因此,
f(n) = n³nlogn
≤ n³n² (当n≥2时)
= n^5
因此,f(n)是O(n^5)。
相关问题
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怎么办
如果你要求主方法的时间复杂度,假设主方法的时间复杂度为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)。