1.2 算法和算法评价

1.2.1 算法的基本概念

算法 (Algorithm) 是对特定问题求解步骤的一种描述, 它是指令的有限序列, 其中的每条指令表示一个或多个操作。此外, 一个算法还具有下列五个重要特性:

1. 有穷性。一个算法必须总在执行有穷步之后结束, 且每一步都可在有穷时间内完成。

2. 确定性。算法中每条指令必须有确切的含义, 对于相同的输入只能得出相同的输出。

3. 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

4. 输入。一个算法有零个或多个输入, 这些输入取自于某个特定的对象的集合。

5. 输出。一个算法有一个或多个输出, 这些输出是与输入有着某种特定关系的量。

通常, 设计一个 “好” 的算法应考虑达到以下目标:

1. 正确性。算法应能够正确地解决求解问题。

2. 可读性。算法应具有良好的可读性, 以帮助人们理解。

3. 健壮性。算法能对输入的非法数据做出反应或处理, 而不会产生莫名其妙的输出。

4. 高效率与低存储量需求。效率是指算法执行的时间, 存储量需求是指算法执行过程中所需要的最大存储空间, 这两者都与问题的规模有关。

1.2.2 算法效率的度量

【命题追踪】 (算法题) 分析时空复杂度 (2010-2013、2015、2016、2018-2021)

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

1. 时间复杂度

【命题追踪】 分析算法的时间复杂度 (2011-2014、2017、2019、2022)

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为 $T\left(n\right)$ ,它是该算法问题规模 $n$ 的函数,时间复杂度主要分析 $T\left(n\right)$ 的数量级。算法中基本运算 (最深层循环中的语句) 的频度与 $T\left(n\right)$ 同数量级,因此通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度。于是,算法的时间复杂度记为

$$T\left(n\right)=O\left(f\left(n\right)\right)$$

注：取 $f\left(n\right)$ 中随 $n$ 增长最快的项,将其系数置为 1 作为时间复杂度的度量。例如, $f\left(n\right)=a{n}^3+b{n}^2+cn$ 的时间复杂度为 $O\left(n^3\right)$

式中, $O$ 的含义是 $T\left(n\right)$ 的数量级,其严格的数学定义是: 若 $T\left(n\right)$ 和 $f\left(n\right)$ 是定义在正整数集合上的两个函数,则存在正常数 $C$ 和 $n_0$ ,使得当 $n\ge n_0$ 时,都满足 $0\le T\left(n\right)\le Cf\left(n\right)$ 。

算法的时间复杂度不仅依赖于问题的规模 $n$ ,也取决于待输入数据的性质 (如输入数据元素的初始状态)。例如,在数组 $\mathrm{A}\left[0\dots \mathrm{n}-1\right]$ 中,查找给定值 $k$ 的算法大致如下:

(1) i = n - 1;

(2) while (i>=0 && (A[i] !=k) )

(3)   i--;

(4) return i ;

该算法中语句 3 (基本运算) 的频度不仅与问题规模 $n$ 有关,而且与下列因素有关:

① 若 A 中没有与 k 相等的元素,则语句 3 的频度 $f\left(n\right)=n$ 。

② 若 A 的最后一个元素等于 k ,则语句 3 的频度 $f\left(n\right)$ 是常数 0 。

最坏时间复杂度是指在最坏情况下, 算法的时间复杂度。

平均时间复杂度是指所有可能输入实例在等概率出现的情况下, 算法的期望运行时间。

最好时间复杂度是指在最好情况下, 算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度, 以保证算法的运行时间不会比它更长。

在分析一个程序的时间复杂性时, 有以下两条规则:

1. 加法规则: $T\left(n\right)=T_1\left(n\right)+T_2\left(n\right)=O\left(f\left(n\right)\right)+O\left(g\left(n\right)\right)=O\left(max\left(f\left(n\right),g\left(n\right)\right)\right)$

2. 乘法规则: $T\left(n\right)=T_1\left(n\right)\times T_2\left(n\right)=O\left(f\left(n\right)\right)\times O\left(g\left(n\right)\right)=O\left(f\left(n\right)\times g\left(n\right)\right)$

例如,设 $a\{\}\text{、}b\{\}\text{、}c\{\}$ 三个语句块的时间复杂度分别为 $O\left(1\right)\text{、}O\left(n\right)\text{、}O\left(n^2\right)$ ,则

①

a {
    b {}
    c {}
}

时间复杂度为 $O\left(n^2\right)$ ,满足加法规则

②

a {
    b {
        c {}
    }
}

时间复杂度为 $O\left(n^3\right)$ ,满足乘法规则

常见的渐近时间复杂度为

$$O\left(1\right)<O\left({\log }_{2}n\right)<O\left(n\right)<O\left(n{\log }_{2}n\right)<O\left(n^2\right)<O\left(n^3\right)<O\left(2^n\right)<O\left(n!\right)<O\left(n^n\right)$$

2. 空间复杂度

算法的空间复杂度 $S\left(n\right)$ 定义为该算法所需的存储空间,它是问题规模 $n$ 的函数,记为

$$S\left(n\right)=O\left(g\left(n\right)\right)$$

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外, 还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身, 和算法无关, 则只需分析除输入和程序之外的额外空间。例如, 若算法中新建了几个与输入数据规模 $n$ 相同的辅助数组,则空间复杂度为 $O\left(n\right)$ 。

算法原地工作是指算法所需的辅助空间为常量,即 $O\left(1\right)$ 。

1.2.3 本节试题精选

一、单项选择题

01. 一个算法应该是 ( )。
A. 程序 B. 问题求解步骤的描述
C. 要满足五个基本特性 D. A 和 C

02. 某算法的时间复杂度为 $O\left(n^2\right)$ ,则表示该算法的 ( )。
A. 问题规模是 $n^2$ B. 执行时间等于 $n^2$
C. 执行时间与 $n^2$ 成正比 D. 问题规模与 $n^2$ 成正比

03. 若某算法的空间复杂度为 $O\left(1\right)$ ,则表示该算法 ( )。
A. 不需要任何辅助空间 B. 所需辅助空间大小与问题规模 $n$ 无关
C. 不需要任何空间 D. 所需空间大小与问题规模 $n$ 无关

04. 下列关于时间复杂度的函数中, 时间复杂度最小的是 ( )。
A. $T_1\left(n\right)=n{\log }_{2}n+5000n$ B. $T_2\left(n\right)=n^2-8000n$
C. $T_3\left(n\right)=n{\log }_{2}n-6000n$ D. $T_4\left(n\right)=20000{\log }_{2}n$

05. 以下算法的时间复杂度为 ( )。

void fun(int n) {
    int i = 1;
    while(i<=n) {
        i = i * 2;
    }
}

A. $O\left(n\right)$   B. $O\left(n^2\right)$   C. $O\left(n{\log }_{2}n\right)$   D. $O\left({\log }_{2}n\right)$

06. 有以下算法, 其时间复杂度为 ( )。

void fun(int n) {
    int i = 0;
    while(i*i*i<=n) {
        i++;
    }
}

A. $O\left(n\right)$ B. $O\left(n\log n\right)$ C. $O\left(\sqrt[3]{n}\right)$ D. $O\left(\sqrt{n}\right)$

07. 程序段如下:

for(i=n-1; i>1; i--)
    for(j=1; j<1; j++)
        if(A[j] > A[j+1])
            A[j] 与 A[j+1] 对换

其中 $n$ 为正整数,则最后一行语句的频度在最坏情况下是 ( )。

A. $O\left(n\right)$   B. $O\left(n\log n\right)$   C. $O\left(n^3\right)$   D. $O\left(n^2\right)$

08. 下列程序段的时间复杂度为 $\left(\right)$ 。

if (n >= 0) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("输入数据大于或等于零\n");
}
else {
    for (int j = 0; j < n; j++)
        printf("输入数据小于零\n");
}

A. $O\left(n^2\right)$   B. $O\left(n\right)$   C. $O\left(1\right)$   D. $O\left(n\log n\right)$

09. 以下算法中加下画线（m++）的语句的执行次数为 ( )。

int m = 0, i, j;
for (i = 1; i <= n; i++)
    for (j = 1; j <= 2 * i; j++)
        m++;

A. $n\left(n+1\right)$   B. $n$   C. $n+1$   D. $n^2$

10. 下列函数代码的时间复杂度是 ( )。

int Func(int n) {
    if (n == 1) return 1;
    else return 2 * Func(n / 2) + n;
}

A. $O\left(n\right)$   B. $O\left(n\log n\right)$   C. $O\left(\log n\right)$   D. $O\left(n^2\right)$

11.【2011 统考真题】设 $n$ 是描述问题规模的非负整数,下列程序段的时间复杂度是 ( )。

x=2;
while(x<n/2)
x = 2*x;

A. $O\left({\log }_{2}n\right)$   B. $O\left(n\right)$   C. $O\left(n{\log }_{2}n\right)$   D. $O\left(n^2\right)$

12.【2012 统考真题】求整数 $n\left(n\ge 0\right)$ 的阶乘的算法如下,其时间复杂度是 $\left(\right)$ 。

int fact(int n) {
    if (n == 1) return 1;
    else return 2 * fact(n - 1);
}

A. $O\left({\log }_{2}n\right)$   B. $O\left(n\right)$   C. $O\left(n{\log }_{2}n\right)$   D. $O\left(n^2\right)$

13.【2014 统考真题】下列程序段的时间复杂度是 ( )。

for (int k = 0; k < n; k *= 2)
{
    for (int j = 1; j <= n; j++)
    {
        count++;
    }
}

A. $O\left({\log }_{2}n\right)$   B. $O\left(n\right)$   C. $O\left(n{\log }_{2}n\right)$   D. $O\left(n^2\right)$

14.【2017 统考真题】下列函数的时间复杂度是 ( )

int func(int n)
{
    int i = 0, sum = 0;
    while (sum < n)
    {
        sum += ++i;
        return i;
    }
}

A. $O\left(\log n\right)$   B. $O\left(n^{1/2}\right)$   C. $O\left(n\right)$   D. $O\left(n\log n\right)$

15.【2019 统考真题】设 $n$ 是描述问题规模的非负整数,下列程序段的时间复杂度是 ( )。

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

A. $O\left(\log n\right)$   B. $O\left(n^{1/2}\right)$   C. $O\left(n\right)$   D. $O\left(n^2\right)$

16. 【2022 统考真题】下列程序段的时间复杂度是 ( )。

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

A. $O\left(\log n\right)$   B. $O\left(n\right)$   C. $O\left(n\log n\right)$   D. $O\left(n^2\right)$

二、综合应用题

01. 分析以下各程序段, 求出算法的时间复杂度。

①：

int i = 1;
int k = 0;
while (i < n - 1)
{
    k = k + 10 * i;
    i++;
}

②：

int y = 0;
while ((y + 1) * (y + 1) <= n)
    y = y + 1;

③

for(i=0;i<n;i++)
    for(i=0;j<m;j++)
        a[i][j]=0;

1.2.4 答案与解析

一、单项选择题

01. B
本题是中山大学往年真题, 题目没有问题, 考查的是算法的定义。程序不一定满足有穷性, 如死循环、操作系统等, 而算法必须有穷。算法代表对问题求解步骤的描述, 而程序则是算法在计算机上的特定实现。不少读者认为 C 也对,它只是算法的必要条件,不能成为算法的定义。

02. C
时间复杂度为 $O\left(n^2\right)$ ,说明算法的时间复杂度 $T\left(n\right)$ 满足 $T\left(n\right)\le c{n}^2$ (其中 $c$ 为比例常数),即 $T\left(n\right)=O\left(n^2\right)$ ,时间复杂度 $T\left(n\right)$ 是问题规模 $n$ 的函数,其问题规模仍然是 $n$ 而不是 $n^2$ 。

03. B
算法的空间复杂度为 $O\left(1\right)$ ,表示执行该算法所需的辅助空间大小相比输入数据的规模来说是一个常量, 而不表示该算法执行时不需要任何空间或辅助空间。

04. D
$\mathrm{A}$ 的最高阶是 $n{\log }_{2}n$ ,时间复杂度是 $O\left(n{\log }_{2}n\right)$ 。 $\mathrm{B}$ 的最高阶是 $n^2$ ,时间复杂度是 $O\left(n^2\right)$ 。C 的最高阶是 $n{\log }_{2}n$ ,时间复杂度是 $O\left(n{\log }_{2}n\right)$ 。D 的最高阶是 ${\log }_{2}n$ ,时间复杂度是 $O\left({\log }_{2}n\right)$ 。

05 . D
找出基本运算 $\mathrm{i}=\mathrm{i}\ast 2$ ,设执行次数为 $t,2^t\le n$ ,即 $t\le {\log }_{2}n$ ,故时间复杂度 $T\left(n\right)=O\left({\log }_{2}n\right)$ 。

更直观的方法: 计算基本运算 $i=i\ast 2$ 的执行次数 (每执行一次 $i$ 乘以 2),其中判断条件可理解为 $2^t=n$ ,即 $t={\log }_{2}n$ ,则 $T\left(n\right)=O\left({\log }_{2}n\right)$ 。

06. C

基本运算为 i++ ,设执行次数为 $t$ ,有 $t\times t\times t\le n$ ,即 $t^3\le n$ 。因此有 $t\le \sqrt[3]{n}$ ,则 $T\left(n\right)=O\left(\sqrt[3]{n}\right)$ 。

07. D
这是冒泡排序的算法代码, 考查最坏情况下的元素交换次数 (若觉得理解困难, 则可在学完第 8 章后再回顾)。当所有相邻元素都为逆序时, 则最后一行的语句每次都会执行。此时,

$$T\left(n\right)=\sum _{i=2}^{n-1}\sum _{j=1}^{i-1}1=\sum _{i=2}^{n-1}i-1=\left(n-2\right)\left(n-1\right)/2=O\left(n^2\right)$$

所以在最坏情况下该语句的频度是 $O\left(n^2\right)$ 。

08. A
当程序段中有条件判断语句时, 取分支路径上的最大时间复杂度。

09. A
m++ 语句的执行次数为

$$\sum _{i=1}^n\sum _{j=1}^{2i}1=\sum _{i=1}^{n}2i=2\sum _{i=1}^{n}i=n\left(n+1\right)$$

10. C
本题求的是递归调用的时间复杂度, 递归调用可视为多重循环, 每次递归执行的基本语句是 if(n == 1) return 1 ;,因此可认为单层循环的执行次数为 1,设递归次数为 $t,2^t\le n$ ,即 $t\le {\log }_{2}n$ , 共执行了 ${\log }_{2}n$ 次递归调用,总执行次数 $T={\log }_{2}n\times 1$ ,所以时间复杂度为 $O\left({\log }_{2}n\right)$ 。

循环变量i	单层循环	单层循环执行次数
n	if(n==1) return 1;	1
n/2	if(n==1) return 1;	1
n/4	if(n==1) return 1;	1
...	...	...
1	if(n==1) return 1;	1

11. A
基本运算 (执行频率最高的语句) 为 $x=2\ast x$ ,每执行一次, $x$ 乘以 2,设执行次数为 $t$ ,则有 $2^{t+1}<n/2$ ,所以 $t<{\log }_2\left(n/2\right)-1={\log }_{2}n-2$ ,得 $T\left(n\right)=O\left({\log }_{2}n\right)$ 。

12. B
本题求的是递归调用的时间复杂度, 递归调用可视为多重循环, 每次递归执行的基本语句是 if(n < 1) return 1 ;,因此可认为单层循环的执行次数为 1,共执行了 $n$ 次递归调用,总执行次数 $T=1+1+\cdots +1=n$ ,所以时间复杂度为 $O\left(n\right)$ 。

循环变量i	单层循环语句	单层循环执行次数
n	if(n<=1) return 1;	1
n-1	if(n<=1) return 1;	1
n-2	if(n<=1) return 1;	1
...	...	...
1	if(n<=1) return 1;	1

13. C
对于单层循环如 for(j=1;j<=n;j++) sum++; 可以直接数出执行次数为 $n$ ,因此可将多层循环转换成多个并列的单层循环,且列出每个单层循环如下 (假设 $t$ 为循环变量的幂次):

循环变量k	单层循环语句	单层循环执行次数
1	for(j=1;j<=n;j++)	n
$2^1$	for(j=1;j<=n;j++)	n
$2^2$	for(j=1;j<=n;j++)	n
...	...	...
$2^t$	for(j=1;j<=n;j++)	n

进入外层循环的条件是 $k\le n$ ,当循环结束时,循环变量的幂次 $t$ 满足 $2^t\le n<2^{t+1}$ ,即 $t\le {\log }_{2}n$ 。 所以总执行次数 $T=n\left(t+1\right)=n\left({\log }_{2}n+1\right)$ ,时间复杂度为 $O\left(n{\log }_{2}n\right)$ 。

14. B
基本运算为 sum+=++i ,等价于 ++i; sum=sum+i,每执行一次, i 都自增 1 。当 i = 1 时,sum = 0+1 ; 当 i = 2 时, sum = 0+1+2 ; 当 i = 2 时, sum = 0+1+2+3 ,以此类推,得出 sum=0+1+2+3+...+i=(1+i)×i/2,可知循环次数 $t$ 满足 $\left(1+t\right)\times t/2<n$ ,故时间复杂度为 $O\left(n^{1/2}\right)$ 。

【注 意】统考真题中常将 ${\log }_2$ 书写为 $\log$ ,此时默认底数为 2 。

15 . B
假设第 $k$ 次循环终止,则第 $k$ 次执行时, ${(x+1)}^2>n,x$ 的初始值为 0,第 $k$ 次判断时, $x=k-1$ , 即 $k^2>n,k>\sqrt{n}$ ,因此该程序段的时间复杂度为 $O\left(\sqrt{n}\right)$ 。

16 . B
对于单层循环如 for(j=0;j<=i;j++) sum++; ,可以直接数出执行次数为 $i$ ,因此可将多层循环转换成多个并列的单层循环,且列出每个单层循环如下 (假设 $t$ 为循环变量的幂次):

循环变量k	单层循环语句	单层循环执行次数
1	for(j=0;j<=1;j++)	1
$2^1$	for(j=0;j<=2;j++)	2
$2^2$	for(j=0;j<=4;j++)	4
...	...	...
$2^t$	for(j=0;j<=$2^t$;j++)	$2^t$

进入外层循环的条件是 i < n ,当循环结束时,循环变量的幂次 $t$ 满足 $2^t<n\le 2^{t+1}$ 。总执行次数 $T=1+2^1+2^2+\cdots +2^t=2^{t+1}-1$ ,即 $n-1\le T$ 且 $T<2n-1$ ,所以时间复杂度为 $O\left(n\right)$ 。

二、综合应用题

01 .【解答】

① 基本语句 $\mathrm{k}=\mathrm{k}+10\ast \mathrm{i}$ 共执行了 $n-2$ 次,所以 $T\left(n\right)=O\left(n\right)$ 。

② 设循环体共执行 $t$ 次,每循环一次,循环变量 $y$ 加 1,最终 $t=y$ 。故 $t^2\le n$ ,得 $T\left(n\right)=O\left(n^{1/2}\right)$ 。

③ 内循环执行 $m$ 次,外循环执行 $n$ 次,根据乘法原理,共执行了 $m\times n$ 次,故 $T\left(m,n\right)=O\left(m\times n\right)$ 。