基本信息

---

下载

文档摘要

---

国家计算机二级考试题库部分答案

一、公共基础知识部分

（一）数据结构与算法

1.算法复杂度

题目：已知某算法的时间复杂度为$O(n^2)$，当输入规模$n=10$时，执行时间为$t$秒。若输入规模变为$n=20$，则执行时间约为多少秒？

答案：根据时间复杂度的定义，$O(n^2)$表示算法的执行时间与输入规模$n$的平方成正比。设输入规模为$n_1=10$时执行时间为$T(n_1)$，输入规模为$n_2=20$时执行时间为$T(n_2)$。

由时间复杂度的性质可得：$\frac{T(n_2)}{T(n_1)}=\frac{n_2^2}{n_1