【算法设计与分析】开学课前预习全攻略：从算法基本概念到时间/空间复杂度分析（万字详解，含例题精讲与考点总结）

在这里插入图片描述

📌 写在前面：新学期《算法设计与分析》课程即将开始，很多同学一听到"算法分析"四个字就头皮发麻。其实，这门课的第一章内容——算法的基本概念、算法的五大特征、渐进符号（大O、大Ω、大Θ）、时间复杂度与空间复杂度分析——是整个课程的地基。地基打牢了，后面学分治、贪心、动态规划、回溯、分支限界都会事半功倍。

本文基于教材第一章的知识点，按照"概念回顾 → 例题精讲 → 错误剖析 → 方法总结 → 考点提炼"的脉络，把课前预习内容完整地梳理了一遍。全文配有代码、公式推导、对比表格和易错点提示，适合预习、复习和考前突击使用。建议收藏后慢慢消化。👇

一、概述：为什么要学算法

在正式进入新知识之前，我们先回忆一下：算法的定义、算法的基本步骤，这些内容其实我们在《数据结构》课程中都学过。也就是说，算法设计与分析这门课并不是从零开始，而是站在数据结构的肩膀上，把"如何设计一个好算法、如何评价一个算法的好坏"这两件事讲得更系统、更数学化。

为什么值得专门开一门课来研究算法？因为在实际软件开发中，我们经常遇到这样的场景：

同一个问题，甲写出来的程序跑1秒，乙写出来的程序跑1小时——差距在哪里？算法。
数据量从1万条涨到100万条，原来的程序突然"跑不动"了——为什么？复杂度增长的阶不同。
面试时手写代码，面试官问"你这个解法的时间复杂度是多少？能不能优化？"——考的还是算法分析能力。

所以，学习这门课的第一个心态转变是：不要只满足于"能写出来、能跑通"，而要追求"写得好、跑得快、说得清"。"说得清"就是指你能用渐进符号准确地分析出自己算法的时间复杂度和空间复杂度，这是区分"码农"和"工程师"的重要分水岭。

二、算法的概念与正确性

2.1 算法的定义

算法（Algorithm）：算法是求解问题的一系列算法步骤，用来将输入数据转换成输出结果。

这个定义中有三个关键词：

一系列步骤——算法是有序的、可执行的指令序列，不是一句空泛的思想；

输入数据——算法处理的原材料；

输出结果——算法要交付的成品。

一句话概括：算法 = 从输入到输出的确定性变换过程。

2.2 算法的正确性

如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是正确的。

注意这里有两个条件，缺一不可：

条件含义反例

结果正确	对任何合法输入，输出都符合问题要求	查找算法把第3个元素错报成第2个
能够停止	算法必须在有限步内结束，不能死循环	while(1) 里永远满足的条件

⚠️ 特别注意："每一个输入实例"是全称量词。一个算法只要存在哪怕一个输入使它输出错误结果或者无法终止，它就不是正确的算法。这就是为什么我们测试程序时要设计边界用例（空输入、极端值、非法值）——因为魔鬼往往藏在边界里。

2.3 算法质量的评价维度

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于：选择合适的算法 + 改进已有算法。

对一个算法的评价，主要从两个维度考虑：

时间复杂度：算法执行所需时间随问题规模增长的趋势；
空间复杂度：算法执行所需存储空间随问题规模增长的趋势。

这两个维度将在本文第12节之后详细展开，它们是本课程第一章的核心，也是期末考试的重中之重。

三、算法设计应追求的六大目标

教材中指出，算法设计应当追求满足以下目标，而不是只知道概念——只知道概念而不动手实践，永远不会进步：

正确性、可使用性、可读性、健壮性、高效率、低存储量需求

我们逐条解释：

3.1 正确性（Correctness）

算法必须能够正确解决问题，对合法的输入产生符合要求的输出。这是最基本的要求，一个结果错误的算法，跑得再快也是废物。

3.2 可使用性（Usability）

算法应当便于使用，接口清晰，使用者不需要了解内部实现细节就能正确调用。比如函数的参数含义明确、返回值约定清楚、有使用文档或注释。

3.3 可读性（Readability）

代码首先是写给人看的，其次才是给机器执行的。命名规范、结构清晰、适当注释的算法，便于他人理解、维护和修改。一个谁也看不懂的"炫技"代码，在团队协作中是负资产。

3.4 健壮性（Robustness）

当输入非法数据或出现意外情况（如空指针、除零、越界）时，算法能做出恰当的反应或进行处理，而不是莫名其妙地崩溃。健壮性要求我们写代码时时刻思考：“如果这里出错了怎么办？”

3.5 高效率（High Efficiency）

指算法执行速度快，即时间复杂度低。

3.6 低存储量需求（Low Storage Requirement）

指算法占用的内存少，即空间复杂度低。

💡 记忆口诀：“正可读写健，高效低存储”——正确性、可使用性、可读性、健壮性、高效率、低存储量需求。

⚠️ 注意一个常见的考试陷阱：高效率与低存储量往往不可兼得（典型的"空间换时间"或"时间换空间"的权衡，trade-off）。例如哈希表查找是 O(1) 时间，但需要额外 O(n) 空间；而直接遍历是 O(1) 空间，但需要 O(n) 时间。算法设计的艺术，很大程度上就是在这些目标之间做取舍。

四、【例1-1】单链表查找算法的错误分析（经典例题）

这道例题是"六大目标"中正确性与健壮性的活教材，几乎每年都会被拿来当分析题考，务必吃透。

4.1 题目描述

以下算法用于在带头结点的单链表 h 中查找第一个值为 x 的结点，找到后返回其逻辑序号（从1计起），否则返回0。分析该算法存在的问题。

int findx(LNode *h; int x)
{
LNode *p = h->next;
int i = 0;
while (p->data != x)
{
i++;
p = p->next;
}
return i;
}

4.2 问题诊断

结论先行：该算法不满足正确性和健壮性。具体有两个致命问题：

问题（1）：初值错误，违反正确性

当单链表中首结点（第一个数据结点）的值就是 x 时：

进入循环前，p 指向首结点，i = 0；
循环条件 p->data != x 不成立，直接跳过循环体；
return i，返回 0。

但按照题意，首结点的逻辑序号应当是 1！返回值错误，这就是正确性问题。

问题（2）：循环条件缺少判空，违反健壮性

当单链表中不存在值为 x 的结点时：

循环会一路走到底，p 最终变成 NULL；
但循环条件 p->data != x 仍然会去解引用 p，也就是对空指针执行 p->data 和 p = p->next；
结果是非法内存访问，程序直接崩溃。

这就是健壮性问题——算法没有对"查不到"这种完全可能发生的情况做出恰当处理。

4.3 改正后的代码

int findx(LNode *h; int x)
{
LNode *p = h->next;
int i = 1; // ① 初值改为1
while (p != NULL && p->data != x) // ② 循环条件先判空
{
i++;
p = p->next;
}
if (p == NULL) // ③ 区分查找成功/失败
return 0;
else
return i;
}

4.4 错误分析要点（考试答题模板）

初值错误：i 初始写成 0。第一个有效结点的逻辑序号是1，i 应当初始化为 1。这样若第一个结点就是 x，循环不执行，直接返回 i = 1，得到正确序号。

循环条件缺少判空：原来写的是 while(p->data != x)，没有判断 p != NULL。链表找不到 x 时，p 会变成 NULL，再访问 p->data 会造成空指针访问，程序崩溃。循环条件必须写成 p != NULL && p->data != x，利用 && 的短路求值特性：一旦 p == NULL，后半部分不会再执行。

没有区分查找成功/失败：原代码无论如何都直接 return i。正确做法是循环结束后判断：p == NULL 说明遍历完整个链表都没找到，应返回 0；否则说明找到了，返回当前序号 i。

4.5 举一反三：这类题的通用检查清单

以后凡是拿到一段"找茬"代码，可以按以下清单逐项排查：

✅ 循环变量的初值对不对？（差一错误，off-by-one）
✅ 循环条件有没有边界保护（判空、判越界）？
✅ 短路求值的顺序对不对？（必须先判 p != NULL 再判 p->data，顺序反了照样崩）
✅ 成功和失败两种路径的返回值是否都符合题意？
✅ 带头结点的链表，p 应该从 h->next 开始（头结点不存数据，序号从1计）——这一点原代码是对的，别误伤。

五、算法的五大特征（Knuth定义）

算法设计的先驱者唐纳德·E·克努特（Donald E. Knuth）——《计算机程序设计艺术》(TAOCP) 的作者、图灵奖得主、TeX排版系统的创造者——给出了算法的五个经典特征：

5.1 有穷性（Finiteness）

一个算法所包含的计算步骤是有限的。

也就是说，算法必须在执行有限步之后结束，不能陷入永无休止的死循环。注意：程序不一定有穷（比如操作系统是个无限循环的程序），但算法必须有穷。这是算法与程序的重要区别之一。

5.2 确定性（Definiteness）

算法执行的每一个步骤必须有确切的定义，不能有模棱两可的情况。

例如"把 x 加上一个足够大的数"就不是确定的描述——多大算"足够大"？而"x = x + 5"是确定的。确定性要求每条指令都有唯一、清晰的含义，同样的输入永远走同样的路径、得同样的结果。

5.3 数据输入（Input）

一个算法有零个或多个数据输入。

注意是"零个或"——有的算法不需要外部输入（比如打印前100个素数），输入可以内嵌在算法之中。

5.4 数据输出（Output）

一个算法有一个或多个数据输出，没有输出的算法是没有意义的。

输入可以是零个，但输出至少一个。算法的目的就是加工数据产出结果，什么都不输出的"算法"做了无用功。

5.5 可行性（Effectiveness / Feasibility）

每个步骤都可以在有限时间内完成。

也翻译为"有效性"。算法中的每一个操作都必须是可执行的基本操作，能够在有限时间内完成。除以零、开负数的实数平方根、调用一个不存在的硬件功能——这些都是不可行的操作。

5.6 速记总结

特征一句话记忆关键词

✅ 有穷性	步骤执行有限次后必须结束	不能死循环
✅ 确定性	每一步定义明确，无歧义	不能模棱两可
✅ 输入	0个或多个输入	可以为零
✅ 输出	1个或多个输出	至少一个
✅ 可行性	每个操作都能在有限时间内完成	不能除零

⚠️ 高频考点辨析：有穷性 vs 可行性怎么区分？

有穷性关注的是整体：整个算法的步骤总数有限，最终会停下来；
可行性关注的是单步：每一步操作本身是可执行的、能在有限时间内完成的。
死循环 → 违反有穷性；除以零这种根本执行不了的操作 → 违反可行性。

六、案例：求 6x+5y+4z=50 的正整数解

下面用一个具体的数学问题，体会用自然语言（步骤化描述）来表达一个算法是什么感觉。

6.1 问题

\\boldsymbol{6x+5y+4z=50}

$6 x + 5 y + 4 z = 50$ 有多少组正整数解？

6.2 数学分析：确定枚举边界

由于 x, y, z 都是正整数（

≥

x, y, z \\ge 1

$x, y, z \geq 1$ ），且各项都是正数，所以每一项都必须小于50：

$\\Rightarrow x \\le 8 6x<50⇒x≤8，但因为 5 y + 4 z ≥ 5 + 4 = 9 5y+4z \\ge 5+4=9 5y+4z≥5+4=9，实际上 6 x ≤ 41 6x \\le 41 6x≤41，即 x ≤ 6 x \\le 6 x≤6；$
同理 $\\Rightarrow y \\le 9 5y<50⇒y≤9，考虑 6 x + 4 z ≥ 10 6x+4z \\ge 10 6x+4z≥10，有 5 y ≤ 40 5y \\le 40 5y≤40，即 y ≤ 8 y \\le 8 y≤8；$
$\\Rightarrow z \\le 12 4z<50⇒z≤12，考虑 6 x + 5 y ≥ 11 6x+5y \\ge 11 6x+5y≥11，有 4 z ≤ 39 4z \\le 39 4z≤39，即 z ≤ 9 z \\le 9 z≤9。$

教材采用的边界为：

⇒

≤

6x<50 \\Rightarrow x\\le6

$6 x < 50 \Rightarrow x \leq 6$ ；

⇒

≤

5y<50 \\Rightarrow y\\le8

$5 y < 50 \Rightarrow y \leq 8$ ；

⇒

≤

4z<50 \\Rightarrow z\\le9

$4 z < 50 \Rightarrow z \leq 9$ 。（这里已经隐含扣除了另外两项的最小取值，保证不遗漏解。）

6.3 算法的自然语言描述（穷举法）

①

;

\\boldsymbol{t=0;}

$t = 0;$ （t 用于统计解的个数） ②

;

\\boldsymbol{x=1;}

$x = 1;$ ③

;

\\boldsymbol{y=1;}

$y = 1;$ ④

;

\\boldsymbol{z=1;}

$z = 1;$ ⑤ 如果满足式子

\\boldsymbol{6x+5y+4z=50}

$6 x + 5 y + 4 z = 50$ ，则解的个数加1（

\\boldsymbol{t=t+1}

$t = t + 1$ ），并输出这个解（输出 x, y, z 的值）； ⑥

;

\\boldsymbol{z=z+1;}

$z = z + 1;$ ⑦ 如果

≤

\\boldsymbol{z \\le 9}

$z \leq 9$ ，则转步骤⑤，否则继续⑧； ⑧

;

\\boldsymbol{y=y+1;}

$y = y + 1;$ ⑨ 如果

≤

\\boldsymbol{y \\le 8}

$y \leq 8$ ，则转步骤④，否则继续⑩； ⑩

;

\\boldsymbol{x=x+1;}

$x = x + 1;$ ⑪ 如果

≤

\\boldsymbol{x \\le 6}

$x \leq 6$ ，则转步骤③，否则继续⑫； ⑫ 结束。

6.4 算法结构解读

这段自然语言描述本质上是一个三重嵌套循环的穷举（暴力枚举）算法：

最外层循环枚举 x（1→6），中层循环枚举 y（1→8），最内层循环枚举 z（1→9）；
每换一个 y，z 要重新从1开始（步骤⑨转回步骤④）；每换一个 x，y 要重新从1开始（步骤⑪转回步骤③）——这正是嵌套循环"内层重置"的语义；
内层每枚举一组 (x, y, z)，就验证一次等式，成立则计数并输出。

如果翻译成 C 语言，就是：

#include <stdio.h>

int main()
{
int t = 0; // 解的个数
for (int x = 1; x <= 6; x++) // 枚举x
for (int y = 1; y <= 8; y++) // 枚举y
for (int z = 1; z <= 9; z++) // 枚举z
if (6*x + 5*y + 4*z == 50)
{
t++;
printf("x=%d, y=%d, z=%d\\n", x, y, z);
}
printf("共有%d组正整数解\\n", t);
return 0;
}

6.5 思考：这个描述符合算法五大特征吗？

有穷性 ✅：x 最多6种、y 最多8种、z 最多9种取值，总验证次数不超过 6×8×9 = 432 次，必然结束；
确定性 ✅：每一步（赋值、比较、转移）都有确切定义；
输入 ✅：零个输入（问题参数内嵌在算法中）；
输出 ✅：输出每组解及解的总数 t；
可行性 ✅：加法、乘法、比较都是基本可执行操作。

所以这是一个合格的算法。它虽然"笨"（穷举），但简单、清晰、必然正确——在问题规模小的时候，穷举法往往是最稳妥的选择。这也体现了算法设计中"先保证正确，再追求高效"的一般原则。

6.6 能否有其他描述方法？

当然可以！算法是对解题过程的精确描述，且需要使用某种方法将其表示出来。描述算法的常用方法有三种：

自然语言：如上面的①~⑫步骤，优点是通俗易懂，缺点是冗长、容易产生歧义、不方便表示分支嵌套；

流程图：用图形符号（起止框、处理框、判断框、流程线）直观表示执行流程，优点是形象直观，缺点是绘制麻烦、修改不便、大型算法的流程图会非常复杂；

伪代码：介于自然语言和程序设计语言之间，用类似编程语言的语法但不拘泥于细节，优点是结构清晰、简洁、便于转化为真实代码，是教材和论文中最常用的算法描述方式。

同一个穷举算法用伪代码可以写成：

Algorithm Enumerate()
t ← 0
for x ← 1 to 6 do
for y ← 1 to 8 do
for z ← 1 to 9 do
if 6x + 5y + 4z = 50 then
t ← t + 1
output(x, y, z)
output(t)

对比之下不难发现：伪代码把12个自然语言步骤压缩成了不到10行，且循环嵌套结构一目了然。这就是为什么要学伪代码——它是算法世界的"通用语"。

七、欧几里得算法（辗转相除法）与特征辨析

7.1 算法描述

在《几何原本》一书中，欧几里得（Euclid）阐述了求两个正整数最大公约数（GCD）的过程，这就是著名的欧几里得算法——辗转相除法。它是人类历史上最古老的算法之一（约公元前300年），至今仍是教科书级的经典。

设给定的两个正整数为 m 和 n，求它们的最大公约数的步骤如下：

1、以 m 除以 n，令所得的余数为 R。 2、若 R=0，则输出结果 n，算法结束；否则，继续步骤3。 3、令 m=n，n=R，并返回步骤1继续进行。

用伪代码表示：

Algorithm gcd(m, n)
while n ≠ 0 do
R ← m mod n
m ← n
n ← R
return m

其数学原理是：

gcd

⁡

(

)

gcd

⁡

(

)

\\gcd(m, n) = \\gcd(n, m \\bmod n)

$g cd (m, n) = g cd (n, m mod n)$ 。不断用"除数、余数"替换"被除数、除数"，余数严格递减且非负，所以必然在有限步内变成0，此时的除数就是最大公约数。

7.2 特征辨析填空题（考试原题级）

题目1：在欧几里得算法中，步骤1明确规定"以 m 除以 n，令所得的余数为 R"，这体现了算法的 ____ 特征。

答案：确定性。解析：步骤1对"做什么"（m除以n）、“结果叫什么”（余数记为R）都给出了确切的定义，没有任何模棱两可的地方——谁除以谁、余数如何命名都规定得清清楚楚，这正是确定性的体现。

题目2：在欧几里得算法中，步骤2"若 R=0，则输出结果 n，算法结束；否则，继续步骤3"，表明这个算法有结果输出，并且有结束条件，这体现了算法的 ____ 和 ____ 特征。

答案：数据输出、有穷性。解析："输出结果 n"对应数据输出特征（算法有至少一个输出）；"算法结束"给出了明确的终止条件，余数序列严格递减保证了一定能到达 R=0 从而停机，对应有穷性特征。

题目3：欧几里得算法的三个步骤都是可以在有限时间内完成的，都是可执行的操作步骤，这体现了算法的 ____ 特征。

答案：可行性。解析：求余、赋值、比较、跳转，每一步都是可以在有限时间内完成的基本操作，这正是可行性的定义。

7.3 答题技巧总结

这类"给一段算法描述，问体现了哪些特征"的题目，抓关键词即可：

描述中的关键词对应特征

“明确规定”“确切定义”“不含糊”	确定性
“算法结束”“终止条件”“有限步”	有穷性
“输出结果”“打印”“返回”	数据输出
“输入m和n”“给定数据”	数据输入
“可以在有限时间内完成”“可执行的操作”	可行性

八、【例1-2】违反算法特征的两段代码

8.1 题目

有下列两段描述，它们均不能满足算法的特征，试问它们违反了算法的哪些特征？

描述1：

void exam1()
{
int n;
n = 2;
while (n % 2 == 0)
n = n + 2;
printf("%d\\n", n);
}

描述2：

void exam2()
{
int x, y;
y = 0;
x = 5 / y;
printf("%d,%d\\n", x, y);
}

8.2 考点解析

描述1：违反有穷性 🔍

追踪一下执行过程：

初始 n = 2，2 % 2 == 0 成立，进入循环；
n = n + 2 = 4，4 % 2 == 0 仍然成立，继续循环；
n = 6, 8, 10, …，n 永远是偶数，循环条件永远成立；
printf 那一行永远执行不到，算法无法终止。

一个永远停不下来的"算法"违反了有穷性（有限性）特征。

描述2：违反可行性 🔍

y = 0，接着执行 x = 5 / y，即除以零；
除以零在数学上没有定义，在计算机上是非法操作（会触发运行时错误/异常，程序崩溃）；
也就是说，这个步骤不是可以在有限时间内完成的可执行操作。

因此描述2违反了可行性特征。

8.3 标准解答

解：（1）描述1是一个死循环（n 初始为偶数2，每次加2仍为偶数，循环条件 n%2==0 恒成立），永远不会执行循环体之后的输出语句，违反了算法的有穷性特征。

（2）描述2中 y=0，执行 x=5/y 时出现除零错误，该操作不可执行，违反了算法的可行性特征。

8.4 对比记忆

描述1描述2

表面现象	死循环	除零崩溃
违反特征	有穷性	可行性
本质区别	每一步都能执行，但整体停不下来	某一步根本无法执行

再次强调前面提到的辨析要点：有穷性看整体（能否终止），可行性看单步（能否执行）。这两段代码恰好是一对绝佳的对比样例，考试经常成对出现，务必记牢。

九、描述算法的三种常用方法（展开）

前面已经提到，描述算法的常用方法有三种，这里再系统展开一下，方便大家做简答题：

9.1 自然语言

优点：通俗易懂，不需要任何编程基础；
缺点：文字冗长，容易产生歧义（违反确定性的风险），分支和循环嵌套层次多时描述困难；
适用场景：向非专业人员解释算法思想，或像"6x+5y+4z=50"这种步骤简单的算法。

9.2 流程图

基本符号：
- 圆角矩形（椭圆）：开始/结束框；
- 矩形：处理框（执行操作）；
- 菱形：判断框（条件分支，两个出口"是/否"）；
- 箭头（流程线）：表示执行顺序；
- 平行四边形：输入/输出框。
优点：形象直观，流程一目了然；
缺点：绘制和修改麻烦，复杂算法的流程图庞大难读，且流程图是"图形"而非"文本"，不便于版本管理和传播；
适用场景：教学演示、简单流程的业务说明。

9.3 伪代码

特点：借用程序设计语言的骨架（if/else、for/while、赋值、函数调用），但不受具体语言语法约束，可以用数学符号和自然语言混排；
优点：结构清晰、简洁紧凑、突出算法逻辑、屏蔽语言细节、易于翻译成任何一门编程语言；
缺点：没有统一标准，不同教材写法略有差异；对完全不懂编程的人不友好；
适用场景：教材、学术论文、算法竞赛题解——这是本课程后续章节的主要描述工具，建议从现在开始就练习书写规范的伪代码。

十、用C/C++描述算法的一般形式

10.1 求 1+2+…+n 的算法

以设计求

⋯

\\boldsymbol{1+2+\\cdots+n}

$1 + 2 + \dots + n$ 值的算法为例，说明 C/C++ 语言描述算法的一般形式。其核心约定是：

用函数的返回值表示算法能否正确执行（如 bool：true 表示成功，false 表示失败）；
用形参表示算法的输入输出（输入型形参传数据进来，输出型形参把结果带出去）。

教材给出的算法框架如下：

bool fun(int n, int s) // 返回值：算法是否正确执行；形参：n为输入，s为输出
{
if (n < 0) return false; // 非法输入，算法执行失败
s = 0;
for (int i = 1; i <= n; i++)
s += i; // 累加求和
return true; // 正常完成，返回true
}

void main()
{
int a = 10, b = 0;
if (fun(a, b)) printf("%d\\n", b);
else printf("参数错误\\n");
}

标注说明：

bool 返回值 → 表示算法执行状态（成功/失败）；
形参列表 (int n, int s) → n 是输入参数，s 意图作为输出参数。

10.2 ⚠️ 一个值得深挖的细节：值传递的陷阱

细心的同学可能已经发现：上面 fun(int n, int s) 中，s 是值传递的普通形参。函数内部 s = 0; s += i; 修改的只是实参 b 的一份副本，函数返回后 main 中的 b 依然是 0！也就是说，这段代码虽然形式上演示了"用形参表示输入输出"，但输出并没有真正带回去。

要想让 s 真正作为输出参数，应改用引用传递：

bool fun(int n, int &s) // s改为引用类型
{
if (n < 0) return false;
s = 0;
for (int i = 1; i <= n; i++)
s += i;
return true;
}

这样 main 中的 b 才会被赋值为 55（当 a=10 时）。

💡 预习启示：这个细节恰好呼应了第4节例1-1的教训——"形参/返回值的设计"直接决定算法的正确性。教材在后续章节（如时间复杂度分析中的 Solve(double a[][MAX], int m, int n, double &s)）就规范地使用了引用参数 double &s。大家在写代码时务必分清：值传递传副本，引用传递传本体，指针传递传地址。

10.3 C/C++描述算法的一般形式总结

一个规范的算法函数应当包含：

函数名：见名知义（如 Find、maxelem、mergesort）；

形参列表：输入参数在前，输出参数在后（输出参数用引用或指针）；

返回值：可以携带结果，也可以像 bool 一样只表示执行状态；

函数体：边界/非法输入检查 → 核心计算 → 返回结果；

必要的注释：说明算法功能、参数含义、复杂度等。

十一、算法与数据结构的联系与区别

这是一道经典的简答题，教材的表述是"既有联系又有区别"：

11.1 联系

数据结构是算法设计的基础。算法的操作对象是数据结构，在设计算法时，要构建适合这种算法的数据结构。数据结构设计主要是选择数据的存储方式，如确定求解问题中的数据采用数组存储还是采用链表存储等。算法设计就是在选定的存储结构上设计一个满足要求的好算法。

举个例子体会一下：同样是"查找"操作——

数据用有序数组存储 → 可以设计二分查找算法，O(log n)；
数据用单链表存储 → 只能顺序查找，O(n)，因为链表不支持随机访问；
数据用哈希表存储 → 平均 O(1) 查找。

存储结构的选择直接决定了你能设计出什么样的算法、算法能达到什么样的效率。这就是"数据结构是算法设计的基础"的含义。著名科学家沃斯（Niklaus Wirth）的名言"程序 = 数据结构 + 算法"说的正是这种密不可分的关系。

11.2 区别

数据结构关注的是数据的逻辑结构、存储结构以及基本操作；而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。

维度数据结构算法

研究对象	数据本身：逻辑结构（线性/树形/图形）、存储结构（顺序/链式/索引/散列）、基本运算	解决问题的步骤与方法：如何加工数据得到答案
回答的问题	“数据怎么组织、怎么存？”	“问题怎么解、解得好不好？”
角色定位	思想的逻辑基础（静态骨架）	编程思想（动态灵魂）

11.3 求解问题的完整流程

教材给出了用计算机求解问题的一般流程图：

分析求解问题
↓
选择数据结构和算法设计策略
↓
描述算法
↓
证明算法正确性
↓
算法分析

这五步是一个方法论闭环：

分析求解问题：弄清输入是什么、输出是什么、约束条件有哪些；

选择数据结构和算法设计策略：决定数据怎么存（数组？链表？树？），用什么策略解（穷举？分治？贪心？动态规划？）——后面章节学的各种设计策略就用在一步；

描述算法：用自然语言/流程图/伪代码/程序语言把算法写出来；

证明算法正确性：论证对一切合法输入算法都给出正确输出（数学归纳法是常用工具）；

算法分析：计算时间复杂度和空间复杂度，评价算法优劣，必要时回到第2步改进。

十二、1.2 算法的分析：时间复杂度概述

从这里开始进入本章的核心计算部分——算法分析。

12.1 什么是算法分析

算法分析是分析算法占用计算机资源的情况，主要是分析算法的时间复杂度和空间复杂度。

时间复杂度：算法运行时间随问题规模 n 增长的渐进趋势；
空间复杂度：算法占用存储空间随问题规模 n 增长的渐进趋势。

为什么不直接测量"运行了多少秒"？因为实际运行时间受机器性能、编译器优化、操作系统调度等太多因素影响，同一算法在不同机器上时间不同。算法分析要的是与机器无关的、本质性的度量——这就是渐进分析（Asymptotic Analysis）的思想：只关心当问题规模 n 趋向无穷大时，运行时间的增长阶。

12.2 算法运行时间的构成

算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，运行时间取决于两者的综合效果。

控制结构：顺序结构（依次执行）、分支结构（if/switch 选择执行）、循环结构（for/while 重复执行）——其中循环结构对运行时间的影响最大，时间复杂度分析的主战场就是数循环次数；
原操作：固有数据类型的操作，如整数的加减乘除、比较、赋值等，每个原操作的执行时间是常数级的。

看教材中的例子：

bool Solve(double a[][MAX], int m, int n, double &s)
{
int i;
s = 0;

if (m != n) return false; // 分支结构：非方阵直接失败

for (i = 0; i < m; i++) // 循环结构：执行m次
s += a[i][i]; // 原操作：累加主对角线元素

return true;
}

这个函数计算 m×n 矩阵主对角线元素之和：先检查是否为方阵（m≠n 则失败），然后循环 m 次累加 a[i][i]。它的运行时间由"1次比较 + m次循环（每次一个加法）"构成，即与 m 成正比，时间复杂度为 O(m)。

12.3 问题规模与基本语句

问题规模 n：指输入数据量的大小，如数组元素个数、矩阵阶数、图中顶点数等；
基本语句（基本操作）：算法中执行次数最多、对运行时间起决定性作用的语句，通常是最深层循环体内的语句。

分析时间复杂度，本质上就是：求出基本语句的执行次数 f(n)，再用渐进符号表示 f(n) 的阶。

12.4 分析算法时间复杂度的一般步骤

教材给出的标准流程：

算法
↓
分析问题规模n，找出基本语句，求出其运行次数 f(n)
↓
用 O、Ω 或 Θ 表示其阶
（上界、下界、准确界）

具体操作口诀（笔者总结）：

找：找到算法中最深层的循环，确定基本语句；

数：计算基本语句的执行次数，得到关于 n 的表达式 f(n)（可能需要用到求和公式）；

化：只保留 f(n) 的最高阶项，并去掉系数，用大O表示，即得时间复杂度。

常用求和公式（必须背熟）：

∑

(

)

∑

(

)

(

)

∑

−

\\sum_{i=1}^{n} i = \\frac{n(n+1)}{2}, \\qquad \\sum_{i=1}^{n} i^2 = \\frac{n(n+1)(2n+1)}{6}, \\qquad \\sum_{i=0}^{k} 2^i = 2^{k+1}-1

$i = 1 \sum n i = \frac{n ( n + 1 )}{2}, i = 1 \sum n i^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}, i = 0 \sum k 2^{i} = 2^{k + 1} - 1$

十三、渐进符号：大O、大Ω、大Θ 详解

渐进符号是算法分析的数学语言，共三种：大O（上界）、大Ω（下界）、大Θ（紧确界）。设 n 为算法中的问题规模，通常用大O、大Ω（Omega）和Θ（Theta）三种渐进符号表示算法的执行时间与 n 之间的一种增长关系。

13.1 定义1：大O符号（上界）

(

)

(

)

f(n) = O(g(n))

$f (n) = O (g (n))$ （读作"f(n)是g(n)的大O"）当且仅当存在正常量 c 和

n_0

$n_{0}$ ，使得当

≥

n \\ge n_0

$n \geq n_{0}$ 时，

(

)

≤

⋅

(

)

f(n) \\le c \\cdot g(n)

$f (n) \leq c \cdot g (n)$ ，即 g(n) 为 f(n) 的上界。

直观理解：只要 n 足够大（

≥

n \\ge n_0

$n \geq n_{0}$ ），f(n) 的图像总被 c·g(n) 的图像"压"在下面。也就是说，f(n) 的增长最多像 g(n) 那样快。

例子1：

(

)

3n+2 = O(n)

$3 n + 2 = O (n)$ 。证明思路：当

≥

n \\ge 2

$n \geq 2$ 时，

≤

3n+2 \\le 3n+n = 4n

$3 n + 2 \leq 3 n + n = 4 n$ 。取

c=4, n_0=2

$c = 4, n_{0} = 2$ 即可。✅

例子2：

(

)

10n^2+4n+2 = O(n^4)

$10 n^{2} + 4 n + 2 = O (n^{4})$ 。证明思路：当

≥

n \\ge 2

$n \geq 2$ 时，

≤

10n^2+4n+2 \\le 10n^4

$10 n^{2} + 4 n + 2 \leq 10 n^{4}$ （因为

≤

n^2 \\le n^4

$n^{2} \leq n^{4}$ ，

≤

4n \\le n^4

$4 n \leq n^{4}$ ，

≤

2 \\le n^4

$2 \leq n^{4}$ 均成立，加起来不超过

10n^4+…

$10 n^{4} + \dots$ ，教材直接给出该放缩）。取

c=10, n_0=2

$c = 10, n_{0} = 2$ 即可。✅

关于"紧凑上界"（紧确上界）：

大O符号用来描述增长率的上界，表示 f(n) 的增长最多像 g(n) 增长的那样快，即当输入规模为 n 时，算法消耗时间的最大值。这个上界的阶越低，结果就越有价值。所以对于

10n^2+4n+2

$10 n^{2} + 4 n + 2$ ，

(

)

O(n^2)

$O (n^{2})$ 比

(

)

O(n^4)

$O (n^{4})$ 有价值。

一个算法的时间用大O符号表示时，总是采用最有价值的 g(n) 表示，称之为 “紧凑上界” 或 “紧确上界” 。

多项式的通用结论：

一般地，如果

(

)

−

⋯

f(n) = a_m n^m + a_{m-1} n^{m-1} + \\cdots + a_1 n + a_0

$f (n) = a_{m} n^{m} + a_{m - 1} n^{m - 1} + \dots + a_{1} n + a_{0}$ （

a_m > 0

$a_{m} > 0$ ），则

(

)

(

)

f(n) = O(n^m)

$f (n) = O (n^{m})$ 。

推导记忆法：多项式的渐进阶 = 最高次项的阶，系数和低次项全部扔掉。例如

(

)

100

f(n)=5n^3+100n^2+n+7

$f (n) = 5 n^{3} + 100 n^{2} + n + 7$ ，则

(

)

(

)

f(n)=O(n^3)

$f (n) = O (n^{3})$ 。

13.2 定义2：大Ω符号（下界）

(

)

(

)

f(n) = \\Omega(g(n))

$f (n) = Ω (g (n))$ （读作"f(n)是g(n)的大Ω"）当且仅当存在正常量 c 和

n_0

$n_{0}$ ，使得当

≥

n \\ge n_0

$n \geq n_{0}$ 时，

(

)

≥

⋅

(

)

f(n) \\ge c \\cdot g(n)

$f (n) \geq c \cdot g (n)$ ，即 g(n) 为 f(n) 的下界。

直观理解：只要 n 足够大，f(n) 的图像总被 c·g(n) "托"在上面。f(n) 的增长至少像 g(n) 那样快。

例子1：

(

)

3n+2 = \\Omega(n)

$3 n + 2 = Ω (n)$ 。证明思路：当

≥

n \\ge 1

$n \geq 1$ 时，

≥

3n+2 \\ge 3n

$3 n + 2 \geq 3 n$ 。取

c=3, n_0=1

$c = 3, n_{0} = 1$ 即可。✅

例子2：

(

)

10n^2+4n+2 = \\Omega(n^2)

$10 n^{2} + 4 n + 2 = Ω (n^{2})$ 。证明思路：当

≥

n \\ge 1

$n \geq 1$ 时，

≥

10n^2+4n+2 \\ge 10n^2 \\ge n^2

$10 n^{2} + 4 n + 2 \geq 10 n^{2} \geq n^{2}$ 。取

c=1, n_0=1

$c = 1, n_{0} = 1$ 即可。✅

关于"紧凑下界"（紧确下界）：

大Ω符号用来描述增长率的下界，表示 f(n) 的增长最少像 g(n) 增长的那样快，也就是说，当输入规模为 n 时，算法消耗时间的最小值。

与大O符号对称：这个下界的阶越高，结果就越有价值。所以对于

10n^2+4n+2

$10 n^{2} + 4 n + 2$ ，

(

)

\\Omega(n^2)

$Ω (n^{2})$ 比

(

)

\\Omega(n)

$Ω (n)$ 有价值。一个算法的时间用大Ω符号表示时，总是采用最有价值的 g(n) 表示，称之为 “紧凑下界” 或 “紧确下界”。

⚠️ 注意方向相反：大O要"越低越有价值"（上界越低说明卡得越紧），大Ω要"越高越有价值"（下界越高说明卡得越紧）。可以想象两个夹子从上下两边夹 f(n)：夹得越紧，信息量越大。

多项式的通用结论：

一般地，如果

(

)

−

⋯

f(n) = a_m n^m + a_{m-1} n^{m-1} + \\cdots + a_1 n + a_0

$f (n) = a_{m} n^{m} + a_{m - 1} n^{m - 1} + \dots + a_{1} n + a_{0}$ （

a_m > 0

$a_{m} > 0$ ），则

(

)

(

)

f(n) = \\Omega(n^m)

$f (n) = Ω (n^{m})$ 。

13.3 定义3：大Θ符号（同阶/紧确界）

(

)

(

)

f(n) = \\Theta(g(n))

$f (n) = Θ (g (n))$ （读作"f(n)是g(n)的大Θ"）当且仅当存在正常量

c_1

$c_{1}$ 、

c_2

$c_{2}$ 和

n_0

$n_{0}$ ，使得当

≥

n \\ge n_0

$n \geq n_{0}$ 时，有

⋅

(

)

≤

(

)

≤

⋅

(

)

c_1 \\cdot g(n) \\le f(n) \\le c_2 \\cdot g(n)

$c_{1} \cdot g (n) \leq f (n) \leq c_{2} \cdot g (n)$ ，即 g(n) 与 f(n) 同阶。

直观理解：f(n) 被上下两条 c·g(n) 曲线夹在中间——增长既不比 g(n) 快，也不比 g(n) 慢，二者"同速增长"。

例子：

(

)

3n+2 = \\Theta(n)

$3 n + 2 = Θ (n)$ ；

(

)

10n^2+4n+2 = \\Theta(n^2)

$10 n^{2} + 4 n + 2 = Θ (n^{2})$ 。

多项式的通用结论：

一般地，如果

(

)

−

⋯

f(n) = a_m n^m + a_{m-1} n^{m-1} + \\cdots + a_1 n + a_0

$f (n) = a_{m} n^{m} + a_{m - 1} n^{m - 1} + \dots + a_{1} n + a_{0}$ （

a_m > 0

$a_{m} > 0$ ），则

(

)

(

)

f(n) = \\Theta(n^m)

$f (n) = Θ (n^{m})$ 。

三者的关系：

大Θ符号比大O符号和大Ω符号都精确。

(

)

(

)

f(n) = \\Theta(g(n))

$f (n) = Θ (g (n))$ 当且仅当 g(n) 既是 f(n) 的上界（

(

)

(

)

f(n)=O(g(n))

$f (n) = O (g (n))$ ）又是 f(n) 的下界（

(

)

(

)

f(n)=\\Omega(g(n))

$f (n) = Ω (g (n))$ ）。

即：

∩

\\Theta = O \\cap \\Omega

$Θ = O \cap Ω$ 。

13.4 三种渐进符号对比表（背诵版）

符号名称数学定义（n≥n₀时）直观含义界的方向价值取向

	大O	$\\le c\\,g(n) f(n)≤cg(n)$	增长率上界，最多这么快	上界	阶越低越有价值（紧凑上界）
$\\Omega Ω$	大Ω	$\\ge c\\,g(n) f(n)≥cg(n)$	增长率下界，至少这么快	下界	阶越高越有价值（紧凑下界）
$\\Theta Θ$	大Θ	$c_1 g(n) \\le f(n) \\le c_2 g(n) c1g(n)≤f(n)≤c2g(n)$	同阶，不快不慢刚刚好	上下夹逼	最精确，O与Ω同时成立

13.5 常见函数增长阶排序（必须烂熟于心）

(

)

(

log

⁡

)

(

)

(

log

⁡

)

(

)

(

)

(

)

(

)

(

)

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 (1) < O (lo g n) < O (n) < O (n lo g n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!) < O (n^{n})$

复杂度名称典型算法举例n=10⁶ 时的感受

	常数阶	数组按下标访问、入栈出栈	瞬间
$O(\\log n) O(logn)$	对数阶	二分查找	约20次操作，瞬间
	线性阶	顺序查找、遍历数组	百万次操作，毫秒级
$O(n\\log n) O(nlogn)$	线性对数阶	归并排序、快速排序（平均）、堆排序	千万级操作，秒级以内
$O(n^2) O(n2)$	平方阶	简单选择/插入/冒泡排序、双重循环	万亿次操作，小时级，不可接受
$O(n^3) O(n3)$	立方阶	三重循环、朴素矩阵乘法	完全不可接受
$O(2^n) O(2n)$	指数阶	子集枚举、朴素斐波那契递归	n=30就爆炸
	阶乘阶	全排列枚举、TSP暴力解法	n=15就爆炸

💡 实践意义：一般认为

(

log

⁡

)

O(n\\log n)

$O (n lo g n)$ 及以下是"高效算法"，

(

)

O(n^2)

$O (n^{2})$ 在 n 较大时已经吃力，指数阶/阶乘阶算法只对极小规模问题可行（这类问题往往属于NP难问题，这正是课程后面章节要讨论的内容）。

十四、【例1-3】三重循环时间复杂度分析（含完整推导）

14.1 题目

分析以下算法的时间复杂度：

void fun(int n)
{
int s = 0, i, j, k;
for (i = 0; i <= n; i++)
for (j = 0; j <= i; j++)
for (k = 0; k < j; k++)
s++;
}

14.2 分析过程

第一步：找基本语句。该算法的基本语句是 s++——它位于最内层循环体中，执行次数最多。

第二步：数执行次数 f(n)。三层循环的边界相互依赖：i 从 0 到 n；对每个 i，j 从 0 到 i；对每个 j，k 从 0 到 j−1。因此 s++ 的总执行次数为三重求和：

(

)

∑

−

f(n)=\\sum_{i=0}^{n}\\sum_{j=0}^{i}\\sum_{k=0}^{j-1}1

$f (n) = i = 0 \sum n j = 0 \sum i k = 0 \sum j - 1 1$

第三步：由内向外逐层化简。

最内层：

∑

−

\\sum_{k=0}^{j-1}1 = j-1-0+1 = j

$\sum_{k = 0}^{j - 1} 1 = j - 1 - 0 + 1 = j$ （k 从 0 数到 j−1，共 j 次）。

(

)

∑

f(n)=\\sum_{i=0}^{n}\\sum_{j=0}^{i} j

$f (n) = i = 0 \sum n j = 0 \sum i j$

中间层用求和公式

∑

(

)

\\sum_{j=0}^{i} j = \\dfrac{i(i+1)}{2}

$\sum_{j = 0}^{i} j = \frac{i ( i + 1 )}{2}$ ：

(

)

∑

(

)

(

∑

)

f(n)=\\sum_{i=0}^{n}\\frac{i(i+1)}{2}=\\frac{1}{2}\\left(\\sum_{i=0}^{n}i^2+\\sum_{i=0}^{n}i\\right)

$f (n) = i = 0 \sum n \frac{i ( i + 1 )}{2} = \frac{1}{2} (i = 0 \sum n i^{2} + i = 0 \sum n i)$

代入公式

∑

(

)

(

)

\\sum_{i=0}^{n} i^2 = \\dfrac{n(n+1)(2n+1)}{6}

$\sum_{i = 0}^{n} i^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ 和

∑

(

)

\\sum_{i=0}^{n} i = \\dfrac{n(n+1)}{2}

$\sum_{i = 0}^{n} i = \frac{n ( n + 1 )}{2}$ ：

(

)

⋅

(

)

(

)

⋅

(

)

(

)

(

)

(

)

(

)

(

)

f(n)=\\frac{1}{2}\\cdot\\frac{n(n+1)(2n+1)}{6}+\\frac{1}{2}\\cdot\\frac{n(n+1)}{2} =\\frac{n(n+1)(2n+1)}{12}+\\frac{3n(n+1)}{12} =\\frac{n(n+1)(2n+4)}{12} =\\frac{2n^3+6n^2+4n}{12}

$f (n) = \frac{1}{2} \cdot \frac{n ( n + 1 ) ( 2 n + 1 )}{6} + \frac{1}{2} \cdot \frac{n ( n + 1 )}{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{12} + \frac{3 n ( n + 1 )}{12} = \frac{n ( n + 1 ) ( 2 n + 4 )}{12} = \frac{2 n ^{3} + 6 n ^{2} + 4 n}{12}$

第四步：取阶。只保留最高阶项

2n^3/12

$2 n^{3} /12$ ，去掉系数得：

(

)

(

)

f(n) = O(n^3)

$f (n) = O (n^{3})$

结论：该算法的时间复杂度为

(

)

\\boldsymbol{O(n^3)}

$O (n^{3})$ 。

14.3 技巧点拨

其实对于这种题目，不必精确求和也可以快速判断：最内层执行次数量级不超过 $\\sim n^3 (n+1)(n+1)(n+1)∼n3，且当 i、j 取较大值时内层确实执行 Θ(n) 次，故总次数为 Θ(n³)。但考试中若要求"分析"，最好写出求和推导过程；$
注意本题 j 循环是 j <= i、k 循环是 k < j，边界各不相同，逐层写清求和上下限是避免出错的关键；
常见的三层"三角形"循环（i:0..n, j:0..i, k:0..j）答案同样是 O(n³)，只是常数不同——渐进分析不在乎常数。

十五、算法的最好、最坏和平均情况

同一个算法，面对不同的输入，执行时间可能大相径庭。例如排序算法：输入已经有序时可能只扫一遍，输入逆序时可能要跑满所有循环。因此需要分三种情况讨论。

15.1 形式化定义（定义4）

设一个算法的输入规模为 n，

D_n

$D_{n}$ 是所有输入的集合，任一输入

∈

I \\in D_n

$I \in D_{n}$ ，

(

)

P(I)

$P (I)$ 是 I 出现的概率，有

∑

(

)

\\sum P(I) = 1

$\sum P (I) = 1$ ；

(

)

T(I)

$T (I)$ 是算法在输入 I 下所执行的基本语句次数，则该算法的平均执行时间为：

(

)

∑

∈

(

)

⋅

(

)

A(n)=\\sum_{I \\in D_n} P(I) \\cdot T(I)

$A (n) = I \in D_{n} \sum P (I) \cdot T (I)$

算法的平均情况指各种特定输入下的基本语句执行次数的带权平均值（权就是各输入出现的概率）。

最好情况（Best Case）：

(

)

∈

{

(

)

}

G(n)=\\mathrm{MIN}_{I \\in D_n}\\{T(I)\\}

$G (n) = MIN_{I \in D_{n}} {T (I)}$

指算法在所有输入 I 下所执行基本语句的最少次数。

最坏情况（Worst Case）：

(

)

∈

{

(

)

}

W(n)=\\mathrm{MAX}_{I \\in D_n}\\{T(I)\\}

$W (n) = MAX_{I \in D_{n}} {T (I)}$

指算法在所有输入 I 下所执行基本语句的最大次数。

15.2 三种情况的意义

情况记号数学定义工程意义

最好情况	G(n)	所有输入中 T(I) 的最小值	乐观估计；通常参考价值不大（好运气可遇不可求）
最坏情况	W(n)	所有输入中 T(I) 的最大值	性能保证：系统绝不会再比这更慢；实时系统、安全敏感场景必须看最坏情况
平均情况	A(n)	T(I) 按概率的带权平均	最贴近实际运行表现；但概率分布往往难以确定，计算也更复杂

⚠️ 考试常考概念题：三种情况是对同一算法在不同输入下的分析，而不是"三种不同的算法"；最坏情况是上界保证，平均情况需要已知输入的概率分布。

十六、【例1-4】顺序查找的三种情况分析（重点+难点）

16.1 题目

采用顺序查找方法，在长度为 n 的一维实型数组 a[0..n-1] 中查找值为 x 的元素：从数组的第一个元素开始，逐个与被查值 x 进行比较，找到后返回1，否则返回0。对应算法如下：

int Find(double a[], int n, double x)
{
int i = 0;
while (i < n)
{
if (a[i] == x) break; // 基本语句
i++;
}
if (i < n) return 1; // 查找成功
else return 0; // 查找失败
}

回答以下问题：

(1) 分析该算法在等概率情况下成功查找到值为 x 的元素的最好、最坏和平均时间复杂度。

(2) 假设被查值 x 在数组 a 中的概率是 q（即查找成功的概率为 q，失败概率为 1−q），求算法的（平均）时间复杂度。

16.2 第(1)问解答

算法 while 循环中的 if 语句是基本语句（比较 a[i]==x 的次数决定运行时间）。数组 a 中有 n 个元素：

最好情况：当第一个元素 a[0] 就等于 x 时，基本语句仅执行 1 次，此时呈现最好的情况：

(

)

(

)

G(n) = O(1)

$G (n) = O (1)$

最坏情况：当 a 中最后一个元素 a[n-1] 才等于 x 时，基本语句执行 n 次，此时呈现最坏的情况：

(

)

(

)

W(n) = O(n)

$W (n) = O (n)$

平均情况（成功查找、等概率）：假设查找每个元素的概率相同，则

(

[

]

)

(

≤

−

)

P(a[i]) = \\dfrac{1}{n} \\ (0 \\le i \\le n-1)

$P (a [i]) = \frac{1}{n} (0 \leq i \leq n - 1)$ ，而成功找到 a[i] 元素时基本语句正好执行 i+1 次（比较了 a[0]、a[1]、…、a[i] 共 i+1 次），所以：

(

)

∑

−

(

)

∑

−

(

)

⋅

(

)

(

)

A(n)=\\sum_{i=0}^{n-1}\\frac{1}{n}(i+1)=\\frac{1}{n}\\sum_{i=0}^{n-1}(i+1)=\\frac{1}{n}\\cdot\\frac{n(n+1)}{2}=\\frac{n+1}{2}=O(n)

$A (n) = i = 0 \sum n - 1 \frac{1}{n} (i + 1) = \frac{1}{n} i = 0 \sum n - 1 (i + 1) = \frac{1}{n} \cdot \frac{n ( n + 1 )}{2} = \frac{n + 1}{2} = O (n)$

结论：等概率成功查找下，顺序查找的最好情况为 O(1)，最坏情况为 O(n)，平均情况为

\\dfrac{n+1}{2}

$\frac{n + 1}{2}$ ，即 O(n)。平均比较次数约为最坏情况的一半。

16.3 第(2)问解答（考虑查找失败）

当被查值 x 在数组 a 中的概率为 q 时，算法执行共有 n+1 种情况：n 种成功查找（x 等于 a[0]…a[n-1] 中某一个）和 1 种不成功查找（x 不在数组中）。

成功查找：假设等概率，则元素 a[i] 被查找到的概率为 $\\dfrac{q}{n} P(a[i])=nq（总成功概率 q 均摊到 n 个元素上），成功找到 a[i] 时基本语句正好执行 i+1 次；$
不成功查找：其概率为 1−q，不成功查找时循环走完全程，基本语句正好执行 n 次（i 从 0 比较到 n−1 都不匹配，i<n 不成立退出）。

所以：

(

)

∑

∈

(

)

⋅

(

)

∑

−

(

)

(

−

)

(

)

(

−

)

A(n)=\\sum_{I \\in D_n} P(I)\\cdot T(I)=\\sum_{i=0}^{n-1}\\frac{q}{n}(i+1)+(1-q)\\,n=\\frac{(n+1)q}{2}+(1-q)n

$A (n) = I \in D_{n} \sum P (I) \cdot T (I) = i = 0 \sum n - 1 \frac{q}{n} (i + 1) + (1 - q) n = \frac{( n + 1 ) q}{2} + (1 - q) n$

特例：如果已知需要查找的 x 有一半的机会在数组中，即

q = 1/2

$q = 1/2$ ，则：

(

)

≈

A(n)=\\frac{n+1}{4}+\\frac{n}{2}\\approx \\frac{3n}{4}

$A (n) = \frac{n + 1}{4} + \frac{n}{2} \approx \frac{3 n}{4}$

结果解读：

当 q=1（一定查找成功）时， $A(n)=\\dfrac{n+1}{2}\\approx\\dfrac{n}{2} A(n)=2n+1≈2n；$
当 q=1/2 时， $A(n)\\approx\\dfrac{3n}{4} A(n)≈43n；$
当 q=0（一定失败）时，A(n)=n。

成功概率越低，平均比较次数越多——因为失败查找总要把整个数组扫完（n 次比较），是最"昂贵"的情形。这个结论非常符合直觉，也提醒我们：分析平均情况时必须把失败路径计入。

16.4 本例方法论总结

分析"三种情况"题目的标准套路：

确定基本语句（通常是最内层循环中的比较/赋值语句）；

最好情况：找让基本语句执行次数最少的输入（如首元素即命中）；

最坏情况：找让基本语句执行次数最多的输入（如末元素命中或根本不命中）；

平均情况：列出所有输入情形、各自概率 P(I) 和执行次数 T(I)，代入

A(n)=\\sum P(I)T(I) A(n)=∑P(I)T(I) 求和，用等差/等比数列公式化简；

注意区分"仅成功查找的平均"与"成功+失败混合的平均"——后者要把失败情形的概率 (1−q) 和次数 n 加进去。

十七、非递归算法的时间复杂度分析

17.1 方法概述

非递归算法（时间复杂度分析）的关键是求出代表算法执行时间的表达式 f(n)。

一般步骤：

找出基本语句（最内层循环体内的语句）；

设基本语句执行次数为 m，建立 m 与问题规模 n 的关系式（等式或不等式）；

解出 m 关于 n 的表达式 f(n)；

用渐进符号取其阶。

对于循环变量非线性变化（如 i += 2、i *= 2、i = i*i）的循环，这是最常考的题型，下面用例题示范。

17.2 【例1-5】

给出以下算法的时间复杂度：

void func(int n)
{
int i = 1, k = 100;
while (i <= n)
{
k++;
i += 2;
}
}

解：基本语句是 while 循环体内的语句（k++; i+=2;）。设其执行次数为 m。

追踪循环变量 i 的变化规律：i 从 1 开始，每次递增2，执行 m 次后，i 的取值为：

i = 1 + 2m

$i = 1 + 2 m$

循环继续的条件是

≤

i \\le n

$i \leq n$ ，因此有：

≤

⇒

≤

−

i = 1+2m \\le n \\;\\Rightarrow\\; m \\le \\frac{n-1}{2}

$i = 1 + 2 m \leq n \Rightarrow m \leq \frac{n - 1}{2}$

(

)

≤

−

(

)

f(n) = m \\le \\frac{n-1}{2} = O(n)

$f (n) = m \leq \frac{n - 1}{2} = O (n)$

该算法的时间复杂度为

(

)

O(n)

$O (n)$ 。

17.3 变式训练（预习自测）

掌握了例1-5的方法，下面几个经典变式应该都能秒答：

变式1：i = 1; while (i <= n) i = i * 2; 设执行 m 次后

≤

i = 2^m \\le n

$i = 2^{m} \leq n$ ，则

≤

log

⁡

m \\le \\log_2 n

$m \leq lo g_{2} n$ ，时间复杂度

(

log

⁡

)

O(\\log_2 n)

$O (lo g_{2} n)$ 。

变式2：i = 0; while (i*i <= n) i++; 设执行 m 次后

≤

m^2 \\le n

$m^{2} \leq n$ ，则

≤

m \\le \\sqrt{n}

$m \leq n$

，时间复杂度

(

)

O(\\sqrt{n})

$O (n$

)。

变式3：i = n; while (i > 1) i = i / 2; 设执行 m 次后

n/2^m > 1

$n / 2^{m} > 1$ ，则

log

⁡

m < \\log_2 n

$m < lo g_{2} n$ ，时间复杂度

(

log

⁡

)

O(\\log_2 n)

$O (lo g_{2} n)$ 。

变式4：双重循环，外层 for(i=0;i<n;i++)，内层 for(j=0;j<i;j++)，基本语句在内层。

(

)

∑

−

(

−

)

(

)

f(n)=\\sum_{i=0}^{n-1} i = \\dfrac{n(n-1)}{2} = O(n^2)

$f (n) = \sum_{i = 0}^{n - 1} i = \frac{n ( n - 1 )}{2} = O (n^{2})$ 。

💡 核心心法：不管循环变量怎么跳（+2、×2、÷2、平方），套路永远是——“设执行 m 次，写出第 m 次后循环变量的表达式，代入循环条件解出 m 关于 n 的上界”。

十八、递归算法的时间复杂度分析

18.1 方法概述

递归算法是采用一种分而治之的方法，把一个"大问题"分解为若干个相似的"小问题"来求解。

分析递归算法时间复杂度的关键是：根据递归过程建立递推关系式，然后求解这个递推关系式，得到一个表示算法执行时间的表达式，最后用渐进符号来表示这个表达式，即得到算法的时间复杂度。

标准四步法：

设规模为 n 的调用所需时间为 T(n)；

根据"递归调用的子问题规模与个数 + 除递归外的其他工作量"写出递推关系式（含初始条件）；

用迭代展开法（或主定理）求解递推式；

用大O表示结果。

18.2 【例1-6】归并排序的递推分析

题目：有以下递归算法：

void mergesort(int a[], int i, int j)
{
int m;
if (i != j)
{
m = (i + j) / 2;
mergesort(a, i, m); // 递归排序左半部分
mergesort(a, m + 1, j); // 递归排序右半部分
merge(a, i, j, m); // 合并两个有序子序列
}
}

mergesort() 用于数组 a[0..n-1]（设

n=2^k

$n = 2^{k}$ ，k 为正整数）的归并排序，调用方式为 mergesort(a, 0, n-1)；另外 merge(a, i, j, m) 用于两个有序子序列的有序合并，是非递归函数，它的时间复杂度为

(

)

O(n)

$O (n)$ （这里

−

n = j-i+1

$n = j - i + 1$ ，即当前处理的区间长度）。分析上述调用的时间复杂度。

解：设调用 mergesort(a, 0, n-1) 的执行时间为

(

)

T(n)

$T (n)$ 。由其执行过程（规模 n 的问题分解为两个规模 n/2 的子问题，加上一次 O(n) 的合并）得到以下求执行时间的递归关系（递推关系式）：

(

)

{

(

)

当

(

)

(

)

当

T(n)=\\begin{cases} O(1) & \\text{当 } n=1 \\\\ 2T(n/2)+O(n) & \\text{当 } n>1 \\end{cases}

$T (n) = {O (1) 2 T (n /2) + O (n) 当 n = 1 当 n > 1$

其中，

(

)

O(n)

$O (n)$ 为 merge() 所需的时间，设为 cn（c 为正常量）。下面用迭代展开法求解：

(

)

(

)

[

(

)

⋅

]

(

)

[

(

)

⋅

]

(

)

⋯

(

)

⋅

\\begin{align*} T(n) &= 2T(n/2)+cn \\\\ &= 2\\left[2T(n/2^2)+c\\cdot\\frac{n}{2}\\right]+cn = 2^2T(n/2^2)+2cn \\\\ &= 2^2\\left[2T(n/2^3)+c\\cdot\\frac{n}{2^2}\\right]+2cn = 2^3T(n/2^3)+3cn \\\\ &= \\cdots \\\\ &= 2^k T(n/2^k)+k\\cdot cn \\end{align*}

$T (n) = 2 T (n /2) + c n = 2 [2 T (n / 2^{2}) + c \cdot \frac{n}{2}] + c n = 2^{2} T (n / 2^{2}) + 2 c n = 2^{2} [2 T (n / 2^{3}) + c \cdot \frac{n}{2 ^{2}}] + 2 c n = 2^{3} T (n / 2^{3}) + 3 c n = \dots = 2^{k} T (n / 2^{k}) + k \cdot c n$

这里假设

n=2^k

$n = 2^{k}$ ，则

log

⁡

k=\\log_2 n

$k = lo g_{2} n$ 。当展开到

n/2^k = 1

$n / 2^{k} = 1$ 时，

(

)

(

)

T(1)=O(1)

$T (1) = O (1)$ ，代入得：

(

)

⋅

(

)

log

⁡

log

⁡

(

log

⁡

)

T(n) = 2^k \\cdot O(1) + cn\\log_2 n = n + cn\\log_2 n = O(n\\log_2 n)

$T (n) = 2^{k} \cdot O (1) + c n lo g_{2} n = n + c n lo g_{2} n = O (n lo g_{2} n)$

结论：归并排序的时间复杂度为

(

log

⁡

)

\\boldsymbol{O(n\\log_2 n)}

$O (n l o g_{2} n)$ 。

18.3 展开过程的规律观察

迭代展开中每一行的结构是"递归项 + 累计工作量"：

展开次数递归项累计非递归工作量

第1次
第2次	$2^2T(n/2^2) 22T(n/22)$
第3次	$2^3T(n/2^3) 23T(n/23)$
第k次	$2^kT(n/2^k) 2kT(n/2k)$

规律：每展开一层，递归项系数翻倍、规模减半，工作量累加一份 cn。展开 k 层后触底（

(

)

T(1)

$T (1)$ ），此时

2^k = n

$2^{k} = n$ ，总工作量

⋅

(

)

log

⁡

= n\\cdot O(1) + kcn = n + cn\\log_2 n

$= n \cdot O (1) + k c n = n + c n lo g_{2} n$ 。

也可以用递归树直观理解：树共

log

⁡

\\log_2 n + 1

$lo g_{2} n + 1$ 层，每一层所有节点的合并工作量之和都是 cn，故总工作量为

log

⁡

(

log

⁡

)

cn\\log_2 n + n = O(n\\log_2 n)

$c n lo g_{2} n + n = O (n lo g_{2} n)$ 。

18.4 拓展：主定理（预习加分项）

对于形如

(

)

(

)

(

)

T(n) = aT(n/b) + f(n)

$T (n) = a T (n / b) + f (n)$ 的递推式，主定理（Master Theorem）可以直接给出答案：

比较

(

)

f(n)

$f (n)$ 与

log

⁡

n^{\\log_b a}

$n^{l o g_{b} a}$ 的阶：

若

O(n^{\\log_b a – \\varepsilon}) f(n)=O(nlogb​a−ε)（ ε > 0 \\varepsilon>0 ε>0），则 T ( n ) = Θ ( n log ⁡ b a ) T(n)=\\Theta(n^{\\log_b a}) T(n)=Θ(nlogb​a)；

若

\\Theta(n^{\\log_b a}\\log^k n) f(n)=Θ(nlogb​alogkn)，则 T ( n ) = Θ ( n log ⁡ b a log ⁡ k + 1 n ) T(n)=\\Theta(n^{\\log_b a}\\log^{k+1} n) T(n)=Θ(nlogb​alogk+1n)；

若

\\Omega(n^{\\log_b a + \\varepsilon}) f(n)=Ω(nlogb​a+ε) 且满足正则条件，则 T ( n ) = Θ ( f ( n ) ) T(n)=\\Theta(f(n)) T(n)=Θ(f(n))。

对归并排序：a=2, b=2, f(n)=cn。

log

⁡

n^{\\log_2 2}=n^1=n

$n^{l o g_{2} 2} = n^{1} = n$ ，f(n)=Θ(n)，命中第2种情况（k=0），得

(

)

(

log

⁡

)

T(n)=\\Theta(n\\log n)

$T (n) = Θ (n lo g n)$ 。与迭代展开的结果一致。✅

预习阶段建议以迭代展开法为主（考试要求写过程），主定理作为快速验算工具。

18.5 常见递推式速查表

递推关系式解典型算法

		线性递归（求n!、表插入排序）
	$O(n^2) O(n2)$	每层做线性工作的递减递归
		二叉树遍历
	$O(n\\log n) O(nlogn)$	归并排序、快速排序（平均）
	$O(\\log n) O(logn)$	二分查找
		每层线性、规模减半（如选择问题的一种解法）
	$O(2^n) O(2n)$	汉诺塔

十九、空间复杂度分析

19.1 基本概念

一个算法的存储量包括形参所占空间和临时变量所占空间。在进行存储空间分析时，只考察临时变量所占空间。

为什么只算临时变量？因为输入数据本身占用的空间是问题固有的，不因算法而异；算法分析要衡量的是"算法本身额外需要多少空间"。

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模 n 的函数，以数量级形式给出，记作：

(

)

(

)

、

(

)

或

(

)

S(n)=O(g(n))、\\Omega(g(n)) \\text{ 或 } \\Theta(g(n))

$S (n) = O (g (n)) 、 Ω (g (n)) 或 Θ (g (n))$

其中渐进符号的含义与时间复杂度中的含义完全相同。

19.2 静态分析与动态分析

根据算法执行过程中对存储空间的使用方式，可以把空间复杂性分析分成两种：

（1）静态分析

一个算法静态使用的存储空间，称为静态空间。静态分析的方法比较容易，只要求出算法中使用的所有变量的空间，再折合成多少空间存储单位即可。

静态空间在编译/进入函数时就一次性分配好，大小固定不变，如普通局部变量 int i, maxi;。

（2）动态分析

一个算法在执行过程中，必须以动态方式分配的存储空间是指在算法执行过程中分配的空间，称为动态空间。动态空间主要是存储中间结果或操作单元所占用空间。

如 malloc/new 分配的数组、递归调用产生的工作记录（栈帧）等，其大小可能随执行过程变化。

19.3 示例：求最大值的算法

int max(int a[], int n)
{
int i, maxi = 0; // 临时变量：i 和 maxi
for (i = 1; i < n; i++)
if (a[i] > a[maxi])
maxi = i;
return a[maxi];
}

函数体内分配的变量空间为临时空间，不计形参占用的空间。这里仅计 i、maxi 两个变量的空间（各一个整型单元），与问题规模 n 无关，所以其空间复杂度为

(

)

O(1)

$O (1)$ 。

⚠️ 数组 a[] 本身是输入数据，其 O(n) 的空间不算在该算法的空间复杂度里。

19.4 【例1-7】非递归算法的空间复杂度

分析例1-5算法的空间复杂度：

void func(int n)
{
int i = 1, k = 100;
while (i <= n)
{
k++;
i += 2;
}
}

解：该算法是一个非递归算法，其中只临时分配了 i、k 两个变量的空间，它与问题规模 n 无关，所以其空间复杂度为

(

)

O(1)

$O (1)$ ，即该算法为原地工作算法（in-place algorithm）。

💡 原地工作算法：指执行算法所需的辅助存储空间是常量级（与输入规模无关）的算法。凡是只用了固定几个局部变量、没有额外数组/递归栈的算法，空间复杂度都是 O(1)。

19.5 【例1-8】递归算法的空间复杂度

题目：有如下递归算法，分析调用 maxelem(a, 0, n-1) 的空间复杂度。

int maxelem(int a[], int i, int j)
{
int mid = (i + j) / 2, max1, max2;
if (i < j)
{
max1 = maxelem(a, i, mid); // 递归求左半最大值
max2 = maxelem(a, mid + 1, j); // 递归求右半最大值
return (max1 > max2) ? max1 : max2;
}
else return a[i]; // 递归出口：只剩一个元素
}

解：执行该递归算法需要多次调用自身，每次调用只临时分配 3 个整型变量（mid、max1、max2）的空间，即每层 O(1)。

关键点：递归算法的空间 = 递归工作栈中同时存在的栈帧空间之和。虽然左右两个递归调用先后发生，但由于 max1 = maxelem(…) 的结果要保留在栈帧中等待右半边算完后使用，递归调用链上的栈帧是叠加的。

设调用 maxelem(a, 0, n-1) 的空间为

(

)

S(n)

$S (n)$ ，有递推关系：

(

)

{

(

)

(

)

(

)

S(n)=\\begin{cases} O(1) & n=1 \\\\ 2S(n/2)+O(1) & n>1 \\end{cases}

$S (n) = {O (1) 2 S (n /2) + O (1) n = 1 n > 1$

（说明：教材此处按

(

)

(

)

2S(n/2)+O(1)

$2 S (n /2) + O (1)$ 建模并给出 O(n) 的结论；直观上也可理解为递归树共 n 个结点、每个结点 O(1) 的栈帧空间，总和为 O(n)。另一种更精细的分析认为递归深度为

log

⁡

\\log_2 n

$lo g_{2} n$ 、每层 O(1)，栈空间为

(

log

⁡

)

O(\\log n)

$O (lo g n)$ ——预习阶段以教材结论 O(n) 为准，考试按教材建模答题。）

迭代展开求解（O(1) 记为常数1）：

(

)

(

)

[

(

)

]

(

)

(

)

⋯

(

)

⋯

−

(

设

即

log

⁡

)

\\begin{align*} S(n) &= 2S(n/2)+1 \\\\ &= 2\\left[2S(n/2^2)+1\\right]+1 = 2^2S(n/2^2)+1+2^1 \\\\ &= 2^3S(n/2^3)+1+2^1+2^2 \\\\ &= \\cdots \\\\ &= 2^kS(n/2^k)+1+2^1+2^2+\\cdots+2^{k-1} \\qquad (\\text{设 } n=2^k, \\text{ 即 } k=\\log_2 n) \\end{align*}

$S (n) = 2 S (n /2) + 1 = 2 [2 S (n / 2^{2}) + 1] + 1 = 2^{2} S (n / 2^{2}) + 1 + 2^{1} = 2^{3} S (n / 2^{3}) + 1 + 2^{1} + 2^{2} = \dots = 2^{k} S (n / 2^{k}) + 1 + 2^{1} + 2^{2} + \dots + 2^{k - 1} (设 n = 2^{k}, 即 k = lo g_{2} n)$

代入

(

)

(

)

(

)

S(n/2^k)=S(1)=O(1)

$S (n / 2^{k}) = S (1) = O (1)$ ，并利用等比数列求和

∑

−

\\sum_{t=0}^{k-1}2^t = 2^k – 1

$\sum_{t = 0}^{k - 1} 2^{t} = 2^{k} - 1$ ：

(

)

⋅

(

−

)

−

(

)

S(n) = n\\cdot 1 + (2^k – 1) = n + n – 1 = 2n-1 = O(n)

$S (n) = n \cdot 1 + (2^{k} - 1) = n + n - 1 = 2 n - 1 = O (n)$

结论：调用 maxelem(a, 0, n-1) 的空间复杂度为

(

)

\\boldsymbol{O(n)}

$O (n)$ 。

19.6 时间 vs 空间：递归的隐性开销

把例1-6（归并排序）和例1-8（分治求最大值）放在一起看，能体会到一个重要思想：

分治递归的时间：
分治递归的空间：
递归总是比等价的非递归实现多消耗栈空间——这是"用空间换代码简洁性"的典型例子。

对比记忆：

算法时间复杂度空间复杂度

顺序查找（例1-4）	最好O(1)、最坏/平均O(n)	O(1)，原地
例1-5 while循环	O(n)	O(1)，原地（例1-7）
归并排序（例1-6）	O(n log n)	教材模型O(n)（合并需辅助数组+递归栈）
分治求最大值（例1-8）	O(n)（可推：T(n)=2T(n/2)+O(1)）	O(n)（教材模型）

二十、全章易错点大盘点

结合本章全部例题，把最容易丢分的地方集中列一遍，考前扫一眼非常有用：

20.1 概念类易错点

输入可以是0个，输出必须至少1个。选择题问"算法的输入个数"，答案是"零个或多个"，不是"至少一个"。

算法必须有穷，程序不一定有穷。操作系统、服务器是程序但不是算法。

有穷性 ≠ 可行性：死循环违反有穷性（例1-2描述1），除零违反可行性（例1-2描述2）。判断口诀：整体停不下来→有穷性；单步做不了→可行性。

大O上界越低越有价值，大Ω下界越高越有价值，方向相反，别记混。

O(n^2) O(n2) 比 O ( n 4 ) O(n^4) O(n4) 有价值； Ω ( n 2 ) \\Omega(n^2) Ω(n2) 比 Ω ( n ) \\Omega(n) Ω(n) 有价值。

f(n)=Θ(g(n)) 当且仅当 f(n)=O(g(n)) 且 f(n)=Ω(g(n))，Θ 是三者中最精确的。

空间复杂度只算临时变量（辅助空间），不算输入数据本身和形参。max(int a[], int n) 的空间复杂度是 O(1) 而不是 O(n)。

平均情况是带权平均：

A(n)=\\sum P(I)T(I) A(n)=∑P(I)T(I)，权重是概率，不是简单算术平均；且要把查找失败的情形计入（例1-4第(2)问）。

20.2 代码分析类易错点

链表序号初值：带头结点链表找第一个数据结点，序号从1开始，i 初值应为1（例1-1）。

循环判空+短路顺序：while (p != NULL && p->data != x)——判空必须写在前面，靠 && 短路保护。

循环变量非线性变化：i += 2 时第 m 次后 i = 初值 + 2m；i *= 2 时第 m 次后 i = 初值 × 2^m。先写出通项再解不等式（例1-5）。

值传递带不回结果：输出型参数必须用引用（int &s）或指针，否则调用方拿不到计算结果（第十章 fun 函数的坑）。

三重循环求和别数错边界：j <= i 与 j < i、k < j 与 k <= j 差一次，写求和式时上下限要逐一核对（例1-3）。

20.3 递推求解类易错点

递推式要写初始条件：

展开找规律：

2^kT(n/2^k)+kcn 2kT(n/2k)+kcn，系数、规模、累计工作量三个部分同步变化，别只写一半。

n=2^k 的换元：展开到

n/2^k=1 n/2k=1 时 k = log ⁡ 2 n k=\\log_2 n k=log2​n，最终结果里的 log ⁡ 2 n \\log_2 n log2​n 就是这么来的。

等比求和公式：

1+2+2^2+\\cdots+2^{k-1}=2^k-1 1+2+22+⋯+2k−1=2k−1（例1-8最后一步），等差求和 ∑ i = 1 n i = n ( n + 1 ) 2 \\sum_{i=1}^{n}i=\\frac{n(n+1)}{2} ∑i=1n​i=2n(n+1)​、平方和 ∑ i = 1 n i 2 = n ( n + 1 ) ( 2 n + 1 ) 6 \\sum_{i=1}^n i^2 = \\frac{n(n+1)(2n+1)}{6} ∑i=1n​i2=6n(n+1)(2n+1)​ 必须熟记。

二十一、考点总结与学习建议

21.1 本章知识框架图（文字版）

算法设计与分析·第一章
│
├── 1.1 概述
│ ├── 算法定义：输入 → 一系列步骤 → 输出
│ ├── 算法正确性：对每个输入实例输出正确结果并停止
│ ├── 设计六大目标：正确性/可使用性/可读性/健壮性/高效率/低存储量
│ ├── 五大特征（Knuth）：有穷性、确定性、输入(0..n)、输出(1..n)、可行性
│ ├── 描述方法：自然语言、流程图、伪代码
│ ├── 例1-1 链表查找找茬（初值i=1、判空短路、区分成功失败）
│ ├── 例1-2 死循环→有穷性；除零→可行性
│ ├── 案例：6x+5y+4z=50穷举；欧几里得算法特征辨析
│ └── 算法与数据结构：联系（结构是算法基础）/区别（组织 vs 求解）
│ 求解流程：分析问题→选结构与策略→描述→证明正确性→分析
│
└── 1.2 算法的分析
├── 构成：控制结构（顺序/分支/循环）+ 原操作
├── 时间复杂度
│ ├── 步骤：找基本语句 → 求f(n) → 用O/Ω/Θ表阶
│ ├── 渐进符号：O(上界,越低越有价值)、Ω(下界,越高越有价值)、Θ(同阶,最精确)
│ ├── 多项式：aₘnᵐ+…+a₀ → O(nᵐ)/Ω(nᵐ)/Θ(nᵐ)
│ ├── 例1-3 三重循环 → O(n³)
│ ├── 三种情况：G(n)=MIN、W(n)=MAX、A(n)=ΣP(I)T(I)
│ ├── 例1-4 顺序查找：G=O(1)、W=O(n)、A=(n+1)/2；
│ │ 含失败概率q：A=q(n+1)/2+(1−q)n，q=1/2时≈3n/4
│ ├── 非递归：例1-5 i+=2 → O(n)；变式 i*=2 → O(log n)
│ └── 递归：建递推式→迭代展开
│ 例1-6 归并排序 T(n)=2T(n/2)+O(n) → O(nlog₂n)
└── 空间复杂度
├── 只计临时变量；静态空间 vs 动态空间
├── 例1-7 非递归两变量 → O(1)（原地工作算法）
└── 例1-8 递归maxelem S(n)=2S(n/2)+O(1) → 2n−1 → O(n)

21.2 高频题型预测

根据本章内容，考试大概率出现以下题型：

题型对应例题分值权重

算法特征辨析（选择/填空）	欧几里得算法填空、例1-2	⭐⭐⭐
找茬改错题（正确性+健壮性）	例1-1	⭐⭐⭐⭐
给代码求时间复杂度	例1-3、例1-5及各种循环变式	⭐⭐⭐⭐⭐
三种情况分析+平均复杂度推导	例1-4	⭐⭐⭐⭐
递归算法递推式建立与求解	例1-6、例1-8	⭐⭐⭐⭐⭐
空间复杂度分析（含递归栈）	例1-7、例1-8	⭐⭐⭐
简答：算法与数据结构的关系、渐进符号定义	第2.4节、第11节、第13节	⭐⭐⭐

21.3 给同学们的学习建议

动手推导，拒绝眼高手低。渐进分析的所有题目，方法都只有几招（找基本语句、写求和式、建递推式、迭代展开），但每一招都需要亲手算几遍才能内化。建议把例1-3的三重求和、例1-6的归并展开各独立推3遍。

背熟三大求和公式和常见递推式速查表（见18.5节），它们是计算题的"乘法口诀"。

建立"复杂度直觉"。看到单层循环想 O(n)，嵌套两层想 O(n²)，循环变量倍增想 O(log n)，"一分为二+线性合并"想 O(n log n)，"规模减一"的递归想 O(n)……做题前先猜答案再验证，进步最快。

重视概念辨析题。有穷性/可行性、O/Ω/Θ、静态/动态空间、最好/最坏/平均——这些概念两两之间的区别都是选择题和填空题的富矿，建议自己制作对比卡片。

写代码时养成分析习惯。今后每写一个函数，顺手在注释里标明时间和空间复杂度。这不仅是本课程的要求，更是终身受用的工程素养。

为后续章节铺垫。第一章的递推式求解方法将直接用于第二章递归/分治算法的分析；"最好/最坏/平均"框架将用于排序和查找算法的评价。基础不牢，地动山摇。

21.4 结语

算法分析的入门门槛其实不高：五大特征记清楚，三种符号分明白，基本语句找得准，递推关系列得出，求和公式用得熟——做到这五句话，第一章就稳了。

真正的功夫在后面：分治、贪心、动态规划、回溯、分支限界……每一种策略都是人类智慧的结晶，而复杂度分析是我们评价它们的统一标尺。希望这份预习笔记能帮你带着清晰的知识地图走进《算法设计与分析》的课堂。

路漫漫其修远兮，吾将上下而求索。新学期，一起加油！💪

📝 本文小结：全文围绕教材第一章展开，覆盖了算法概念与正确性、六大设计目标、五大特征、例1-1链表找茬、例1-2特征违反辨析、穷举案例与欧几里得算法、三种算法描述方法、C/C++描述形式（含值传递陷阱）、算法与数据结构的关系、时间复杂度分析（渐进符号O/Ω/Θ、例1-3三重循环、例1-4顺序查找三种情况、例1-5非递归、例1-6归并排序递归）、空间复杂度分析（例1-7原地算法、例1-8递归栈空间）等全部知识点，并附有易错点大盘点、知识框架图和考点预测。如果对你有帮助，欢迎点赞👍、收藏⭐、关注三连，评论区交流你的预习心得！