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$

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

理解

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

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. 找到所占空间大小与问题规模相关的变量。
• 2. 分析所占空间 $x$ 与问题规模 $n$ 的关系： $$ x=f(n) $$
• 3. $x$ 的数量级就是算法空间复杂度： $$ S(n)=O(x) $$

第二部分：典型例子

• 如果开辟数组：

int a[n];

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

第三部分：知识点复盘

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

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

题型：#递归空间复杂度

第一部分：解题方法

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

如果每一层空间相同

• 若递归深度为 $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$；
• 2. 再找基本操作；
• 3. 分析基本操作执行次数；
• 4. 保留最高阶；
• 5. 写成大 O 形式。