14.6 算法基础章节概述

算法基础这一章把数据结构之后的“操作方法”集中讲了一遍。课程的主线可以概括为：先定义什么是算法，再学会评价算法，然后掌握常见策略、查找和排序。

本章知识地图

flowchart TD
  A["算法基础"] --> B["算法概念"]
  A --> C["复杂度分析"]
  A --> D["算法策略"]
  A --> E["查找算法"]
  A --> F["排序算法"]

  B --> B1["有穷性/确定性/可行性/输入/输出"]
  C --> C1["时间复杂度"]
  C --> C2["空间复杂度"]
  D --> D1["分治"]
  D --> D2["贪心"]
  D --> D3["动态规划"]
  D --> D4["回溯"]
  E --> E1["顺序查找"]
  E --> E2["二分查找"]
  E --> E3["哈希查找"]
  F --> F1["插入/选择/交换"]
  F --> F2["归并/基数"]

算法概念：先判断“是不是算法”

算法必须满足若干基本特征：

特征	含义	易错点
有穷性	有限步后结束，每一步也能在有限时间内完成	“理论上一直循环”不是算法
确定性	每一步含义明确，没有二义性	“适当处理”“尽快完成”不够明确
可行性	每一步都能通过有限基本操作实现	不能依赖不可执行的神谕
输入	可以有零个或多个输入	输入不是必须有
输出	至少有一个输出	没有输出无法体现求解结果

这部分题通常是定义判断题，但要注意“输入可以为 0，输出至少为 1”这类反直觉表述。

复杂度：用增长阶评价算法

复杂度不是精确计时，而是看输入规模 $n$ 增大时，执行次数或辅助空间如何增长。

复杂度	常见来源	增长特点
$O(1)$	常数次语句	与 $n$ 无关
$O(\log n)$	每次折半	增长很慢
$O(n)$	单层线性扫描	与 $n$ 成正比
$O(n\log n)$	分治排序、堆排序	大规模排序常见优秀复杂度
$O(n^2)$	双重循环、简单排序	规模稍大就明显变慢
$O(2^n)$、$O(n!)$	穷举组合/排列	只适合小规模

求复杂度时保留最高阶，忽略常数和低阶项。例如 $3n^2+10n+100$ 记为 $O(n^2)$。

算法策略：看问题结构

策略	核心思想	典型问题	判断关键词
分治法	分解、求解、合并	归并排序、快速排序	子问题相互独立
贪心法	每一步选当前最优	活动选择、部分背包	局部最优能推出整体最优
动态规划	保存重叠子问题结果	矩阵连乘、0-1 背包	重叠子问题、最优子结构
回溯法	试探，不行就撤销	八皇后、排列组合	搜索解空间、剪枝

这四类策略最容易混淆的是贪心和动态规划。贪心一旦选择通常不回头；动态规划会系统记录多个子问题状态，再从表中推出最优结果。

查找算法：先看数据条件

查找	前提	平均查找长度/复杂度	高频考点
顺序查找	顺序表、链表均可，无需有序	成功时约 $(n+1)/2$	简单但效率低
二分查找	有序顺序表	$O(\log n)$	中点、边界、比较次数
哈希查找	能构造散列函数	理想接近 $O(1)$	冲突、装填因子、线性探测

二分查找是查找题的重点。边界更新要注意：mid 已经比较过，向左查找时右边界应变为 mid - 1，向右查找时左边界应变为 mid + 1。

排序算法：对比条件比背排名更重要

条件	常见选择
基本有序	直接插入
稳定且 $O(n\log n)$	归并排序
大规模且辅助空间少	堆排序
平均速度优秀的内部排序	快速排序
关键字位数少、范围明确	基数排序或计数排序

排序题常以“过程 + 性质”混合考查。例如给出一个堆，问是否满足大顶堆；给出一趟归并结果，问比较次数；给出稳定性条件，排除简单选择、堆、希尔、快速。

本章复习顺序

1. 先背算法特性和复杂度阶序。
2. 再理解四种策略的适用问题。
3. 查找重点练二分边界和哈希冲突。
4. 排序重点整理复杂度、稳定性、适用场景。
5. 遇到过程题，按算法动作模拟，不凭记忆猜结果。

单选

题干描述“每次把查找范围缩小一半”，通常指哪种查找方法？

A顺序查找B二分查找C哈希查找D回溯法

本节小结

算法基础不是零散结论堆积，而是一套判断框架：算法是否定义清楚，复杂度如何增长，问题适合哪种策略，数据条件允许哪种查找或排序。复习时把“前提条件”放在第一位，很多选择题会自然排除。