下载掌阅APP，畅读海量书库
立即打开
例1.下面这段代码中，执行函数func的时间复杂度为（ ）。【模拟题】
void func(int n){
int i=0,j=0,sum=0;
for(i=0;i<n;i++){
while(j<=i){
j++;
sum++;
}
}
}A. O ( n )
B. O ( n 2 )
C. O ( n log n )
D.以上均错误
【答案】 A
【解析】 本题考查时间复杂度的计算。在函数一开始， i 和 j 均为0， i 每次循环加1，而 j 每次循环的结果为 j +1，因此整个函数的执行过程中，每次for循环实际上只会执行3次操作，分别为 j 和sum的自增操作，以及循环后的i++操作，因此执行时间约为3 n ，时间复杂度为 O ( n )。
知识链接
时间复杂度描述的是算法执行时间随着输入规模的增长而增加的趋势。它通常以执行基本操作的次数作为度量，用来评估算法的执行效率。常见记号为 O 。
以下是常见的时间复杂度的定义。
O (1)：常数时间，无论输入规模增大多少，算法执行时间都固定。
O (log n )：对数时间，算法执行时间随输入规模呈对数增长，即增长缓慢。
O ( n )：线性时间，算法执行时间随输入规模呈线性增长。
O ( n log n )：线性对数时间，算法执行时间随输入规模呈线性对数增长。
O ( n 2 )：平方时间，算法执行时间随输入规模呈平方增长。
O ( n 3 )：立方时间，算法执行时间随输入规模呈立方增长。
O (2 n )：指数时间，算法执行时间随输入规模呈指数增长。
上述时间复杂度的比较关系为：
O (1) ≤ O (log n )≤ O ( n ) ≤ O ( n 2 ) ≤ O ( n 3 ) ≤ O (2 n )。
例2.设 n 为描述问题规模的非负整数，下列程序段的时间复杂度是（ ）。【2019年全国统考】
x=0;
while(n>=(x+1)*(x+1)){
x=x+1;
}A. O (log n )
B. O ( n 1/2 )
C. O ( n )
D. O ( n 2 )
【答案】 B
【解析】
本题考查时间复杂度的计算。此程序段主要耗时在循环上，循环共执行了
x
次，需要根据
n
求得
x
。根据式子
n
=（
x
+1）（
x
+1）求解
x
，最终求得循环执行次数
x
≈
，即
n
1/2
，所以此程序段的时间复杂度为
O
(
n
1/2
)。
例3.一个算法的时间复杂度为 O ( n 2 )，则下列说法中哪个是正确的（ ）。【模拟题】
A.该算法的执行时间为 n 2
B.该算法的执行时间与 n 2 成正比
C.该算法的问题规模是 n 2
D.该算法的问题规模与 n 2 成正比
【答案】 B
【解析】 本题考查时间复杂度的分析。首先算法的时间复杂度是对时间的考量，而不是对问题规模的考量，时间复杂度和问题规模无关（但和数据规模有关），因此C、D选项不正确；其次时间复杂度是一种渐进表示方式，其省略了最高项的系数以及所有的其他项，因此大多数问题的执行时间都不会恰好为 n 2 ，但可能和 n 2 成正比，例如执行时间可能为2 n 2 。故A选项不正确，B选项正确。
例4.下列关于算法时间复杂度的说法中，正确的是（ ）。【模拟题】
A.算法的时间复杂度与问题规模有关
B.算法的时间复杂度与程序设计语言有关
C.算法的时间复杂度与算法解决问题的策略有关
D.算法的时间复杂度与算法中语句的执行次数无关
【答案】 C
【解析】 本题考查时间复杂度的分析。规模很大的问题的解决策略的时间复杂度可能很小，故A选项错误。时间复杂度是一种多项式，程序设计语言不会影响多项式的系数和项数，故B选项错误。对于同一个问题，不同解决策略的时间复杂度可能不同。例如，不同的排序算法，虽然都是为了排序，但是时间复杂度不完全一致，故C选项正确。对时间复杂度的分析实际上就是对最内层循环语句的分析，因此关键的语句执行次数多出一个量级后，时间复杂度自然会变大，故D选项错误。
例.某算法的空间复杂度为 O (1)，则（ ）。【2015年四川大学】
A.该算法执行不需要任何辅助存储空间
B.该算法执行所需辅助存储空间的大小与问题规模 n 无关
C.该算法执行不需要任何存储空间
D.该算法执行所需存储空间的大小与问题规模 n 无关
【答案】 B
【解析】 本题考查空间复杂度的分析。空间复杂度与时间复杂度相似，它们都是数学上的渐进表示方式。空间复杂度的意义为在算法执行过程中，不需要大于常数级别的辅助存储空间，而不是不需要大于常数级别的存储空间。这里考生应清楚存储空间与辅助存储空间的易混淆之处。
误区警示
空间复杂度描述的是算法执行期间所需辅助存储空间的大小。它通常以数据结构的存储空间和程序使用空间的度量来评估算法的空间性能。