算法和算法评价

2026 大纲 一、基本概念（二）算法的基本概念。

什么算是算法，什么算是好算法

算法是为解决某类问题而规定的有限长操作序列。这个定义里的每个限定词都对应一条特性，五条缺一不可：

特性	含义	反例
有穷性	有穷步内结束，每步也在有穷时间内完成	while(1) x++;；操作系统主循环
确定性	每种情况的操作都有确切规定，无二义性	"把较大的放前面"——相等时没规定
可行性	都能由已实现的基本运算执行有限次完成	"取 $\pi$ 的全部小数位求和"
输入	零个或多个	打印九九乘法表没有输入，允许
输出	一个或多个	无输出的算法没有意义

这里有个值得单独记一笔的边界：算法必须有穷，程序不必。操作系统的等待循环是个正经程序，却永远不停，所以它不是算法（殷人昆 p24 明确点出这一条）。另外算法可以用自然语言或流程图描述，程序则必须用程序设计语言写成、能被执行。

"是不是算法"之外还有"好不好"，标准有四条：正确性、可读性、健壮性、高效性。高效性又含时间与空间两面，这两面常常此消彼长，一般以时间为主要指标——本篇剩下的内容都在讲怎么衡量这两面。

怎么衡量快慢：只数基本操作

最直接的办法是把程序跑一遍计时，但这叫事后统计，有两个绕不过去的毛病：必须先把算法实现出来，而且结果严重依赖机器和编译器，换台电脑就变。所以实际用的是事前分析估算——不看时间，只数执行次数。

也不必把每条语句都数。一条语句的重复执行次数叫语句频度，$T(n)$ 是全部语句频度之和；但真正决定量级的只有基本操作，也就是嵌套最深、次数最多的那条语句（查找类算法看关键字比较，排序类看比较与移动）。数它一条就够，因为剩下的部分只贡献常数系数和低次项，而大 $O$ 恰好把这两样丢掉。

三个记号的分工是这样的：

大 $O$	存在 $c,n_0$ 使 $n\ge n_0$ 时 $T(n)\le cf(n)$，渐近上界
$\mathrm{\Omega }$	$n\ge n_0$ 时 $T(n)\ge cg(n)$，渐近下界
$\mathrm{\Theta }$	同时是 $O$ 与 $\mathrm{\Omega }$，上下界同阶，具有对称性
多项式规则	$m$ 次多项式为 $O(n^m)$，低次项与全部系数丢掉
加法与乘法规则	并列取 $O(max(f,g))$，嵌套取 $O(f\cdot g)$；与 $n$ 无关的常数记 $O(1)$
取最紧	上界不唯一，习惯取最紧的上界、最大的下界

常见量级从小到大排开，右边那列是为了让"差一个量级"有实感：

量级（递增）	典型算法	${10}^9$ 次操作/秒、$n={10}^6$ 时
$O(1)$ 常数阶	下标访问、散列查找（理想）	瞬时
$O(\log n)$ 对数阶	折半查找、二叉排序树查找	瞬时
$O(n)$ 线性阶	顺序查找、遍历一遍表	1 ms
$O(n\log n)$ 线性对数阶	快排（平均）、归并、堆排序	20 ms
$O(n^2)$ 平方阶	直接插入、起泡、简单选择排序	约 17 分钟
$O(n^3)$ 立方阶	三重循环（如 Floyd）	约 32 年
$O(2^n)$ 指数阶	穷举子集、汉诺塔	无法完成
$O(n!)$ 阶乘阶	穷举排列	无法完成

🔴 这张表只在 $n$ 足够大时成立。渐近分析丢掉的常数在小规模下可能占主导：$n<1000$ 时 $n^2$ 反而比 $1000n$ 快。快速排序在子表足够小时改用直接插入排序，依据就是这一条。

先看一眼

加载可视化中...

图里把"找基本操作 → 数频度 → 定量级"这条主线和递归、空间两个分支摊开了。看的时候留意一件事：非递归和递归是两套数法——前者数循环转了几圈，后者要先写出递归方程。下面就分这两条走。

数循环：看循环变量怎么长

非递归算法的量级，全看循环变量是怎么从起点走到终点的：每次加一个常数就是线性，每次乘一个常数就是对数，被平方约束就是平方根。把这条原则套开，常见的形态就七种：

形态	代码骨架	精确次数	量级
1 单层线性	for(i=0;i<n;i++)	$n$	$O(n)$
2 嵌套独立	内层上界与外层无关	$n\times m$	$O(nm)$
3 嵌套相关	for(j=1;j<=i;j++) 上界是外层变量	$n(n+1)/2$	$O(n^2)$
4 倍增	i=1; while(i<=n) i*=2;	$\lfloor {\log }_{2}n\rfloor +1$	$O(\log n)$
5 折半	i=n; while(i>1) i/=2;	$\lfloor {\log }_{2}n\rfloor$	$O(\log n)$
6 平方比较	for(i=0;i*i<=n;i++)	$\lfloor \sqrt{n}\rfloor +1$	$O(\sqrt{n})$
7 两段并列	两段顺序执行	相加	取较大者

要想真的会用这张表，得能自己把次数数出来。先看频度是怎么算的：

int MatrixSum(int a[][N], int n) {
    int sum = 0;                      /* 频度 1 */
    for (int i = 0; i < n; i++)       /* 条件判断 n+1 次（最后一次为假才跳出）*/
        for (int j = 0; j < n; j++)   /* 对每个 i 判断 n+1 次，共 n(n+1) 次 */
            sum += a[i][j];           /* 频度 n²，这是基本操作 */
    return sum;                       /* 频度 1 */
}

$$T(n)=1+(n+1)+n(n+1)+n^2+1=2n^2+2n+3$$

和基本操作的频度 $n^2$ 只差常数系数与低次项——这就是"数最内层那一条就够"的由来。两处容易漏：循环的条件判断比循环体多一次；内层判断是 $n(n+1)$ 而不是 $n^2$。

形态 4 和形态 5 量级相同，精确次数却差一次，这个差别值得单独看清楚。形态 4（i = 1; while (i <= n) i *= 2;）的循环体在 $i=1,2,4,\dots$ 时进入，只要 $2^t\le n$ 就还会进一次，所以次数是满足 $2^t\le n$ 的 $t(t\ge 0)$ 的个数，即 $\lfloor {\log }_{2}n\rfloor +1$。取 $n=8$ 检验：$i$ 依次取 $1,2,4,8$，执行 4 次，而 $\lceil {\log }_{2}8\rceil =3$——可见这里不能写成 $\lceil {\log }_{2}n\rceil$。形态 5（i = n; while (i > 1) i /= 2;）从 $n$ 折半到 $1$ 为止，取 $n=8$ 时 $8\to 4\to 2\to 1$，执行 3 次 $={\log }_{2}8$。

差别的来源是边界：形态 4 的循环体在 $i=1$ 时执行了一次（"从 1 撑到 $n$"），形态 5 在 $i=1$ 时不再执行（"从 $n$ 缩到 1"）。看循环体在边界值上执不执行，就不会记混。

⚠️ 嵌套循环不是一律相乘。只有内层上界与外层无关时才是形态 2 的相乘；内层上界或步长跟着外层变（如 for (j = 1; j <= n; j += i)），次数由起点、终点、步长共同决定，得老老实实求和——上式的总次数是 $\mathrm{\Theta }(n\log n)$，不是 $O(n^2)$。

数递归：写方程再逐层展开

递归没有循环变量可数，得先把代价写成递归方程（递归项 + 非递归项 + 边界条件），再逐层展开：反复代入自身直到看出规律，用边界条件收尾。

递归式	解	典型来源
$T(n)=T(n-1)+1$	$\mathrm{\Theta }(n)$	阶乘、单链表递归遍历
$T(n)=T(n-1)+n$	$\mathrm{\Theta }(n^2)$	每层还要扫一遍整表
$T(n)=T(n/2)+1$	$\mathrm{\Theta }(\log n)$	折半查找（只进一个子区间）
$T(n)=2T(n-1)+1$	$\mathrm{\Theta }(2^n)$	汉诺塔，精确解 $2^n-1$
$T(n)=2T(n/2)+n$	$\mathrm{\Theta }(n\log n)$	归并排序

这张表的每一行都是展开出来的，不必背。看两个最典型的展开过程。

规模每次减 1，以阶乘为例：

long long Fact(int n) {
    if (n <= 1) return 1;          /* 递归出口 */
    return n * Fact(n - 1);        /* 问题规模每次减 1 */
}

Fact 每层只做常数次操作，对应 $T(n)=T(n-1)+1$，展开得 $\mathrm{\Theta }(n)$。若每层的代价换成 $n$（比如每层还要扫一遍整表），就是 $T(n)=T(n-1)+n$：

$$\begin{array}{rl}T(n)& =T(n-1)+n=T(n-2)+(n-1)+n=T(n-3)+(n-2)+(n-1)+n\\ & =\cdots =T(1)+2+3+\cdots +n=\frac{n(n+1)}{2}\end{array}$$

即 $\mathrm{\Theta }(n^2)$。

规模每次减半，以折半查找为例：

/* 在升序数组 a[low..high] 中折半查找 key，找到返回下标，找不到返回 -1 */
int BinSearch(int a[], int low, int high, int key) {
    if (low > high) return -1;             /* 出口：区间为空，查找失败 */
    int mid = low + (high - low) / 2;      /* 这样写而非 (low+high)/2，避免相加溢出 */
    if (a[mid] == key) return mid;
    else if (a[mid] > key)
        return BinSearch(a, low, mid - 1, key);   /* key 更小，只进入左半区间 */
    else
        return BinSearch(a, mid + 1, high, key);  /* key 更大，只进入右半区间 */
}

$$T(n)=T\left(\frac{n}{2}\right)+1=T\left(\frac{n}{4}\right)+2=\cdots =T\left(\frac{n}{2^k}\right)+k$$

令 ${\displaystyle \frac{n}{2^k}}=1$ 得 $k={\log }_{2}n$，代回得 $T(n)=1+{\log }_{2}n=\mathrm{\Theta }(\log n)$。

🔴 "减 1"和"减半"是两回事，前者线性、后者对数。递归本身不带来任何量级，量级来自规模缩小的方式。

汉诺塔是第三种形态：每层派生两个子问题、规模只减 1。把 $n$ 个盘从 A 移到 C，先把上面 $n-1$ 个借 C 移到 B，再把第 $n$ 号移到 C，最后把 B 上的 $n-1$ 个借 A 移到 C，于是 $T(n)=2T(n-1)+1$：

$$T(n)=2T(n-1)+1=4T(n-2)+2+1=8T(n-3)+4+2+1=\cdots =2^{k}T(n-k)+(2^k-1)$$

令 $k=n-1$ 得 $T(n)=2^n-1=\mathrm{\Theta }(2^n)$。取 $n=1,2,3,4$ 检验，移动次数 $1,3,7,15$ 逐个吻合。

另外两种解递归式的方法：递归树与主定理（想系统学就展开）

递归树：把每一层的非递归代价摊在树上逐层求和，适合 $T(n)=aT(n/b)+f(n)$。 以归并排序的 $T(n)=2T(n/2)+n$ 为例：第 $i$ 层（根为第 0 层）有 $2^i$ 个子问题、每个规模 $n/2^i$、每个的非递归代价 $n/2^i$，故该层总代价 $=2^i\times n/2^i=n$，与层号无关； 规模从 $n$ 折半到 1 共 ${\log }_{2}n+1$ 层，总代价 $=\mathrm{\Theta }(n\log n)$。

"每层 $O(n)$、共 $O(\log n)$ 层，故 $O(n\log n)$"——这句话就是递归树法的完整推导， 归并排序、快速排序的复杂度都是这么来的，不必当结论背。

主定理：对 $T(n)=aT(n/b)+f(n)$（$a\ge 1,b>1$），记 $d={\log }_{b}a$，把 $n^d$ 与 $f(n)$ 比：

情形	条件	结论
1	存在 $\epsilon >0$ 使 $f(n)=O(n^{d-\epsilon })$	$T(n)=\mathrm{\Theta }(n^d)$
2	$f(n)=\mathrm{\Theta }(n^d)$	$T(n)=\mathrm{\Theta }(n^d\log n)$
3	存在 $\epsilon >0$ 使 $f(n)=\mathrm{\Omega }(n^{d+\epsilon })$，且存在 $c<1$ 使 $n$ 充分大时 $af(n/b)\le cf(n)$	$T(n)=\mathrm{\Theta }(f(n))$

一句话用法：算出 $n^{{\log }_{b}a}$ 跟 $f(n)$ 比谁大，大的赢；一样大就再乘一个 $\log n$。

递归式	$n^{{\log }_{b}a}$	$f(n)$	结论	出现在
$T(n)=T(n/2)+O(1)$	$1$	$1$	$\mathrm{\Theta }(\log n)$	折半查找
$T(n)=2T(n/2)+O(1)$	$n$	$1$	$\mathrm{\Theta }(n)$	二叉树遍历、求结点数
$T(n)=2T(n/2)+O(n)$	$n$	$n$	$\mathrm{\Theta }(n\log n)$	归并排序、快排平均情形
$T(n)=2T(n/2)+O(n^2)$	$n$	$n^2$	$\mathrm{\Theta }(n^2)$	——

🔴 适用条件：主定理只适用于规模按倍数缩小的 $T(n)=aT(n/b)+f(n)$。 对规模按常数递减的 $T(n)=T(n-1)+f(n)$、$T(n)=2T(n-1)+f(n)$ 主定理不适用， 只能逐层展开——这正是逐层展开必须掌握、不能只背主定理的原因。

二叉树遍历那一行要加一句限定：$T(n)=2T(n/2)+O(1)$ 描述的是平衡二叉树。一般的二叉树 应写成 $T(n)=T(k)+T(n-1-k)+O(1)$（左子树 $k$ 个结点、右子树 $n-1-k$ 个结点）， 不论 $k$ 取什么，展开后每个结点恰好被访问一次，总代价都是 $\mathrm{\Theta }(n)$——结论不变， 但推导过程不同。

最好、最坏与平均

同一个 $n$，喂进去的数据不同，执行次数也可能差很远。于是同一个算法有三档：

情况	定义	说明
最好	计算量的最小值	易求，但出现概率通常极小
最坏	计算量的最大值	上界保证，默认讨论的就是它
平均	各输入等概率时计算量的加权平均值	最贴近实际，但常难以确定

🔴 三档比较的是同一个 $n$ 下的不同输入，别和大 $O$ 混作一谈。$O$ 描述的是函数关系（渐近上界），最好/最坏是在挑输入，两者正交——"最坏情况下的时间复杂度是 $O(n^2)$"和"平均情况下是 $O(n)$"可以同时成立。直接插入排序遇升序是最好 $O(n)$、遇逆序是最坏 $O(n^2)$，变的是初始状态；顺序查找等概率下平均比较 $\frac{n+1}{2}$ 次，与最坏同为 $O(n)$。

平均情况永远附带一个概率分布假设。题目不说明时默认等概率，一旦给了别的分布就必须按给定分布重算。比如已知待查元素有 $50\mathrm{\%}$ 的概率就在第 1 个位置、其余 $n-1$ 个位置均分剩下的 $50\mathrm{\%}$，平均比较次数是

$$0.5\times 1+\sum _{i=2}^n\frac{0.5}{n-1}\times i=0.5+\frac{n+2}{4}$$

取 $n=4$ 核对：等概率时是 ${\displaystyle \frac{4+1}{2}}=2.5$ 次，按上式是 $2.0$ 次；$n=10$ 时分别是 $5.5$ 与 $3.5$ 次。量级仍是 $O(n)$，变的只是常数。

由于平均情况往往难以确定，除非特别指明，讨论的时间复杂度一律指最坏情况。后面各章沿用这个约定，只在排序一章同时给出三档。

空间复杂度

$S(n)$ 只度量辅助存储空间：程序本身、常数、输入数据本身都不计（输入占多大取决于问题，与算法无关）；额外申请的变量、数组，以及递归工作栈要计。

$S(n)$	含义	例子
$O(1)$	原地工作，只用常数个额外变量	起泡、直接插入、简单选择、堆排序
$O(\log n)$	递归深度为 $\log n$	折半查找（递归）、快排（平均）
$O(n)$	与输入同量级的辅助空间	归并排序的辅助数组、快排最坏的递归栈

递归算法的空间是这里最容易出错的地方，关键是一句话：时间数的是递归树的结点总数，空间数的是递归树的高度。 递归是深度优先展开的，左分支出栈后右分支才入栈，所以栈上任何时刻只躺着"根到叶"的一条路径——每层只占常数空间时，$S(n)$ 就等于递归工作栈的最大深度，而不是调用总次数。

两段只差"进一个子区间"还是"进两个子区间"的代码，正好把这件事分开：

	递归式	时间	同时在栈的层数	空间
只递归一边（折半查找）	$T(n)=T(n/2)+O(1)$	$O(\log n)$	根到叶一条路径	$O(\log n)$
两边都递归（统计出现次数）	$T(n)=2T(n/2)+O(1)$	$O(n)$	仍是根到叶一条路径	$O(\log n)$

按这条口径过一遍后面会遇到的典型情形：

算法	递归深度	其他辅助空间	空间复杂度	深度为什么是这个值
阶乘 / 单链表递归遍历	$n$	$O(1)$	$O(n)$	规模每次只减 1
折半查找（递归）	$\lfloor {\log }_{2}n\rfloor +1$	$O(1)$	$O(\log n)$	规模每次减半
汉诺塔	$n$	$O(1)$	$O(n)$	时间虽是 $O(2^n)$，栈上仍只有一条路径
二叉树先序遍历（递归）	树高 $h$	$O(1)$	最坏 $O(n)$、平衡时 $O(\log n)$	深度就是树高；单支树时 $h=n$
归并排序	$O(\log n)$	辅助数组 $O(n)$	$O(n)$	两项取较大者
快速排序	平均 $O(\log n)$、最坏 $O(n)$	$O(1)$	平均 $O(\log n)$、最坏 $O(n)$	划分越均匀树越矮；每次都切成 0 和 $n-1$ 时退化成长为 $n$ 的链

原地与非原地的代码对照，以及形参占不占空间（写大题时会用上）

时间同为 $O(n)$、空间一个 $O(1)$ 一个 $O(n)$ 的一组对照：

/* 原地逆置：S(n) = O(1)，全程只用了 i、j、t 三个额外变量 */
void Reverse(int a[], int n) {
    int i = 0, j = n - 1, t;
    while (i < j) {                     /* i == j 时中间那个元素不用换，直接停 */
        t = a[i]; a[i] = a[j]; a[j] = t;
        i++; j--;
    }
}

/* 借助辅助数组逆置：S(n) = O(n)，多开了一个长度为 n 的数组 */
void ReverseCopy(int a[], int n) {
    int *b = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) b[i] = a[n - 1 - i];
    for (int i = 0; i < n; i++) a[i] = b[i];
    free(b);                            /* 申请了就要释放 */
}

形参占不占空间：C 语言里数组作形参会退化成指针，void f(int a[], int n) 与 void f(int *a, int n) 完全等价，传的是首地址、不产生数组拷贝，只占 $O(1)$； 但结构体按值传入会真的拷贝，把含 MaxSize 数组成员的 SqList L 按值传给递归函数， 每层都复制一整份，空间会从 $O(\text{深度})$ 变成 $O(\text{深度}\times \text{结构体大小})$， 写成 SqList *L 或 SqList &L 就不会。

考点速记

三条会被反复调用的结论：

1. 分析的是基本操作的执行次数，不是运行时间——大 $O$ 丢掉系数与低次项。
2. 递归的时间与空间量级可以差很远——时间数递归树的结点总数，空间数递归树的高度。
3. 主定理只管"规模按倍数缩小"的递归式，$T(n)=T(n-1)+f(n)$ 一律逐层展开。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：几乎是同一道题的变体——给一段程序片段，问它的时间复杂度。区别只在循环变量的走法，所以判断顺序固定：先看循环变量每次怎么变，再看有没有嵌套、内层依不依赖外层。

• 每次乘 2（或除以 2） → $\log$ 级。x = 2 * x 从 2 撑到 $n/2$，只需约 ${\log }_{2}n$ 次。
• 每次加 1，但被平方约束 → $\sqrt{n}$ 级。i*i < n 等价于 $i<\sqrt{n}$；while (n >= (x+1)*(x+1)) x++ 也是同一件事。
• 每次加的量本身在变 → 先求和再判。sum += ++i 直到 sum >= n，累加的是 $1+2+\cdots +i=\frac{i(i+1)}{2}$，解出 $i\approx \sqrt{2n}$，所以是 $\sqrt{n}$ 级。
• 嵌套且内层与外层无关 → 两层相乘。外层 k *= 2 走 ${\log }_{2}n$ 次、内层老老实实 $n$ 次，合起来 $O(n\log n)$。
• 嵌套且内层上界就是外层变量 → 不能相乘，要求和。外层 i *= 2、内层 j < i，总次数是 $1+2+4+\cdots \approx n$，结果是 $O(n)$ 而不是 $O(n\log n)$。
• 递归 → 只看规模怎么缩。fact(n-1) 是减 1，深度 $n$，$O(n)$。

易错：嵌套循环里只看了一层。 只盯外层 k *= 2 就答 $O(\log n)$、只盯内层 j<n 就答 $O(n)$，都是漏掉了另一层的乘法。看到嵌套，先确认内层跑几次、外层跑几次，再决定是相乘还是求和。

易错："内层依赖外层"被当成了相乘。 外层 ${\log }_{2}n$ 层、内层 $j<i$ 时，每层的次数不一样，得按等比数列求和，答案是 $O(n)$；直接乘成 $O(n\log n)$ 就错了。同理，内层 j<i 配上外层 $\sqrt{n}$ 次时，总数是 $O(n)$。

易错：把"递归"和"对数"画等号。 $O(\log n)$ 对应的是规模每次减半（如折半查找），而 fact(n) = n * fact(n-1) 每次只减 1，深度是 $n$，时间是 $O(n)$。

易错：开方当成了取对数。 i*i < n 是 $O(\sqrt{n})$，不是 $O(\log n)$；只有乘除以常数才是对数级。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版），p11：算法的定义（"为了解决某类问题而规定的一个 有限长的操作序列"）与五个特性的完整表述；评价算法优劣的四条标准（正确性、可读性、 健壮性、高效性）。
• 同书 p12：语句频度的定义（"一条语句的重复执行次数"）；"算法分析并非精确统计实际执行时间， 而是针对语句的执行次数做出估计"；基本语句的定义（"重复执行次数和算法的执行时间成正比的 语句"）；矩阵乘法的逐句频度统计示例。
• 同书 p13：大 $O$ 的定义（存在 $C$ 与 $n_0$ 使 $n\ge n_0$ 时 $T(n)\le Cf(n)$，描述增长率的 上限）；定理 1.1（$m$ 次多项式的时间复杂度为 $O(n^m)$，可忽略低次幂项与最高次幂的系数）； 以及"递归算法的时间复杂度通常用递归方程表示，涉及递归方程求解"。
• 同书 p13~p14：常量阶、线性阶、立方阶、对数阶四个分析示例；常见时间复杂度按数量级递增的排列 （常量阶、对数阶、线性阶、线性对数阶、平方阶、立方阶、$k$ 次方阶、指数阶）。
• 同书 p15：最好、最坏、平均时间复杂度的定义——平均时间复杂度是"按照输入实例以等概率 出现时算法计算量的加权平均值"；顺序查找在等概率假设下平均频度为 $n/2$ 的推导； 以及"除特别指明外，均指最坏情况下的时间复杂度"这条默认约定。
• 同书 p15~p16：空间复杂度的定义——只分析算法实现时所需的辅助存储空间，输入数据所占 存储量取决于问题本身、与算法无关；以及时间与空间"可能此消彼长"的权衡。
• 同书 p65~p67：函数调用与返回时系统各做的三件事、递归工作栈与活动记录的进栈/退栈过程 （以 Fact 的逐层活动记录图为例）；汉诺塔问题的递归解法与"规模减 1"的分解方式。
• 殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版），p24：算法与程序的界线 （"程序可以不满足有穷性"，并举操作系统的等待循环为例）。
• 同书 p33~p34：大 $O$ 表示法的一般提法 （"当且仅当存在正整数 $c$ 和 $n_0$ 使 $T(n)\le cf(n)$ 对所有 $n\ge n_0$ 成立"）与线性、平方、 指数、常数四个函数的验证例子；加法规则；量级序列 $c<{\log }_{2}n<n<n{\log }_{2}n<n^2<n^3<2^n<3^n<n!$。
• 同书 p35：乘法规则及其常数特例（"任何非 0 正常数都属于同一数量级，记为 $O(1)$"）； 各函数随 $n$ 增长的数值对照表；渐近空间复杂度的定义，明确指出计入的是 "排序算法中为移动数据所需的临时工作单元、递归算法中所需的递归工作栈"。
• 同书 p36~p37：$\mathrm{\Omega }$ 记号的定义（存在 $c$ 与 $n_0$ 使 $n\ge n_0$ 时 $T(n)\ge cg(n)$） 与"取最紧下界"的约定；$\mathrm{\Theta }$ 记号的定义（上下界同阶）及其对称性；顺序搜索在最好、最坏、 平均三档下分别为 $\mathrm{\Omega }(1)$、$O(n)$、$\mathrm{\Theta }(n)$ 的完整分析。

主定理不在上述两本教材的正文中，本篇把它作为求解 $T(n)=aT(n/b)+f(n)$ 的工具给出， 并同时给出逐层展开法——后者才是两本教材共同采用的方法，也是减法型递归式唯一可用的方法。

相关知识

数据结构的基本概念｜线性表基本概念｜ 栈和队列的基本概念｜递归与栈｜ 树的基本概念｜图的基本概念｜ 查找的基本概念｜查找算法对比｜ 排序的基本概念｜排序算法对比

相关文章

• 数据结构的基本概念

交互体验

前往完整可视化页面 →

真题练习

相关真题（7题）

2025Q12分2022Q12分2019Q12分2017Q12分2014Q12分2012Q12分2011Q12分