题目

某算法的语句执行频[1]度为(3n+nlog2n+n^2+8)，其时间复杂度为( )。O(n)B. O(nlog2n)C. O(n^2)D. O(log2n)

某算法的语句执行频[1]度为(3n+nlog2n+n^2+8)，其时间复杂度为( )。

  1. O(n)

B. O(nlog2n)

C. O(n^2)

D. O(log2n)

题目解答

答案

对于给定的语句执行频度(3n+nlog2n+n^2+8)，我们可以根据增长趋势判断其时间复杂度。当n趋向无穷大时，其中的线性项3n和对数项nlog2n都会被抛弃，而平方项n^2会主导增长。因此，该算法的时间复杂度为O(n^2)。

答案：C. O(n^2)

解析

时间复杂度的判断核心在于确定算法执行时间随输入规模$n$增长的主导项。

  • 关键思路：忽略低阶项和系数，只保留增长最快的项。
  • 破题点：比较表达式$3n + n\log_2 n + n^2 + 8$中各项的增长速率。
    • $n^2$是二次项，增长最快；
    • $n\log_2 n$次之，$3n$和常数项$8$最慢。
      当$n$足够大时，$n^2$将主导整个表达式，因此时间复杂度为$O(n^2)$。

步骤分析

  1. 拆分表达式：将$3n + n\log_2 n + n^2 + 8$分解为四个独立项。
  2. 比较增长速率：
    • 二次项$n^2$的增长速率远快于其他项（如$n\log_2 n$、$3n$）。
    • 例如，当$n=1000$时，$n^2=10^6$，而$n\log_2 n \approx 1000 \times 10 = 10^4$，差距显著。
  3. 确定主导项：$n^2$是主导项，其他项可忽略。
  4. 结论：时间复杂度为$O(n^2)$。