第二节
算法的时间复杂度与空间复杂度

考点3　时间复杂度

例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 ² )

C. O ( n log n )

D.以上均错误

【答案】 A

【解析】 本题考查时间复杂度的计算。在函数一开始， i 和 j 均为0， i 每次循环加1，而 j 每次循环的结果为 j +1，因此整个函数的执行过程中，每次for循环实际上只会执行3次操作，分别为 j 和sum的自增操作，以及循环后的i++操作，因此执行时间约为3 n ，时间复杂度为 O ( 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 ² )

【答案】 B

【解析】 本题考查时间复杂度的计算。此程序段主要耗时在循环上，循环共执行了 x 次，需要根据 n 求得 x 。根据式子 n =（ x +1）（ x +1）求解 x ，最终求得循环执行次数 x ≈ ，即 n ^1/2 ，所以此程序段的时间复杂度为 O ( n ^1/2 )。

例3.一个算法的时间复杂度为 O ( n ² )，则下列说法中哪个是正确的（ ）。【模拟题】

A.该算法的执行时间为 n ²

B.该算法的执行时间与 n ² 成正比

C.该算法的问题规模是 n ²

D.该算法的问题规模与 n ² 成正比

【答案】 B

【解析】 本题考查时间复杂度的分析。首先算法的时间复杂度是对时间的考量，而不是对问题规模的考量，时间复杂度和问题规模无关（但和数据规模有关），因此C、D选项不正确；其次时间复杂度是一种渐进表示方式，其省略了最高项的系数以及所有的其他项，因此大多数问题的执行时间都不会恰好为 n ² ，但可能和 n ² 成正比，例如执行时间可能为2 n ² 。故A选项不正确，B选项正确。

例4.下列关于算法时间复杂度的说法中，正确的是（ ）。【模拟题】

A.算法的时间复杂度与问题规模有关

B.算法的时间复杂度与程序设计语言有关

C.算法的时间复杂度与算法解决问题的策略有关

D.算法的时间复杂度与算法中语句的执行次数无关

【答案】 C

【解析】 本题考查时间复杂度的分析。规模很大的问题的解决策略的时间复杂度可能很小，故A选项错误。时间复杂度是一种多项式，程序设计语言不会影响多项式的系数和项数，故B选项错误。对于同一个问题，不同解决策略的时间复杂度可能不同。例如，不同的排序算法，虽然都是为了排序，但是时间复杂度不完全一致，故C选项正确。对时间复杂度的分析实际上就是对最内层循环语句的分析，因此关键的语句执行次数多出一个量级后，时间复杂度自然会变大，故D选项错误。

考点4　空间复杂度

例.某算法的空间复杂度为 O (1)，则（ ）。【2015年四川大学】

A.该算法执行不需要任何辅助存储空间

B.该算法执行所需辅助存储空间的大小与问题规模 n 无关

C.该算法执行不需要任何存储空间

D.该算法执行所需存储空间的大小与问题规模 n 无关

【答案】 B

【解析】 本题考查空间复杂度的分析。空间复杂度与时间复杂度相似，它们都是数学上的渐进表示方式。空间复杂度的意义为在算法执行过程中，不需要大于常数级别的辅助存储空间，而不是不需要大于常数级别的存储空间。这里考生应清楚存储空间与辅助存储空间的易混淆之处。