算法与程序设计核心要点整理

一、基础知识点

1. 算法时间复杂度与空间复杂度

时间复杂度：算法执行时间随数据规模增长的变化趋势

常见复杂度：O(1)、O $(l o g n)$ 、O(n)、O $(n l o g n)$ 、O(n²)、O(2ⁿ)
循环计算：嵌套循环相乘，顺序循环相加
递归计算：分析递归方程，如归并排序 T(n) = 2T(n/2) + O(n)

空间复杂度：算法运行所需内存空间随数据规模增长的变化趋势

包括固定空间和可变空间（递归栈空间等）

2. 递归算法思想

核心要点：

将问题分解为相同形式的子问题
必须有递归终止条件
每次递归调用应使问题规模减小
经典例子：阶乘、斐波那契数列、汉诺塔

3. 分治算法思想

三步走：

分解：将原问题分解为若干子问题
解决：递归解决子问题
合并：合并子问题的解得到原问题的解

经典例子：

快速排序：不稳定排序，平均O( $n l o g n$ ),最坏O( $n^{2}$ )
归并排序：稳定排序，O( $n l o g n$ )

特性	归并排序	快速排序
时间复杂度
最坏情况	O( $n l o g n$ )	O(n²)
平均情况	O( $n l o g n$ )	O( $n l o g n$ )
最好情况	O( $n l o g n$ )	O( $n l o g n$ )
空间复杂度	O(n)	O( $l o g n$ )
稳定性	稳定	不稳定
排序方式	非原地排序	原地排序
数据敏感度	不敏感	敏感（依赖pivot选择）
排序稳定性：相等元素的相对顺序在排序前后保持不变

4. 二分查找算法

思想：在有序序列中，每次比较中间元素，缩小一半搜索范围

时间复杂度：O( $l o g n$ )
适用场景：有序数组查找、单调函数求根
前提条件：数据必须有序

5. 枚举法算法思想

思想：列举所有可能情况，判断是否满足条件

优点：简单直接
缺点：效率低，仅适用于小规模问题
适用范围：问题规模小，没有更优解法

6. 栈和队列的基本特点

栈（Stack）：

LIFO（后进先出）
基本操作：push、pop、top
应用：函数调用、表达式求值、括号匹配

队列（Queue）：

FIFO（先进先出）
基本操作：enqueue、dequeue、front
应用：BFS、缓冲区、任务调度

7. 深度优先搜索（DFS）

思想：尽可能深地搜索图的分支，直到末端再回溯

遍历顺序：使用栈（显式或隐式递归栈）
适用于：路径查找、连通分量、拓扑排序
空间复杂度：O(h)，h为树高

8. 广度优先搜索（BFS）

思想：逐层遍历图的所有节点

遍历顺序：使用队列
适用于：最短路径（无权图）、层次遍历
空间复杂度：O(w)，w为最大宽度

9. 回溯法算法思想

思想：系统性地搜索解空间，遇到不满足条件的情况时回溯

解空间树：
- 子集树：从n个元素中找出满足条件的子集（2ⁿ个节点）
- 排列树：n个元素的全排列（n!个节点）
经典例子：
- N皇后：在棋盘上放置皇后使其互不攻击
- 数独：填充数字满足规则
- 01背包：选择物品使价值最大且不超重

10. 分支限界法与回溯法的区别

特征	回溯法	分支限界法
搜索方式	深度优先	广度优先或最小成本优先
存储结构	栈	队列、优先队列
节点扩展	活结点的所有儿子	每个活结点一次产生所有儿子
应用目标	所有解或一个解	最优解
剪枝方式	约束函数	约束函数+限界函数

11-13. C++基础编程

数据类型定义：

cpp

char ch = 'A';
string str = "Hello";
int arr[10];
struct Student { string name; int score; };

输入输出：

cpp

cin >> ch >> str;
cout << "Value: " << arr[0];

流程控制： $i f - e l s e 、 f o r 、 w h i l e 、 d o - w h i l e 、 s w i t c h - c a s e$

14. sort函数使用

cpp

// 升序排序
sort(arr, arr+n);
// 降序排序
sort(arr, arr+n, greater<int>());
// 自定义排序
bool cmp(int a, int b) { return a > b; }
sort(arr, arr+n, cmp);

15. 蛮力法思路

使用多重循环枚举所有可能情况
一重循环：O(n)
二重循环：O(n²)
适用于小规模问题或验证其他算法

16. 求最大值、次大值、最小值

cpp

// 一次遍历求最大和最小
int maxVal = INT_MIN, minVal = INT_MAX;
for(int num : arr) {
    maxVal = max(maxVal, num);
    minVal = min(minVal, num);
}
// 求次大值需要记录两个变量

二、拓展知识点

1. 子集枚举和排列枚举

子集枚举（2ⁿ种情况）：

cpp

// 位运算枚举
for(int i = 0; i < (1 << n); i++) {
    for(int j = 0; j < n; j++) {
        if(i & (1 << j)) {
            // 第j个元素在子集中
        }
    }
}

排列枚举（n!种情况）：

cpp

// 使用next_permutation
sort(arr, arr+n);
do {
    // 处理当前排列
} while(next_permutation(arr, arr+n));

3-4. 回溯法应用

递归模板：

cpp

void dfs(int step) {
    if(满足结束条件) {
        记录解;
        return;
    }
    for(所有可能的选择) {
        if(满足约束条件) {
            做选择;
            dfs(step + 1);
            撤销选择; // 回溯
        }
    }
}

关键理解：

递归前做选择，递归后撤销选择
通过约束函数剪枝减少搜索
可求所有解或最优解

5. 二叉树操作

存储结构：

cpp

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

遍历：

先序遍历：根→左→右（DFS顺序）
中序遍历：左→根→右
后序遍历：左→右→根

6. 图的存储与遍历

邻接矩阵：适用于稠密图，O(1)查询边

cpp

int graph[N][N]; // graph[i][j]表示i到j的边

邻接表：适用于稀疏图，节省空间

cpp

vector<int> adj[N]; // adj[i]存储i的所有邻居

图的DFS/BFS：与树类似，但需要visited数组避免重复访问

7. BFS求无权图最短路径

BFS第一次访问到目标节点时的路径就是最短路径
需要记录路径长度或使用层次遍历
时间复杂度：O(V+E)

8. 01背包问题解法对比

方法	时间复杂度	空间复杂度	特点
枚举法	O(2ⁿ)	O(n)	简单，仅适用于n≤20
回溯法	O(2ⁿ)	O(n)	可剪枝，求所有解或最优解
动态规划	O(nW)	O(nW)或O(W)	最优解，W为背包容量

DP状态定义： $d p [i] [j]$ 表示前i个物品，容量为j时的最大价值 状态转移 $： d p [i] [j] = m a x (d p [i - 1] [j], d p [i - 1] [j - w [i]] + v [i])$

学习建议：

理解每个算法的核心思想而非死记代码
通过画图理解递归和搜索过程
多做分类练习，总结各类问题的解题模式
注重时间/空间复杂度分析的训练
从暴力解法开始，逐步优化到更高效的算法

一、算法基础概念

算法定义与特性
- 有限、有序、可执行的步骤序列
- 基本特性：有穷性、确定性、输入输出性、可行性
- 核心本质：解决问题的有限步骤集合
算法描述方式
- 自然语言：通俗易懂，无歧义性
- 流程图：图形化表示步骤流向
- 伪代码：连接自然语言与编程语言
- 机器语言：可读性差，依赖硬件
算法分析核心
- 时间复杂度（衡量执行步骤数随输入规模增长的趋势）
- 空间复杂度（衡量所需额外存储空间随输入规模增长的趋势）
- 正确性验证
时间复杂度分析
- 渐近表示法：大O（最坏情况）、Θ（平均情况）
- 忽略常数项和低次项的原因
- 常见复杂度排序：O(1)<O( $l o g n$ )<O(n)<O( $n l o g n$ )<O(n²)<O(2ⁿ)
算法设计步骤
- 明确问题需求与输入输出
- 选择合适的解决方案
- 算法描述与实现
- 验证与优化
- 复杂度分析

二、STL（标准模板库）容器

序列容器
- vector：动态数组，内存连续，支持随机访问，尾部插入高效
- deque：双端队列，两端插入删除O(1)，支持随机访问
- list：双向链表，内存不连续，插入删除高效（非首尾也高效）
关联容器
- set/multiset：基于红黑树，自动排序，不允许/允许重复元素
- map/multimap：键值对存储，键自动排序，不允许/允许重复键
- unordered_set/unordered_map：基于哈希表，无序，查找O(1)平均
容器适配器
- stack：后进先出（LIFO），默认基于deque
- queue：先进先出（FIFO），默认基于deque
- priority_queue：优先队列，始终处理优先级最高元素
string容器
- 专门处理字符串
- 支持拼接、查找、比较、随机插入字符等操作
容器选择原则
- 频繁随机访问：vector、deque
- 频繁插入删除：list
- 需要排序：set/map
- 需要快速查找：unordered_set/unordered_map
- 需要特定进出顺序：stack、queue、priority_queue

三、递归算法

递归核心概念
- 函数直接或间接调用自身
- 与数学归纳法的关系：终止条件对应基例，递归体对应归纳步骤
递归三要素
- 递归终止条件（base case）
- 递归体（将问题分解为更小子问题）
- 子问题的解合并逻辑
递归应用场景
- 基于递归数据结构的问题（二叉树、链表）
- 问题可分解为结构相同的更小子问题
- 递归实现排序算法（如插入排序）
递归算法设计
- 明确递归终止条件
- 假设规模为n-1的子问题已解决
- 推导规模为n的问题解法
- 避免重复计算（记忆化优化）
递归复杂度分析
- 空间复杂度：主要来自递归调用栈
- 时间复杂度分析：直接展开法、递归树法、主方法
- 递归层数过多导致栈溢出风险
主方法（Master Theorem）
- 适用于形式：T(n) = aT(n/b) + f(n)
- 根据f(n)与n^(log_b a)的关系确定复杂度

四、分治算法

分治核心思想
- 分解 → 求解 → 合并
- 子问题相互独立、结构相同
- 递归方程分析：T(n) = aT(n/b) + f(n)
经典分治算法
- 二分查找：O(logn)，适用于有序数组
- 快速排序：选择基准分区，平均O(nlogn)，最坏O(n²)
- 归并排序：合并有序子序列，稳定，O(nlogn)，空间O(n)
- 棋盘覆盖：L型骨牌，规模2^n×2^n
- 循环日程安排：n=2^k选手，构造n×(n-1)日程表
分治应用
- 最大连续子序列和：考虑左半、右半、跨越中间三种情况
- 适合问题：可拆分、子问题独立、可合并

五、穷举法（枚举法）

穷举核心思想
- 遍历所有可能解，验证符合条件的解
- 逻辑简单，能确保找到所有可行解
穷举通用框架
- 确定候选解范围
- 生成所有可能候选解
- 验证候选解是否满足条件
适用场景
- 解空间规模较小
- 无法找到更高效算法
- 需要验证所有可能解
经典穷举问题
- 子集枚举（幂集）： $2^{n}$ 个候选解
- 排列枚举：n!个候选解
- 最大连续子序列和：枚举所有子数组起始和结束位置
- 01背包：枚举每个物品选或不选（ $2^{n}$ ）
- N皇后：枚举每行皇后位置
- 任务分配：n!种分配方案
- 旅行商问题（TSP）：(n-1)!条路径
优化技巧
- 剪枝：提前排除不可能解
- 前缀和数组：快速计算区间和
- 并查集：管理元素连通关系

六、回溯法

回溯核心思想
- 试探与回退（深度优先搜索+剪枝）
- 解空间树结构：子集树、排列树
- 剪枝操作减少无效搜索
解空间树类型
- 子集树：元素选或不选，深度为元素个数，叶子2^n个
- 排列树：元素排列，叶子n!个
回溯算法框架
- 验证约束条件
- 选择当前决策
- 递归深入
- 回溯到上一步
经典回溯问题
- N皇后：皇后不能同行同列同对角线
- 图的m着色：相邻节点颜色不同
- 子集和：部分和等于目标和
- 01背包：物品选或不选
- 任务分配：每个任务分配给一个人
- 旅行商问题（TSP）：遍历所有城市一次的最短回路
- 构造表达式：试探运算符与括号组合
回溯特点
- 适用于解空间较大但存在约束条件的问题
- 时间复杂度取决于解空间树的节点数
- 需要明确定义终止条件

七、分支限界法

分支限界核心思想
- 分支搜索 + 限界剪枝
- 通常广度优先或优先队列搜索
- 目标：找到最优解
与回溯法区别
- 搜索目标：回溯法找所有解，分支限界法找最优解
- 搜索方式：回溯法深度优先，分支限界法广度优先/优先队列
- 剪枝依据：回溯法依赖约束条件，分支限界法依赖界限函数
分支限界类型
- 队列式（FIFO）：广度优先搜索
- 优先队列式：按界限函数值排序，启发式搜索
分支限界设计要点
- 定义解空间结构
- 构造合适的界限函数（上界/下界）
- 选择搜索策略
- 剪枝：排除不可能包含最优解的分支
经典应用
- 单源最短路径（如Dijkstra算法）
- 01背包问题：界限函数基于剩余物品单位价值贪心估计
- 旅行商问题：界限函数为当前路径长度+剩余路径估计

八、图遍历算法

广度优先搜索（BFS）
- 队列实现，按层遍历
- 应用：无权图最短路径、层次遍历、连通分量
- 时间复杂度：邻接矩阵O(n²)，邻接表O( $n + e$ )
深度优先搜索（DFS）
- 栈/递归实现，一条路走到底再回溯
- 应用：回溯法、拓扑排序、连通分量
图最短路径
- 无权图：BFS第一次访问到目标节点的路径最短
- 带权图：Dijkstra算法（优先队列分支限界）

九、经典算法问题汇总

排序算法
- 快速排序（分治，不稳定）
- 归并排序（分治，稳定）
- 直接插入排序（递归实现）
查找算法
- 二分查找（分治，O $(l o g n)$ ）
背包问题
- 01背包：回溯法（子集树）、分支限界法、动态规划
- 简单装载：不超过载重量时最大化装载量
排列组合问题
- 幂集生成（子集枚举）
- 全排列生成（排列枚举）
约束满足问题
- N皇后：排列树+约束检查
- 图着色：相邻节点颜色不同
- 任务分配：排列树+成本计算

十、复杂度总结表

算法/问题	时间复杂度	空间复杂度	备注
二分查找	O(logn)	O(1)	有序数组
快速排序	平均O(nlogn) 最坏O(n²)	O(logn)递归栈	不稳定
归并排序	O(nlogn)	O(n)	稳定
子集枚举	O(2ⁿ)	O(n)	幂集
排列枚举	O(n!)	O(n)	全排列
01背包（穷举）	O(2ⁿ)	O(n)	n≤20可行
01背包（分支限界）	指数级但剪枝	O(n)	优于穷举
N皇后（回溯）	O(n!)	O(n)	排列树
TSP（穷举）	O((n-1)!)	O(n)	n≤10可行
最大连续子序列和（穷举）	O(n²)	O(1)	可优化到O(n)
最大连续子序列和（分治）	O(nlogn)	O(logn)	递归栈

算法与程序设计核心要点整理 ​

一、基础知识点 ​

1. 算法时间复杂度与空间复杂度 ​

2. 递归算法思想 ​

3. 分治算法思想 ​

4. 二分查找算法 ​

5. 枚举法算法思想 ​

6. 栈和队列的基本特点 ​

7. 深度优先搜索（DFS） ​

8. 广度优先搜索（BFS） ​

9. 回溯法算法思想 ​

10. 分支限界法与回溯法的区别 ​

11-13. C++基础编程 ​

14. sort函数使用 ​

15. 蛮力法思路 ​

16. 求最大值、次大值、最小值 ​

二、拓展知识点 ​

1. 子集枚举和排列枚举 ​

3-4. 回溯法应用 ​

5. 二叉树操作 ​

6. 图的存储与遍历 ​

7. BFS求无权图最短路径 ​

8. 01背包问题解法对比 ​

一、算法基础概念 ​

二、STL（标准模板库）容器 ​

三、递归算法 ​

四、分治算法 ​

五、穷举法（枚举法） ​

六、回溯法 ​

七、分支限界法 ​

八、图遍历算法 ​

九、经典算法问题汇总 ​

十、复杂度总结表 ​