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

考点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(n2)

C．O(nlogn)

D．以上均错误

【答案】 A

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

知识链接

时间复杂度描述的是算法执行时间随着输入规模的增长而增加的趋势。它通常以执行基本操作的次数作为度量，用来评估算法的执行效率。常见记号为O。

以下是常见的时间复杂度的定义。

O(1)：常数时间复杂度，无论输入规模增大多少，算法执行时间都固定。

O(logn)：对数时间复杂度，算法执行时间随输入规模呈对数增长，即增长缓慢。

O(n)：线性时间复杂度，算法执行时间随输入规模呈线性增长。

O(nlogn)：线性对数时间复杂度，算法执行时间随输入规模呈线性对数增长。

O(n2)：平方时间复杂度，算法执行时间随输入规模呈平方增长。

O(n3)：立方时间复杂度，算法执行时间随输入规模呈立方增长。

O(2n)：指数时间复杂度，算法执行时间随输入规模呈指数增长。

上述时间复杂度的比较关系为：

O(1) ≤ O (logn)≤O(n) ≤ O (nlogn)≤O(n2) ≤ O(n3) ≤O(2n)。

例2．设n为描述问题规模的非负整数，下列程序段的时间复杂度是（　　）。【2019年全国统考】

x=0;
while(n>=(x+1)*(x+1)){
    x=x+1;
}

A．O(logn)

B．O(n1/2)

C．O(n)

D．O(n2)

【答案】 B

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

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

A．该算法的执行时间为n2

B．该算法的执行时间与n2成正比

C．该算法的问题规模是n2

D．该算法的问题规模与n2成正比

【答案】 B

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

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

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

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

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

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

【答案】 C

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