Lecture 2：算法和算法评价

2.1 算法和算法评价

2.1.1 什么是算法

定义：#算法

描述：算法是解决特定问题的一系列有限步骤。

解释

“程序＝数据结构＋算法”是常用助记表达，强调数据组织与处理步骤共同决定程序的核心逻辑，并非严格数学恒等式。 $$ \text{程序}=\text{数据结构}+\text{算法} $$
数据结构是要处理的信息。
算法是处理信息的步骤。
数据结构偏向“数据如何组织”，算法偏向“问题如何求解”。

理解

如果把做饭看成程序：
- 食材和调料 -> 数据结构；
- 做饭步骤 -> 算法；
- 最终能执行的菜谱流程 -> 程序。

2.1.2 算法的五个特性

核心

一个算法通常需要满足五个特性：
- 有穷性；
- 确定性；
- 可行性；
- 输入；
- 输出。

2.1.2.1 有穷性

定义：#有穷性

描述：算法必须在执行有穷步之后结束。

解释

算法不能无限执行下去。
需要注意：程序可以是无穷执行的。
- 比如操作系统、服务器程序、事件循环程序；
- 它们可以一直运行，但这不代表算法本身可以没有终止条件。

2.1.2.2 确定性

定义：#确定性

描述：算法中的每条指令必须有确切含义，对于相同输入只能得到相同输出。

解释

同一个算法在相同输入下，不应该出现不同结果。
算法步骤不能含糊，比如“适当处理一下”就不是严格算法描述。

2.1.2.3 可行性

定义：#可行性

描述：算法中描述的操作，都可以通过已经实现的基本运算执行有限次来完成。

解释

算法不能只停留在想象中。
每一步都必须是计算机或执行者可以完成的操作。

2.1.2.4 输入

定义：#输入

描述：一个算法有零个或多个输入，这些输入来自某个特定对象集合。

解释

算法可以没有外部输入。
- 比如固定输出一句话的算法。
但多数算法需要输入数据。

2.1.2.5 输出

定义：#输出

描述：一个算法有一个或多个输出，这些输出是与输入存在某种特定关系的量。

解释

算法必须产生结果。
如果一个过程没有任何输出，也无法体现问题是否被解决。

2.1.3 好算法的性质

四个标准

正确性；
可读性；
健壮性；
高效率与低存储量需求。

2.1.3.1 正确性

定义：#正确性

描述：算法应能够正确地解决求解问题。

解释

正确性是最基本要求。
如果算法结果错误，时间复杂度再低也没有意义。

2.1.3.2 可读性

定义：#可读性

描述：算法应具有良好的可读性，便于人们理解、检查和维护。

解释

数据结构算法题中，代码不是越短越好，而是要清楚表达思路。
面试或考试中，清晰的伪代码通常比晦涩的技巧更稳。

2.1.3.3 健壮性

定义：#健壮性

描述：当输入非法数据时，算法能够适当地做出反应或处理，而不会产生莫名其妙的输出结果。

解释

健壮性强调异常情况处理。
例如：
- 空表；
- 越界下标；
- 空指针；
- 非法输入；
- 除数为 0。

2.1.3.4 高效率与低存储量需求

定义：#效率

描述：好算法应尽可能时间复杂度低、空间复杂度低。

解释

高效率：运行时间尽量少。
低存储量：额外占用空间尽量少。
实际写题时，常常需要在时间和空间之间做权衡。

2.2 算法的时间复杂度

2.2.1 时间复杂度的概念

定义：#时间复杂度

描述：时间复杂度用于事前预估算法时间开销 $T(n)$ 与问题规模 $n$ 之间的增长关系。

解释

$T$ 表示 time，即算法时间开销。
$n$ 表示问题规模。
时间复杂度不精确计算程序运行多少秒，而是看输入规模变大时，时间开销如何增长。

注意

分析时间复杂度时，可以只考虑最高阶部分。
常数项和低阶项通常可以忽略。
例如： $$ T(n)=3n^2+10n+100 $$ 则时间复杂度为： $$ T(n)=O(n^2) $$

2.2.2 大 O 表示法

定义：#大O表示法

描述：若存在正常数 $c$ 和 $n_0$，使得对任意 $n\ge n_0$ 都有 $0\le T(n)\le c f(n)$，则记作 $T(n)=O(f(n))$。大 O 给出渐近上界，不要求 $T(n)$ 与 $f(n)$ 同阶。

公式 $$ T(n)=O(f(n)) $$

严格定义为： $$ T(n)=O(f(n)) \Longleftrightarrow \exists c>0,\exists n_0,\forall n\ge n_0: 0\le T(n)\le c f(n) $$

与 $\Theta$ 的区别

若存在 $0<k<\infty$，使 $$ \lim_{n\to\infty}\frac{T(n)}{f(n)}=k, $$ 则可以推出 $T(n)=\Theta(f(n))$，也就一定有 $T(n)=O(f(n))$。
反过来不成立。例如 $n=O(n^2)$，但 $n\ne\Theta(n^2)$。

教材补充：$O$、$\Omega$ 与 $\Theta$

记号	含义	形式化条件
$O(f(n))$	渐近上界	最终有 $0\le T(n)\le c_2f(n)$
$\Omega(f(n))$	渐近下界	最终有 $0\le c_1f(n)\le T(n)$
$\Theta(f(n))$	渐近紧界	最终有 $0\le c_1f(n)\le T(n)\le c_2f(n)$

其中 $c_1,c_2$ 为正常数。因此 $T(n)=\Theta(f(n))$ 当且仅当它同时属于 $O(f(n))$ 和 $\Omega(f(n))$。算法的“最坏情况”描述输入实例上的最大代价，而“大 $O$”描述函数增长的上界，两者不是同一个概念；最好、平均、最坏代价函数都可以分别使用 $O/\Omega/\Theta$。

理解

大 O 关心增长的渐近上界，常数倍和低阶项不影响常用的紧上界表达。因此： $$ 3n^2+10n+100=O(n^2) $$
同一函数可以有多个大 O 上界，例如 $n=O(n)$ 也有 $n=O(n^2)$；算法分析通常希望给出尽可能紧的上界，常写成 $\Theta$ 级别。

2.3 时间复杂度的运算规则

2.3.1 加法规则

定义：#加法规则

描述：多项相加时，只保留最高阶的项，并且系数变为 1。

公式 $$ \begin{aligned} T(n) &=T_1(n)+T_2(n)\ &=O(f(n))+O(g(n))\ &=O(\max(f(n),g(n))) \end{aligned} $$

解释

顺序执行的多段代码，时间复杂度相加。
最终只保留增长最快的一项。

例子 $$ O(n)+O(n^2)=O(n^2) $$

2.3.2 乘法规则

定义：#乘法规则

描述：多项相乘时，各项都要保留。

公式 $$ \begin{aligned} T(n) &=T_1(n)\times T_2(n)\ &=O(f(n))\times O(g(n))\ &=O(f(n)\times g(n)) \end{aligned} $$

解释

嵌套循环常常使用乘法规则。
外层循环执行 $n$ 次，内层循环执行 $n$ 次，则总次数为： $$ n\times n=n^2 $$ 所以时间复杂度为： $$ O(n^2) $$

2.3.3 常见数量级

从小到大 $$ O(1)<O(\log_2 n)<O(n)<O(n\log_2 n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) $$

记忆

常数阶：$O(1)$。
对数阶：$O(\log n)$。
线性阶：$O(n)$。
线性对数阶：$O(n\log n)$。
平方阶：$O(n^2)$。
指数阶：$O(2^n)$。
阶乘阶：$O(n!)$。

2.4 时间复杂度分析方法

2.4.1 基本分析原则

三条规则

1. 顺序执行的各段代码应先把复杂度相加，再由增长最快的项决定总数量级；顺序结构不一定只影响常数项。
1. 选择能代表主要开销的基本操作，计算其执行次数与 $n$ 的关系；必要时要分别计算不同操作。
1. 嵌套循环应根据各层真实边界求总执行次数。边界相互独立时常用乘法；若内层边界依赖外层变量，通常需要求和，不能只机械地看最深层。

理解

时间复杂度分析不是逐行算时间，而是找“增长最快”的部分。
循环、递归和嵌套结构通常是重点。

2.4.2 例题 1：二层嵌套循环

题型：#嵌套循环复杂度

第一部分：解题方法

外层循环若执行 $n$ 次；
内层循环每次也执行 $n$ 次；
总执行次数为： $$ n\times n=n^2 $$

第二部分：典型例题

PDF 中给出的关系： $$ T(n)=O(n)+O(n^2)=O(n^2) $$

解释

$O(n)$ 可以看作外层循环或其他线性操作；
$O(n^2)$ 可以看作二层嵌套循环；
根据加法规则，只保留最高阶项： $$ O(n)+O(n^2)=O(n^2) $$

第三部分：知识点复盘

嵌套循环优先考虑乘法规则。
多段顺序代码优先考虑加法规则。
最终结果只保留最高阶。

2.4.3 例题 2：每次倍增的循环

题型：#对数复杂度

第一部分：解题方法

如果循环变量每次乘以 2，循环次数通常是对数级。
核心判断： $$ 2^x>n $$
因此： $$ x>\log_2 n $$
时间复杂度为： $$ O(\log_2 n) $$

第二部分：典型例题

PDF 中给出的代码形式：

void function(int n)
{
    int i = 0;
    while(i <= n)
    {
        i *= 2;
        // 操作
    }
}

注意

这段代码如果严格写成 i = 0 且 i *= 2，那么 $i$ 永远是 0，会死循环。
这里应理解为 PDF/OCR 或原示例存在问题，常见正确写法应为：

void function(int n)
{
    int i = 1;
    while(i <= n)
    {
        i *= 2;
        // 操作
    }
}

分析

假设循环执行 $x$ 次。
每次循环后，$i$ 变为原来的 2 倍。
当： $$ 2^x>n $$ 循环终止。
因此： $$ x=\log_2 n $$
时间复杂度： $$ O(\log_2 n) $$

第三部分：知识点复盘

只要循环变量按倍数增长，常见复杂度就是对数级。
常见形式：
- i *= 2
- i *= 3
- i /= 2
底数不同不影响大 O 数量级，因此通常写作： $$ O(\log n) $$

2.4.4 三种时间复杂度

分类

最坏时间复杂度；
平均时间复杂度；
最好时间复杂度。

说明

一般情况下，408 中主要计算：
- 最坏时间复杂度；
- 平均时间复杂度。
最好时间复杂度通常不作为主要计算对象。
题目未说明时要结合教材语境：许多数据结构操作习惯给出最坏复杂度，但有些题会明确要求平均、最好或期望复杂度，不能一律替换为最坏情况。

2.5 空间复杂度

2.5.1 空间复杂度的概念

定义：#空间复杂度

描述：空间复杂度用于估计算法执行过程中，额外存储空间随问题规模 $n$ 增长的关系。

解释

时间复杂度看“运行多久”。
空间复杂度看“额外占多少存储空间”。
常用记号： $$ S(n)=O(f(n)) $$

2.5.2 普通程序的空间复杂度计算

题型：#普通程序空间复杂度

第一部分：解题方法

1. 找到所占空间大小与问题规模相关的变量。
1. 分析所占空间 $x$ 与问题规模 $n$ 的关系： $$ x=f(n) $$
1. $x$ 的数量级就是算法空间复杂度： $$ S(n)=O(x) $$

第二部分：典型例子

如果开辟数组：

int a[n];

数组大小与 $n$ 成正比，所以空间复杂度为： $$ S(n)=O(n) $$

第三部分：知识点复盘

只计算与问题规模相关的额外空间。
固定数量的变量通常只贡献 $O(1)$。

2.5.3 递归程序的空间复杂度计算

题型：#递归空间复杂度

第一部分：解题方法

递归程序需要考虑递归调用栈。
基本思路：
- 1. 找到递归调用深度 $x$ 与问题规模 $n$ 的关系；
- 1. 分析每一层递归需要多少额外空间；
- 1. 将各层空间开销相加；
- 1. 取数量级作为空间复杂度。

如果每一层空间相同

若递归深度为 $n$，每层只使用常数空间，则： $$ S(n)=O(n) $$

如果每一层空间不同

不能只看递归深度；
需要把每一层空间开销求和。

第二部分：典型例题

PDF 中给出的代码：

void function(int n, int breakNumber = 0)
{
    int numbers[n];
    if(n > breakNumber)
    {
        function(n - 1);
    }
}

NOTE · 原例是复杂度分析用的伪代码原 PDF 把 C++ 风格的默认参数 int breakNumber = 0 与 C99 的变长数组 int numbers[n] 混写；还会递归到 n=0，在停止判断前声明零长度数组。这段代码不能当作标准 C 或标准 C++ 源码直接照搬。以下只按“有效递归层依次分配长度 $n,n-1,\ldots,1$ 的数组”这一模型计算峰值空间；若写成可运行程序，应先判断边界，再分配数组。

分析

每次递归都会开辟一个数组：

int numbers[n];

第一次调用数组长度为 $n$；
第二次调用数组长度为 $n-1$；
第三次调用数组长度为 $n-2$；
一直到数组长度接近 1。

空间开销

只看数组部分： $$ S(n)=n+(n-1)+(n-2)+\cdots+1 $$
求和： $$ S(n)=\frac{n(n+1)}{2} $$
展开： $$ S(n)=\frac{1}{2}n^2+\frac{1}{2}n $$
所以空间复杂度为： $$ S(n)=O(n^2) $$

补充

如果把函数调用栈、函数元信息等也计算进去，每一层还会有常数级额外开销。
递归深度为 $n$，这部分开销为： $$ O(n) $$
但 $O(n)$ 低于 $O(n^2)$，所以最终空间复杂度仍然是： $$ O(n^2) $$

第三部分：知识点复盘

普通递归不一定都是 $O(n)$。
如果每层递归额外空间不同，就要逐层求和。
这道题的关键不是递归深度，而是每层都开了一个不同长度的数组。

2.6 本节复盘

必须掌握

算法的五个特性：
- 有穷性；
- 确定性；
- 可行性；
- 输入；
- 输出。
好算法的四个性质：
- 正确性；
- 可读性；
- 健壮性；
- 高效率与低存储量需求。
时间复杂度： $$ T(n)=O(f(n)) $$
空间复杂度： $$ S(n)=O(f(n)) $$

常考点

加法规则： $$ O(f(n))+O(g(n))=O(\max(f(n),g(n))) $$
乘法规则： $$ O(f(n))\times O(g(n))=O(f(n)g(n)) $$
常见数量级： $$ O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) $$

易错点

程序可以无限运行，但算法必须有穷。
大 O 表示渐近上界；“比值趋于正常数”描述的是 $\Theta$ 级别。
多层嵌套循环要按真实循环边界计数，不能只看语法上的最深层。
倍增循环通常是 $O(\log n)$。
递归空间复杂度不仅要看递归深度，还要看每层额外空间。

做题顺序

1. 先找问题规模 $n$；
1. 再找基本操作；
1. 分析基本操作执行次数；
1. 保留最高阶；
1. 写成大 O 形式。

2.1 算法和算法评价

2.1.1 什么是算法

定义：#算法

2.1.2 算法的五个特性

2.1.2.1 有穷性

定义：#有穷性

2.1.2.2 确定性

定义：#确定性

2.1.2.3 可行性

定义：#可行性

2.1.2.4 输入

定义：#输入

2.1.2.5 输出

定义：#输出

2.1.3 好算法的性质

2.1.3.1 正确性

定义：#正确性

2.1.3.2 可读性

定义：#可读性

2.1.3.3 健壮性

定义：#健壮性

2.1.3.4 高效率与低存储量需求

定义：#效率

2.2 算法的时间复杂度

2.2.1 时间复杂度的概念

定义：#时间复杂度

2.2.2 大 O 表示法

定义：#大O表示法

2.3 时间复杂度的运算规则

2.3.1 加法规则

定义：#加法规则

2.3.2 乘法规则

定义：#乘法规则

2.3.3 常见数量级

2.4 时间复杂度分析方法

2.4.1 基本分析原则

2.4.2 例题 1：二层嵌套循环

题型：#嵌套循环复杂度

第一部分：解题方法

第二部分：典型例题

第三部分：知识点复盘

2.4.3 例题 2：每次倍增的循环

题型：#对数复杂度

第一部分：解题方法

第二部分：典型例题

第三部分：知识点复盘

2.4.4 三种时间复杂度

2.5 空间复杂度

2.5.1 空间复杂度的概念

定义：#空间复杂度

2.5.2 普通程序的空间复杂度计算

题型：#普通程序空间复杂度

第一部分：解题方法

第二部分：典型例子

第三部分：知识点复盘

2.5.3 递归程序的空间复杂度计算

题型：#递归空间复杂度

第一部分：解题方法

第二部分：典型例题

第三部分：知识点复盘

相关知识

2.6 本节复盘