n(logn)2与nlog n那个时间复杂度大？

当 n 趋近于无穷大时，时间复杂度 n(logn)2 比 nlogn 更大。这是因为 (logn)2 的增长速度比 logn 还快。可以通过比较它们的极限来得出这个结论。当 n 趋近于无穷大时，n(logn)2 的极限为正无穷，而 nlogn 的极限为无穷大。因此，n(logn)2 的时间复杂度比 nlogn 更大。

相关问题

作业1：(对应算法基础部分，25分) 已知T(n)=2T(n/2)+nlog₂n,且T(1)=1,求T(n)的时间复杂度。

根据主定理（Master Theorem），可以解出该递归式的时间复杂度为 O(nlog₂n)。具体证明如下：

将递归式 T(n) = 2T(n/2) + nlog₂n 转化为通用形式 T(n) = aT(n/b) + f(n)，其中 a = 2，b = 2，f(n) = nlog₂n。那么有：

- 当 f(n) = O(n^(log_ba-ϵ))，其中 ϵ > 0 时，T(n) = Θ(n^(log_ba))。因为 log₂2 = 1，所以 log_ba = 1。又因为 nlog₂n = O(n^1)，所以 f(n) = O(n^(log_ba-ϵ))，即 f(n) = O(n^(1-ϵ))。因此，T(n) = Θ(nlog₂n)。
- 当 f(n) = Θ(n^(log_ba)) 时，T(n) = Θ(n^(log_ba) * logn)。因为 log₂2 = 1，所以 log_ba = 1。又因为 f(n) = Θ(nlog₂n) = Θ(n^(log_ba) * logn)，所以 T(n) = Θ(nlog₂n * logn)。
- 当 f(n) = Ω(n^(log_ba+ϵ))，其中 ϵ > 0 时，T(n) = Θ(f(n))。因为 nlog₂n = Ω(n^(1+ϵ))，所以 f(n) = Ω(n^(log_ba+ϵ))，即 f(n) = Ω(n^(1+ϵ))。根据主定理第三种情况，T(n) = Θ(nlog₂n)。

综上所述，T(n) 的时间复杂度为 O(nlog₂n)。

求素数时间复杂度分析

求素数的时间复杂度通常可以分为两个部分：筛选素数的时间复杂度和判断一个数是否为素数的时间复杂度。

1. 筛选素数的时间复杂度：
- 最常用的素数筛法是埃拉托斯特尼筛法，其时间复杂度为 O(nlog(logn))。
- 另一种常见的素数筛法是欧拉筛法，其时间复杂度也为 O(nlog(logn))。

2. 判断一个数是否为素数的时间复杂度：
- 最简单的方法是试除法，即遍历从 2 到 sqrt(n) 的所有数，判断是否能整除 n，时间复杂度为 O(sqrt(n))。
- 若使用更加高效的算法，如 Miller-Rabin 算法或 AKS 算法，则时间复杂度可以降低到多项式级别。

综上所述，求素数的时间复杂度大致可以认为是 O(nlog(logn)) 或 O(sqrt(n))，具体取决于所采用的算法。