算法基本概念

真题练习

复杂度分析 是本节重点，需要掌握时间复杂度和空间复杂度的含义、常见数量级及基本分析方法。

什么是算法

算法 (Algorithm) 是一个明确规定了操作步骤的有限指令集，用于计算函数、处理数据、解决一个特定问题或执行某个任务。

算法 的基本属性：

1. 明确性：每一步骤必须有明确且不含糊的定义。
2. 有输入和输出：算法 应有 0 个或更多的 输入 和 1 个或更多的 输出。输入 是在 算法 开始之前提供的，而 输出 是在 算法 结束时产生的。
3. 有限性：如果 算法 在执行完有限步骤后终止，那么它就是 有限的。换句话说，一个 算法 必须总是在执行有限次操作后结束。
4. 可行性：算法 中的每一步都应该是简单且基本的，这样它们可以在有限的时间内完成并由计算机执行。
5. 独立性：算法 的指令应该有普适性，也就是说，它们不应依赖于任何特定的编程语言或模型。相反，算法 应该足够通用，可以在任何编程环境中实现。

效率度量

时间复杂度

时间复杂度（Time Complexity）是衡量算法运行效率的重要指标。它主要描述当输入规模（通常记为 $n$）不断增大时，算法执行所需的 基本操作次数 的增长趋势。

在算法的时间复杂度分析中，基本操作指算法中执行时间可视为常数的最小操作单元。分析时通常选取能代表主要工作量、且执行次数随输入规模变化的操作进行计数。

这些基本操作通常包括：

• 算术运算：例如，加、减、乘、除、取模等。
• 比较运算：例如，小于、大于、等于等。
• 赋值操作：将一个值赋给一个变量。
• 逻辑运算：例如，与、或、非等。

计算方法

设输入规模为 $n$，算法执行所需的基本操作次数记为 $T(n)$。为了衡量算法效率，我们关心 $T(n)$ 随 $n$ 增大的增长趋势，而不是某次运行的精确耗时。

若存在正常数 $c$ 和 $n_0$，使得当 $n\ge n_0$ 时均有

则称 $T(n)=O(f(n))$。其中 $f(n)$ 是能反映 $T(n)$ 增长速度的函数。大 $O$ 给出渐近上界；在 408 的常规复杂度分析中，通常用它表示基本操作次数的增长量级。

常用分析步骤

分析一段伪代码时，先确定规模参数 $n$ 和被计数的基本操作，再把循环或递归转写为次数关系。常见情形如下：

• 单层循环执行 $n$ 次，总代价为 $cn+d=O(n)$；
• 内层第 $i$ 轮执行 $i$ 次时，总次数为 $\sum_{i=1}^{n}i=\dfrac{n(n+1)}2=O(n^2)$，不能误写成 $O(n)$；
• 每轮把规模缩小到原来的一半时，满足 $n/2^k\le1$，因此 $k=\lceil\log_2n\rceil=O(\log n)$；
• 递归还要写出递推式。例如二路归并的 $T(n)=2T(n/2)+O(n)$，每一层合并代价为 $O(n)$，共 $O(\log n)$ 层，所以为 $O(n\log n)$。

最后保留最高阶项并忽略常数系数，是因为渐近复杂度比较的是规模足够大时的增长速度；这不表示小规模下常数、缓存或实现差异一定不重要。

常见时间复杂度

常见的 时间复杂度（按增长速度排序）有：

• $O(1)$：常数时间。基本操作次数不随输入规模增长。
• $O(\log n)$：对数时间。例如折半查找。
• $O(n)$：线性时间。例如顺序查找。
• $O(n\log n)$：线性对数时间。例如归并排序。
• $O(n^2)$、$O(n^3)$ 等：多项式时间。例如冒泡排序、插入排序和选择排序通常为 $O(n^2)$。
• $O(2^n)$：指数时间。例如直接递归计算斐波那契数列的朴素实现。
• $O(n!)$：阶乘时间。例如枚举所有排列的暴力算法。

空间复杂度

空间复杂度（Space Complexity）是衡量 算法执行过程中所需存储空间 随输入数据量增长而变化的指标。它不仅包括算法中用来存放 输入数据 的空间，还包括 辅助变量、递归调用栈 等临时空间。与时间复杂度类似，我们关注的是 增长趋势，通常只关注最高阶的量级，用大 O 符号表示。

组成

1. 固定部分
   • 包括常量、程序代码本身、简单变量、常量数组等。
   • 这一部分的空间大小与输入数据规模无关，通常记为 $O(1)$。
2. 可变部分
   • 随着输入数据量的变化而变化的空间，主要包括：
     • 输入数据本身（如数组、链表）
     • 辅助空间（如临时数组、栈、队列等）
     • 递归调用栈（递归深度对空间占用有直接影响）

常见空间复杂度

常见的 空间复杂度（按增长速度排序）有：

空间复杂度	描述	示例
$O(1)$	使用常量级额外空间	交换两个变量、迭代求最大值/最小值
$O(\log n)$	额外空间随递归深度按对数增长	递归实现的折半查找
$O(n)$	需要与输入规模成线性关系的额外空间	复制数组、借助栈或数组完成操作
$O(n^2)$	需要平方量级的额外空间	Floyd-Warshall 算法的距离矩阵

口径说明：有的题目讨论算法占用的总存储空间，有的题目只讨论除输入数据外的辅助空间。作答时要先明确口径；递归算法还必须计入递归调用栈。