## 前言
AI:训练成本、推理能力、架构能力、算法的优化
我们在AI时代需要什么：独立思考的能力、分析用户的需求
> 程序=数据结构+算法
>
> 算法->智能
脚本语言vs系统语言
> **脚本语言**：Python、JavaScript、PHP、Ruby
>
> **特点**：开发快、动态、适合胶水代码、自动化任务
>
> **系统语言**：C/C++、Java、Go
>
> **特点**：性能强、类型安全、适合大型系统
**软件架构**
软件开发生命周期：可行性研究——需求分析——概要设计——详细设计——实现测试——使用维护
软件结构——Web Service
```mermaid
graph LR
subgraph A_group
A["Service Broker"]
D["UDDI Registry"]
end
B["Service Provider"] -->|Publish/UDDI /WSDL| A
C["Service Requester"] -->|Find/UDDI/WSDL| A
C -->|Bind/Invoke| B
E["Client Application"] --> |SOAP| F["Web Service"]
```
- **Web Service**：基于HTTP/HTTPS的API服务（RESTful、SOAP）
- **架构层次**：单体 → 微服务 → 云原生
- **框架**：Spring Boot（Java）、Django（Python）、Express（Node.js）
- **核心观点**：框架封装了架构，但背后业务的核心竞争力仍是**算法**。
技术栈——以Java为例
- **演进逻辑**：
- PHP：快速建站
- J2EE（Servlet/EJB）：企业级重量级
- JSP：前后端混合
- Spring：轻量级IoC/AOP
- Spring Boot：简化配置，微服务基石
- 技术演进方向是**简化开发、解耦、云原生**。
**思维体系**
培养自己独立思考的能力,归纳、总结，把算法梳理成一个体系.
1. 理解问题
- 精确解（最优解） vs 近似解（启发式、随机化）
2. 选择数据结构和算法
- 数据结构：数组、链表、树、图、哈希表
- 算法策略：分治、贪心、动态规划、回溯、分支限界
3. 设计策略
- 从暴力到优化
- 从特殊到一般
- 从递归到迭代
4. 设计算法
- 伪代码 → 流程图 → 代码实现
5. 证明正确性
- 数学归纳法
- 循环不变式
- 反证法
- 对拍验证
6. 分析算法
- **时间复杂度**：Big O 分析
- **空间复杂度**：内存占用
- **稳定性**：是否改变相对顺序
- **适用场景**：数据规模、数据特性
7. 设计程序
框架大纲列出来
- 需求 → 模块划分 → 接口定义 → 数据流 → 核心算法 → 测试用例
8. 反思：为什么这么设计？还能改进吗？
理解算法为什么这么设计
1. **历史背景**：当时解决了什么问题？
2. **类比思维**：借鉴了哪些已知方法？
3. **数学原理**：用了什么数学性质（最优子结构、贪心选择性质）？
4. **优化动机**：从暴力到优化的每一步是怎么想到的？
5. **局限性**：为什么这个方法不是万能的？
算法设计的由来相比算法设计的正确性更重要
例如：动态规划的由来→从递归到记忆化搜索再到递推的过程。
学习能力≠解决问题的能力
- **理解**：学习是输入，解决问题是输出。中间需要**独立思考**的转化过程。
```mermaid
graph TD
A[理解问题] --> B(精确解或近似解，选择数据结构，算法设计策略)
B --> C[设计算法]
C --> B
D --> B
E -->B
C --> D[证明正确性]
D --> E[分析算法]
E --> F[设计程序]
```
分析算法
1. 算法的复杂性
- 理论层面的分析，时间复杂度和空间复杂度
2. 用户的实际感受
- 效率不够快、结果不令人满意
3. 对比、调研市场上现有的解决方案
- 同类产品的算法选型、性能指标
解决问题的步骤
策略：先写出个大致执行过程/框架
> 输入 → 预处理 → 核心算法 → 后处理 → 输出
问题分解/问题新认识——问题的需求
- 用户真正需要的是什么？
- 问题的本质特征是什么？
- 将大问题拆解为可处理的子问题
提高效率的两种策略
1. 计算结果复用
- **实现方式**：
- 数据库缓存
- 内存缓存（Redis）
- 动态规划表
- 空间换时间
2. 减小搜索空间
- **实现方式**：
- 剪枝（回溯法）
- 启发式搜索（A*）
- 分支限界
设计算法，问题是否可分解？
1. 可分解，拆成子问题
- 子问题是否独立？
- 子问题是否重叠？
- 是否有最优子结构？
- **分治**：子问题独立，不复用结果
- **动态规划**：子问题重叠，最优子结构，复用计算结果
- **贪心**：只做一次选择，局部最优到全局最优，迭代推进，不需要复用历史结果
2. 不可分解，解空间搜索范围
- **需要找到所有解/判定可行性** → **回溯法**（DFS + 剪枝）
- **需要找到最优解**（且解空间较大）→ **分支界限法**（BFS + 限界）
- 如果需要快速逼近最优解 → **LC分支**（优先队列 + 成本估计函数 c(x)）
- 回溯:DFS+剪枝
- 分支界限：BFS或最小耗费优先。在扩展节点时采用成本估计函数来评估后续。通过界限来剪掉不可能产生最优解的分支。
- LC分支。是分支界限法的一种实现方式，使用优先队列（堆）来管理活结点，每次选择成本估计最小的节点作为扩展结点
- 概率算法。在算法中引入随机值，包括数值概率算法、蒙特卡洛算法、拉斯维加斯算法
根据问题特征
| 问题特征 | 适用算法 | 核心思想 |
| :-------------------------------- | :-------------------- | :------------------------- |
| 子问题独立 | **分治法** | 分解 + 递归 + 合并 |
| 子问题重叠，动态规划性质 | **动态规划** | 记忆化 + 递推 |
| 局部最优 = 全局最优，贪心选择性质 | **贪心算法** | 每一步都选当前最优 |
| 解空间树，无最优子结构 | **回溯法** | 深度优先搜索 + 剪枝 |
| 求最优解 + 上下界 | **分支限界** | 广度优先 + 剪枝 |
| 解空间巨大 | **概率算法** | 以概率1正确/以高概率正确 |
| 非确定性 | **随机算法** | 引入随机性（如快排随机化） |
| 连续优化 | **梯度下降** | 沿负梯度方向迭代 |
| 神经网络 | **反向传播** | 链式法则 + 梯度更新 |
| 组合优化 | **模拟退火/遗传算法** | 启发式搜索 |
```mermaid
flowchart TD
Start([开始设计算法]) --> A{问题是否可分解？}
%% 不可分解分支
A -- "否" --> B[搜索类算法]
B --> C{解空间搜索策略}
C -- "完整搜索" --> D[回溯法]
C -- "剪枝搜索" --> E[分支界限法]
E --> F[LC分支
（成本估计函数剪枝）]
%% 可分解分支
A -- "是" --> G{子问题是否重叠？}
%% 无重叠 -> 分治
G -- "否（子问题独立）" --> H[分治法]
%% 有重叠 -> 进一步判断
G -- "是" --> I{是否有最优子结构？}
I -- "是" --> J[动态规划
（结果复用）]
I -- "否（但局部最优即全局最优）" --> K[贪心算法
（每一步选当前最优）]
%% 特殊情况
A -.-> L[特殊情况]
L --> M[概率算法
拉斯维加斯、蒙特卡洛等]
M --> N[允许一定错误概率]
```
分支界限的关键公式
成本估计函数$\hat c(x)=f(h(x))+g(x)$
- $x$：当前节点（部分解）
- $h(x)$：从根到x的路径（已做的选择）
- $f(h(x))$：已产生的实际成本
- $g(x)$：从x到目标的最小可能成本的**估计值**（启发式函数）
- $\hat c(x)$：通过x节点得到完整解的总成本下界
- 用于评估该路径的潜力，提前终止不是最优解的函数
剪枝条件：如果$\hat c(x)$>当前最优解，则剪掉x的子树
LC(Least Cost)分支
- 优先队列分支界限法
- 每次选择 $\hat {c}(x)$ 最小的节点扩展
- 期望尽快找到最优解，提高剪枝效率
线性时间
特殊的函数
分治的代价
问题特殊
搜索类算法详解
1. **回溯法**
- **思想**：深度优先搜索解空间树，遇到不符合条件就返回
- **适用**：组合问题、排列问题、子集问题
- **优化**：剪枝（可行性剪枝、最优性剪枝）
2. **分支限界算法**
- **思想**：广度优先搜索，用上下界剪枝
- **适用**：旅行商问题、背包问题
- **优化**：优先队列扩展最有希望的节点
3. **概率算法**
- **拉斯维加斯算法**：总是正确，时间随机
- **蒙特卡洛算法**：时间确定，可能出错
- **理解**：用随机性换效率
4. **随机算法**
- 快排随机化：避免最坏情况
- 随机化哈希：避免恶意攻击
- **理解**：让输入无法针对你的算法
连续优化算法
1. **梯度下降**
- 沿负梯度方向迭代
- 变种：批量梯度下降、随机梯度下降、小批量梯度下降
2. **反向传播**
- 神经网络的核心训练算法
- 本质：链式法则 + 动态规划
3. **凸优化**
- 目标函数是凸函数 → 全局最优
- 工具：拉格朗日乘子法、KKT条件
循环不变式来证明算法正确性
1. **循环不变式**
- **定义**：在循环的每次迭代前后都成立的性质
- **三要素**：
1. 初始化：循环开始前成立
2. 保持：如果某次迭代前成立，迭代后仍然成立
3. 终止：循环结束时，不变式给出有用性质
2. **举例：插入排序的正确性证明**
> 循环不变式：每次迭代前，子数组 A[0..i-1] 已排序
>
> 初始化：i=1 时，A[0] 已排序（单个元素）
>
> 保持：假设 A[0..i-1] 已排序，将 A[i] 插入合适位置后，A[0..i] 已排序
>
> 终止：i=n 时，A[0..n-1] 已排序 → 整个数组排序完成
3. **其他证明方法**
- 数学归纳法
- 反证法
- 对偶证明
- 交换论证（贪心算法）
**概率分析（RAM模型）**
分析一个算法之前，需要建立一个现实技术的模型，包括描述所用资源及代价的模型。
RAM模型：通用的单处理器、随机存取器RAM计算模型
指令一条接一条执行，没有并发操作。
包含了真实计算机中常见的指令：算术指令、数据移动指令和控制指令。
每条指令所需的时间都为常量。
数据类型有整数类型和浮点实数类型。
RAM模型中的灰色区域：
真实计算机包含的一些以上未列出的指令，例如，指数运算一般情况下不是常量时间的指令。然而，在受限情况下，指数运算是一种常量时间的操作（’左移指令”）
RAM没有对常见的存储器层次进行建模
- 有几种计算模型试图反映出存储层次的效果
- 有时在真实计算机上的真是程序中非常重要
- 这些计算模型复杂，比较难以运用
- RAM模型分析通常能够很好地预测实际计算机上的性能
I/O高效的算法分析
- **理解**：传统算法分析假设内存无限快，但现实中I/O（磁盘、网络）往往是瓶颈。I/O高效算法关注如何减少磁盘读写次数（如B树、外部排序）。
渐进分析
- O、Ω、Θ
最坏情况与评价情况
- **最坏情况**：算法运行时间的上界（保证性分析）
- **平均情况**：假设输入分布下的期望时间（更难分析）
- **理解**：最坏情况保证可靠性，平均情况反映实际性能。
递归三要素
- **终止条件**：最小子问题可直接求解
- **分解**：将原问题分解为子问题
- **求解合并**：将子问题的解合并为原问题的解
可分解的问题——分治法
不一定复用，问题求解是个递归的过程
子问题相互独立
经典例子：归并排序、快速排序、二分搜素
> if (终止条件) return 直接求解
>
> 分解为若干子问题
>
> 递归求解每个子问题
>
> 合并子问题的解
对于不可分解的问题，采用缩小问题规模，分治法
- 子问题重叠，不是独立分解
- 经典例子：动态规划、回溯法
- **理解**：这类问题往往需要记录中间结果（复用）或探索解空间（剪枝）
算法分析的三个方法
顺序算法分析的基本方法
1. 评价算法的标准
- 正确性
- 时间复杂度
- 空间复杂度
- 稳定性（排序算法）
- 适应性（是否依赖输入特性）
算法复杂性的估计
- 渐进分析
- 摊还分析（Amortized Analysis）
- 平摊分析（平均每次操作的成本）
问题复杂性的下界
- **理解**：任何算法解决该问题都至少需要这么多时间
- 例如：比较排序的下界是 Ω(n log n)
算法分析的实例
- **排序算法**：插入排序、归并排序、快速排序、堆排序
- **查找算法**：二分查找、哈希查找
- **图算法**：DFS、BFS、Dijkstra、Floyd
- **字符串匹配**：KMP、Boyer-Moore
- **动态规划**：背包问题、LCS、矩阵链乘
计算复杂性理论的基本概念
1. **基本概念**
- **可计算性**：哪些问题可以用算法解决
- **复杂性**：解决问题需要多少资源（时间、空间）
2. 图灵机
- 确定性图灵机（DTM）
- 非确定性图灵机（NTM）
- **理解**：图灵机是算法能力的理论边界模型
3. 复杂性类
- **P**：多项式时间可解
- **NP**：多项式时间可验证
- **NPC（NP完全）**：NP中最难的问题，如果有一个多项式解，则所有NP问题都可多项式解
- **NP-hard**：至少和NP问题一样难，但不一定在NP中
4. NP完全性理论及其应用
- 典型NPC问题：SAT、旅行商问题（TSP）、背包问题、图着色
- **理解**：遇到NPC问题，不追求精确解，而是寻找近似解或启发式算法
创造新的服务是有人需要的
1、 问题新认识——来自用户的需求
2、 不准确、效率不高——根据问题的特征来解决问题
提高效率的两种方法
1、计算结果的复用——动态规划
- **适用条件**：
- 最优子结构
- 重叠子问题
- **实现方式**：记忆化搜索（自顶向下）或递推（自底向上）
2、减小搜索空间——回溯法+剪枝
- **核心思想**：在解空间树中搜索，遇到不可能的分支就提前返回
- **剪枝策略**：
- 可行性剪枝
- 最优性剪枝（上界/下界估计）
- 对称性剪枝
- **理解**：回溯法本质是暴力搜索 + 智能剪枝
**近似算法**
## 算法入门
算法是对特定问题求解步骤的一种描述，是若干个指令的有穷序列，满足性质/特征：
1. 0或多个输入
2. 1或多个输出
3. 有穷性 每条指令的执行次数是有限的、执行每条指令的时间也是有限的
4. 确定性 组成算法的每条指令是清晰的、无歧义的
5. 可行性
因此算法具有正确性、可读性、健壮性、（可使用性）、效率与低存储量需求
一个算法是由控制结构（顺序、分支和循环3种）和原操作（固有数据类型的操作）构成的。（或者说每一行代码所运行的操作）
从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间复杂度
算法的效率
1. 事后统计的方法
2. 事前估计的方法
问题规模n，输入序列I，算法本身A
书写程序的语言
编译程序所产生的机器代码质量
机器执行指令的速度
算法的正确性
不正确的算法不是都没用
1. 近似
2. 模拟
找不到精确解就找一个近似的解
可计算性
理论上判断什么问题可以给出算法利用计算机求解，什么问题不可以，属于“可计算性理论”
研究的问题
比如“停机问题”就是不可计算的
可计算理论认为可计算的问题，都有求解的算法，这样的算法不是唯一的
### 插入排序
排序问题
输入:n个数\
输出：输入序列的一个排列(重新排序)
$,使得a'1≤a'2...≤a'n$
插入排序算法思想:
伪代码：
INSERTION-SORT(A) cost times
```
for j<-2 to length[A]
do key <-A[j]
Insert A[j] into the sorted sequence A[1...j-1].
i<-j-1
while i>0 and A[i] >key
do A[i+1] <-A[i]
i<-i-1
A[i+1]<-key
```
| line | cost | times |
| ------------------------------------------------ | ---- | ---------------------- |
| for j<-2 to length[A] | c1 | n |
| do key <-A[j] | c2 | n-1 |
| Insert A[j] into the sorted sequence A[1...j-1]. | 0 | n-1 |
| i<-j-1 | c4 | n-1 |
| while i>0 and A[i] >key | c5 | $\sum_{j=2}^{n} t$ |
| do A[i+1] <-A[i] | c6 | $\sum_{j=2}^{n} (t-1)$ |
| i<-i-1 | c7 | $\sum_{j=2}^{n} (t-1)$ |
| A[i+1]<-key | c8 | n-1 |
sort(首地址，尾地址+1，[cmp函数])缺省为递增排序。
浮点数不建议用等号直接判断，fabs(x.score-y.score)>0.01,来比较
欣赏美的水平，并不是说AI能去做我们就不做了。
### 循环不变式与插入排序的正确性
**(Loop invariants and the correctness of insertion sort)**
三条重要性质：
- **初始化(Initialization)**：循环的第一次迭代之前，循环不变式为真。
- **保持(Maintenance)**：循环过程中每次迭代前后，循环不变式为真，布尔性质保持不变。
- **终止(Termination)**：循环终止时，不变式返回正确的结果，并且能够证明算法的正确性。
评：除了插入排序（左边排好序右边未排序），典型的还有二分查找（if判断中左边check为true右边check为false或者左边check为false右边check为true），这些算法都具有明显的二段性。
循环不变式
在循环内及循环结束的时候都成立的表达式
如果在循环的每一步，这个式子都是正确的，那么循环结束后，这个式子也正确，并得到了期望的结果
用于证明算法 的正确性
初始化：它在循环的第一轮迭代开始之前，应该是正确的
保持：如果在循环的某一次迭代开始之前它是正确的，那么在下一次迭代开始之前，它也应该保持正确
终止：当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。
第一类归纳法要从n证明到n+1
1. n=1的时候P(1)成立
2. 假设k=n时，P（n）成立
3. 证明P(n+1)的成立，那么P(n)对于一切正整数都成立
**理解**：如果假设(2)成立，即：命题P(n)成立，推出命题P(n+1)成立（n为任意正整数，表明该推导数量的无穷性）。根据此假设，可以得到P(n)→P(n+1)为真，亦即有：**P(1)→P(2)，P(2)→P(3)，P(3)→P(4)，...，P(n)→P(n+1)**为真，则得P(n)成立。
第二类数学归纳法
1. n=1时P（1）成立
2. 假设对于正整数k，nn=2
P1->p2
P1,P2 n ≤2 =>n=3
P1,P2->P3
P1,...,pk=>Pk+1
第一数学归纳法和第二数学归纳法
第一数学归纳法
1. 验证n=1时，命题成立；
2. 假设n=k时，命题成立；
3. 证明n=k+1时，命题成立
则命题对任意正整数n成立
第二数学归纳法：
1. 验证n=1和n=2成立
2. n B[选择数据结构和算法设计策略]
B -->C[描述算法]
C -->D[证明算法正确性]
D -->E[算法分析]
```
## 伪代码
- 在伪代码中，每一条指令占一行(else if 例外)，指令后不跟任何符号；
- “缩进”表示程序中的分支程序结构（缩进表示块结构；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进）；
- 通常每个算法开始时都要描述它的输入和输出，而且算法中的每一行都给编上行号，在解释算法的过程中会经常使用算法步骤中的行号来指代算法的步骤；
- 每一行可以加上编号（也可不加）。
**1.变量的声明**
算法中出现的数组、变量可以是以下类型：整数、实数、字符、字符串或指针。定义变量的语句不用写出来，但必须在注释中给出。
伪代码程序中的变量都是局部变量。在没有显式说明的情况下，不使用全局变量
通过数组名[下标]的形式访问数组元素，伪代码中一般使用 1 作为第一个元素下标，但高级语言中一般使用 0 作为第一个元素下标。
用符号“..” 来表示数组中的一个取值范围。A[1...j]就表示A[1]..A[j]
也就是说，对于A[i:j],算法导论中有j-i+1个元素
而python中，却是只有j-i个元素
但是呢，算法导论是从1开始，python从0开始
实质上没有区别
**对象可由一组属性构成。**
**伪代码中函数传参按照值传递。**
**多重赋值 i<-j<-e将表达式e的值赋给变量j和i**
**（相当于i=j=e）**
**变量（如i，j和key）是局部于给定过程的，在没有显示说明的情况下，我们不使用全局变量**
**评：函数传参有三种方式：值传递，地址传递，引用传递（应注意C语言没有引用）。**
**参数采用按值传递的方式，且传递的是引用（指针），那么是“引用的值被复制”，当对象被传递时，实际传递的是对象引用的拷贝（指向该对象数据的指针值的拷贝），而对象的各个域则不被拷贝（对象本身不被拷贝）。例如，x是某个被调用过程的参数，在被调过程中的赋值x<-y对主调过程是不可见的，但是f[x]<-3是可见的。**
1. **按值传递（True pass-by-value）：**
- **完整拷贝对象及其所有数据**
- **所有修改对调用方都不可见**
- **典型语言：C++（非引用参数）、Java基本类型**
2. **按共享传递（Pass-by-sharing）：**
- **拷贝对象引用（指针），不拷贝对象数据**
- **修改引用不可见，修改数据可见**
- **典型语言：Python、Java对象类型**
3. **按引用传递（Pass-by-reference）：**
- **直接传递原始变量的引用**
- **所有修改对调用方都可见**
- **典型语言：C++引用参数、C# ref参数**
**# Python示例（按共享传递）**
**def modify(obj):**
**obj = [4,5,6] # 修改引用，外部不可见**
**obj[0] = 100 # 修改数据，外部可见**
**original = [1,2,3]**
**modify(original)**
**print(original) # 输出[100, 2, 3] 而非[4,5,6]**
1. **对被调用过程中：**
- **重新赋值参数变量（如x←y）不会影响调用方**
- **通过引用修改对象内容（如f[x]←3）会影响调用方"**
**前句说传递"对象的一个拷贝"，后句又说"对象的各个域不被拷贝"，这是自相矛盾的。正确的表述应该是：**
- **浅拷贝（shallow copy）：拷贝对象引用（指针），但不拷贝引用指向的数据。**
- **深拷贝（deep copy）：拷贝对象及其所有嵌套数据**
**"对象的一个拷贝"是浅拷贝还是深拷贝？**
**答案：取决于上下文，但通常指浅拷贝（除非明确说明是深拷贝）。**
**. 按值传递（Pass-by-value）是浅拷贝还是深拷贝？**
**答案：取决于数据类型，但严格来说，按值传递是值的完整拷贝。**
- **基本类型（int, float, bool 等）：**
- **按值传递 = 深拷贝（完全独立的副本）。**
- **例如：C/C++ 的 int、Java 的 int、Python 的不可变类型。**
- **对象/引用类型（类实例、数组、字典等）：**
- **按值传递 = 浅拷贝（传递的是引用的拷贝，而非对象本身）。**
- **例如：Java 的对象、Python 的列表/字典。**
- **按值传递的本质是拷贝变量的值。**
- **如果是基本类型，拷贝的是实际值（深拷贝）。**
- **如果是引用类型，拷贝的是指针/引用（浅拷贝）。**
**// Java 示例（按值传递，但对象是浅拷贝）**
**void modify(List list) {**
**list = new ArrayList<>(Arrays.asList(4, 5, 6)); // 新引用，外部不可见**
**list.set(0, 100); // 修改引用指向的数据，外部可见**
**}**
**List original = new ArrayList<>(Arrays.asList(1, 2, 3));**
**modify(original);**
**System.out.println(original); // 输出 [100, 2, 3]（证明是浅拷贝）**
**. 按共享传递（Pass-by-sharing）是浅拷贝还是深拷贝？**
**答案：浅拷贝（传递的是引用的拷贝）。**
- **按共享传递（如 Python、Java 的对象传递）本质上是按值传递引用。**
- **即传递的是对象的指针/引用的拷贝，但对象本身不拷贝。**
- **因此，修改引用指向的数据会影响原对象（浅拷贝行为）。**
**示例：**
**python**
**def modify(obj):**
**obj[0] = 100 \*#\* \*修改引用指向的数据，外部可见\***
**original = [1, 2, 3]**
**modify(original)**
**print(original) \*#\* \*输出 [100, 2, 3]（浅拷贝行为）\***
| **概念** | **拷贝方式** | **是否拷贝数据** | **影响原对象** | **典型语言/场景** |
| ------------------------ | ---------------- | ---------------- | -------------------- | ------------------------------------- |
| **浅拷贝** | **仅拷贝引用** | **❌ 不拷贝数据** | **✅ 修改影响原对象** | **Python list.copy(), Java clone()** |
| **深拷贝** | **递归拷贝数据** | **✅ 完全拷贝** | **❌ 不影响原对象** | **Python copy.deepcopy()** |
| **按值传递（基本类型）** | **深拷贝** | **✅ 完全拷贝** | **❌ 不影响原变量** | **C int, Java int** |
| **按值传递（引用类型）** | **浅拷贝** | **❌ 仅拷贝引用** | **✅ 修改影响原对象** | **Java 对象、Python 列表** |
| **按共享传递** | **浅拷贝** | **❌ 仅拷贝引用** | **✅ 修改影响原对象** | **Python、JavaScript** |
1. **可见性规则表述不严谨：**
- **"x<-y不可见但f[x]<-3可见"的表述过于绝对。正确的可见性规则应明确取决于：**
- **如果传递的是对象引用的拷贝：**
- **修改引用本身（如x = y）对调用方不可见**
- **通过引用修改对象内容（如f[x] = 3）对调用方可见**
- **如果传递的是完整对象拷贝：**
- **所有修改都对调用方不可见**
```mermaid
graph TD
A[参数传递方式] --> B[按值传递]
B --> C[深拷贝对象]
A -->D[按引用传递]
A --> E[按共享传递]
E --> G[拷贝对象引用]
E--> H[不拷贝对象数据]
```
**返回(return)语句执行后将返回到函数的调用点，大多数返回语句能返回一个值，伪代码中可以返回多个值。**
**评：一些高级语言例如C++不支持多个返回值，一般就采用全局变量，引用传递，结构体，元组等方式，伪代码支持多返回值会非常方便。**
**布尔运算符”and“和”or“都是短路的。**
**关键词error表示已调用过程不对，出现了错误。**
**2.指令的表示**
在算法中的某些指令或子任务可以用文字来叙述，例如，”设x是A中的最大项”，这里A是一个数组；或者”将x插入L中”，这里L是一个链表。这样做的目的是为了避免因那些与主要问题无关的细节使算法本身杂乱无章。
**3.表达式**
算术表达式可以使用通常的算术运算符（+，-，*，/，以及表示幂的^）。逻辑表达式可以使用关系运算符 = 、≠、<、>、≤ 和 ≥，以及逻辑运算符与(and)、或（or）、非（not）。
**4.赋值语句**
赋值语句是如下形式的语句：a←b 。或者sum=0；
这里a是变量、数组项，b是算术表达式、逻辑表达式或指针表达式。语句的含义是将b的值赋给a。
变量交换：若a和b都是变量、数组项，那么记号a<->b 表示a和b的内容进行交换。
**5.goto语句**
goto语句具有形式：
goto label（goto标号）
它将导致转向具有指定标号的语句。
**6.分支结构 if then else**
条件语句：
if i=10
then xxxx
else xxxx //else 和 then 要对齐
//或者
if i=10
then xxxx //if 后面必定跟上then，else后面不用跟then
elseif i=9 //elseif 要连在一起写
then xxxx
yyyy
else xxxx //else 跟在 elseif 的 then 对齐
**7.循环结构**
有两种循环指令：while和for、repeat
while语句的形式是：
while time<10
do xxxxx //while后面必定要紧跟缩进的do
xxxxx
end
for语句的形式是：
for var init to limit by incr
do s
end
这里var是变量，init、limit和incr都是算术表达式，而s是由一个或多个语句组成的语句串。初始时，var被赋予init的值。假若incr≥0，则只要var≤limit，就执行s并且将incr加到var上。（假若incr<0，则只要var≥limit，就执行s并且将incr加到var上）。incr的符号不能由s来该改变。
For i=1 to n
**8.程序的结束**
exit语句可以在通常的结束条件满足之前，被用来结束while循环或者for循环的执行。exit导致转向到紧接在包含exit的（最内层）while或者for循环后面的一个语句。
return用来指出一个算法执行的终点；如果算法在最后一条指令之后结束，它通常是被省略的；它被用得最多的场合是检测到不合需要的条件时。return的后面可以紧接被括在引号的信息。
**9.注释风格**
算法中的注释被括在 //或者/* */ 之中。或者是“▷”
**10.函数的编写**
函数的伪代码格式例子为：search（A，name）， 参数类型可以不给出，但必须在注释中说明。
11. 复合数据
复合数据一般组织成对象，它们是由属性或域所组成的，每个属性（域）存储特定的值。这些属性可以是数据（数字、字符串、数组），也可以是函数（方法），它们最终对应特定的值。访问对象的属性/域的访问是由域（属性）名后跟由方括号的对象名形式来表示。例如：数组可以被看做是一个对象，其属性有length，表示数组中元素的个length[A]。
**什么是“域的访问”？**
所谓“访问”，就是**取出（读取）或修改**对象中的某个属性。
在伪代码中，访问语法可能会这样写：
name[person] // 表示“访问person对象的name属性”
相当于其他语言中更常见的写法：
Js
person.name // JavaScript语法
person["name"] // 等价写法
用于表示一个对象的变量被看作是指向该对象的一个指针。这样，多个变量指向同一个对象，修改一个会影响另一个
## 描述运行时间
l 算法，算法复杂度的基本概念；
l 时间复杂度的估算方法；
l 算法分析的数学基础，函数的渐近的界，递推方程求解方法。
l 算法复杂性：时间复杂性、空间复杂性、最优算法
l 算法复杂性分析：最坏情况和平均情况分析、如何估算运行时间
一般来说，算法所需时间是与输入规模同步增长的，因而一个程序的运行时间是其输入的函数。
输入规模：最自然的度量标准是输入中的元素个数
算法的运行时间
1、 独立于具体机器的“步骤”概念
2、 假定每次执行第i行所花的时间都是常量$c_i$
评价一个算法可以从不同方面来考虑，如正确性，简单性、时间复杂性、空间复杂性
还可以提出求解某问题的最优算法
时间复杂性归结为某些基本操作的次数问题，基本操作的次数与问题的规模有关。我们一般考虑对基本操作的次数影响最大的量。
算法效率
求解同一个问题，不同的算法效率或复杂性不同
渐进复杂性
$$
\underset{n\rightarrow \infty}{\lim}\frac{T\left( n \right) -T^*\left( n \right)}{T\left( n \right)}=0
$$
设算法的运行时间为T（n），如果存在T*(n)
T*(n)称为算法的渐进性态或渐进时间复杂性
$$T^*\left( n \right) =7n^3
\\
\underset{n\rightarrow \infty}{\lim}\frac{T\left( n \right) -T^*\left( n \right)}{T\left( n \right)}=\underset{n\rightarrow \infty}{\lim}\frac{6n^2+5n+4}{7n^3+6n^2+5n+4}=0
\\
\text{当}n\rightarrow \infty ,T^*\left( n \right) =7n^3=n^3$$
N为算法中的问题规模，通常用大O/Ω/Θ等三种渐进符号表示算法执行时间和n之间的一种增长关系
算法:分析问题规模n，找出基本语句，求出其运行次数f(n).用O、Ω、Θ来表示其阶
#### 渐进记号
紧确XX
##### 渐进（紧）确界
$$\varTheta \left( g\left( n \right) \right) =\left\{ f\left( n \right) ,\exists c1,c2,n0,\forall n\ge n0,0\le c1g\left( n \right) \le f\left( n \right) \le c2g\left( n \right) \right\} $$
也可以表示成
$$f\left( n \right) \subseteq \Theta \left( g\left( n \right) \right) $$
$$f\left( n \right) =\varTheta \left( g\left( n \right) \right) $$
一个渐进正函数中低阶项在决定渐进确界时可以被忽略
高阶项的系数也可以忽略
##### 渐进上界
$$O\left( g\left( n \right) \right) =\left\{ f\left( n \right) :\exists c,n0,\forall n\ge n0,0\le f\left( n \right) \le cg\left( n \right) \right\} $$
$$\Theta \left( g\left( n \right) \right) \subseteq O\left( g\left( n \right) \right) $$
用O表示$T(n)=7n^3+6n^2+5n+4$的阶
1. 带入定义：$7n^3+6n^2+5n+4\leq{cf(n)}$
2. 如何取出c和n0？
3. 升阶:$7n^3+6n^2+5n+4\leq7n^3+6n^3+5n^3+4n^3=22n^3$
4. 存在c=22，n0=1,使得$n\geq{n0}$,令$f(n)=n^3$,$T(n)\leq{cf(n)=22n^3}$,即$T(n)=O(f(n))=O(n^3)$
直接升到最高次项
##### 渐进下界
$$\Omega \left( g\left( n \right) \right) =\left\{ f\left( n \right) :\exists c,n0,\forall n\ge n0,0\le cg\left( n \right) \le f\left( n \right) \right\} $$
$$\Theta \left( g\left( n \right) \right) \subseteq \Omega \left( g\left( n \right) \right) $$
删阶
用Ω表示$T(n)=7n^3+6n^2+5n+4$的阶
1. 带入定义：$7n^3+6n^2+5n+4\geq{cf(n)}$
2. 如何取出c和n0？
3. 升阶:$7n^3+6n^2+5n+4\geq7n^3$
4. 存在c=7，n0=1,使得$n\geq{n0}$,令$f(n)=n^3$,$T(n)\geq{cf(n)=7n^3}$,即$T(n)=Ω(f(n))=Ω(n^3)$
上界的阶越小，下界的阶越高，结果就越有价值
定理：$ 对于任意两个函数f(n)和g(n),f(n)=\Theta(g(n))当且仅当f(n)=\Omega (g(n))和f(n)=O(g(n))$
函数间关系
- f(n)和g(n)都是渐近正值函数
- 传递性：
- $$
f(n)=\Theta(g(n))和g(n)=\Theta(h(n))蕴含f(n)=\Theta(h(n))\\
f(n)=O(g(n))和g(n)=O(h(n))蕴含f(n)=O(h(n)) \\
f(n)=\Omega(g(n)) 和g(n)=\Omega(h(n))蕴含f(n)=\Omega(h(n))
$$
渐近记号$\ O \Omega \Theta$ 规律：若T(n)是一个一元多项式，最高项次数是$n^m,T(n)=O(n^m)=\Omega(n^m)=\Theta(n^m)$
时间复杂度排行$O(1)b
对于函数，三分性不成立，对于两个函数f(n)和g(n),可能$f(n)=O(g(n))和f(n)=\Omega(g(n))$都不成立
$n和n^{1+sin{n}}$无法利用渐近符号来比较
时间复杂度与空间复杂度
空间复杂度
一个算法的存储量包括形参所占空间和临时变量所占空间，在进行存储空间分析时，之考察临时变量所占空间
1、 静态分析
一个算法静态使用的存储空间，称为静态空间。静态分析的方法比较容易，只要求算法中所使用的所有变量的空间，再折合成多少空间存储单位
2、 动态分析
一个算法执行过程中，必须以动态方式分配的存储空间是指算法执行过程中分配的空间，称为动态空间。动态控件主要是存储中间结果或操作单元所占用空间
原地工作并非不需要额外空间，只是说额外空间不随数据大小的增长而增长
例如，以下算法中临时变量i、maxi占用的空间。所以，空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作：
$S(n)=O(g(n))、\Omega(g(n))或\Theta(g(n))$
其中渐进符号的含义与时间复杂度中的含义相同。
```
int max(int a[],int n)
{int i,maxi=0;
for (int i=1;ia[maxi])
maxi=i;
return a[maxi];
}
```
函数体内分配的变量空间为临时空间，不计形参占用的空间，这里的仅计i、maxi的空间，空间复杂度为O(1)
```
void func(int n)
{
int i,k=100;
while (i<=n)
{
k++;
i+=2;}
}
```
临时分配了i、k两个变量的空间，它与问题规模n无关，空间复杂度为O（1），即该算法为原地工作算法。
有如下递归算法，分析调用maxelem(a,0,n-1)的空间复杂度
```
int maxelem(int a[],int i,int j)
{
int mid(i+j)/2,max 1,max2;
if (imax2)?max1:max2;
}
else return a[i];
}
```
每次调用只临时分配3个整型变量的空间(O(1))
调用maxelem(a,0,n-1)的空间为S(n),有
>S(n)=O(1) ,当n=1
>
>S(n)=2S(n/2)+O(1),当n>1
$S(n)=2S(n/2)+1=2[2S(n/2^2)+1]+1=2^2S(n/2^2)+1+2^1 \\=2^3S(n/2^3)+1+2^1+2^2 \\= ... =2^k S(n/2^k)+1+2^1+...+2^{k-1}(设n=2^k,k=log_2^n) \\ =n*1+2^k-1=2n-1=O(n)$
一些函数
单调性
- 单调递增：$m\leq n$蕴含$f(m)\leq f(n)$
- 单调递减：$m\leq n$蕴含$f(n)\leq f(m)$
- 严格递增：$m< n$蕴含$f(m)0$
$\lceil \lceil n/a \rceil /b \rceil =\lceil n/ab \rceil$
$\lfloor \lfloor n/a \rfloor /b \rfloor =\lfloor n/ab \rfloor$
$\lceil a/b \rceil \leq (a+(b-1))/b$
$ \lfloor a/b \rfloor \geq (a-(b-1))/b$
取模运算
$a \ \ mod \ \ n =a- \lfloor a/n \rfloor *n$
$a \mod n =b \mod \ n,a \equiv b \ (mod \ n)$
$a \mod n \ne b mod n,a \not \equiv b \ (mod \ n) $
等价的，$a \equiv b \ (mod n)$当且仅当n 是b-a的一个约数
多项式
给定一个正整数d,n的d次多项式是具有如下形式的函数p(n):
$$p\left( n \right) =\sum_{i=0}^d{a_in^i}$$
$a_d \neq 0$
一个多项式是渐进正的，当且仅当$a_d > 0$
对于一个d次的渐进多项式p(n),$p(n) = \Theta (n^d)$
对于任意实常数$a \ge 0,n^a 单调递增$
对于任意实常数$a \le 0,n^a 单调递增$
指数式
对于任意实数a和b，且a>1 。
增长关系
$\lim_{x \rightarrow a} \frac {n^b}{a^n}=0，即n^b =o(a^n)$
对任意实数x
$e^x=1+x+\frac{x^2}{2!}+...=\Sigma_{i=0}^\infty \frac{x^i}{i!} \\ e^x\ge 1+x \\ lim_{n\rightarrow \infty } \left( 1+\frac{x}{n} \right) ^n$
当$|x|\le1$
$1+x\le e^X\le 1+x+x^2$
当$x\rightarrow 0$
$e^x = 1+x+\Theta(x^2)$
约定下列记号：
$$\lg _{n}=\log _{n}^{2} $$
$ln_{n} =log_{e}^{n},lg^{k}n=(lg \ n)^k,lg\ lg\ n=lg(lg\ n)$
$|x|<1:$
$ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}$
泰勒展开：
$f(x)=f(0)+f'(0)x+f''(0)(\frac{x^2}{2})+...$
当$x>-1$
$\frac{x}{x+1}\le ln(1+x)\le x$
对于任意常数a>0
$\lim_{n\rightarrow \infty} \frac{n^b}{a^n}=0，当(n=lgn,a=2^a),lg^bn=o(n^a)$
因此任意正多项式函数都比多项对数函数增长的快
多重对数函数
设$lg^{i}n如上定义，其中f(n)=lg\ n,由于lg^{i} n有定义当且仅当lg^{(i-1) n}>0$
多重对数的定义为:
$lg^{*}n=min \{i \ge0:lg^{(i)}n \le 1 \}$
注意区分$lg ^{(i)}n 和lg ^{i} n$
多重对数函数是一种增长很慢的函数：
$lg^{*}2=1,lg^*4=2,lg^*16=3,lg*65536=5,lg*2^{65536}=6$
阶乘
定义
\[
n!=\left \{ \begin{array}{ll} 1 & n=0 \\ n \times (n-1)! & n>0\end{array}\right.
\]
斯特林公式$n!=\sqrt{2\pi n} (\frac{n}{e})^n (1+\Theta(\frac{1}{n}))$
可以证明
$n!=o(n^n),n!=\omega(2^n),lg(n!)=\Theta(n\ lg\ n)$
对于任意$n \ge 1 \\ n!=\sqrt{2\pi n} (\frac{n}{e})^2e^{a_n},\\ 其中\frac{1}{12n+1} < a_n <\frac {1}{12n}$
函数迭代
\[
f^{(i)} (n) =
\begin{cases}
n & \hfill \text{if } i=0 \\
f(f^{(i-1)} (n)) & \hfill \text{if } i>0 \\
\end{cases}
\]
$f(n)=2n,f^{(i)}(n)=2^i n$
递归定义
斐波那契数列和黄金分割率及其共轭数有关系，它们有如下关系：、
$F0=0,F1=1,F_i=F_{i-1}+F_{i-2} \\ \phi =\frac{1+\sqrt{5}}{2} \\ \hat{\phi}==\frac{1-\sqrt{5}}{2},\\F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$
即斐波那契数列以指数形式增长
算法分析技术
最坏情况和平均情况分析
递归式
递归算法采用一种分而治之的方式，把一个大问题分解为若干个相似的小问题
关键时根据递归过程建立递推关系式，然后求解这个递推关系式，得到一个表示算法执行时间的表达式，最后用渐进符号来表示这个表达式即得到算法的时间复杂度
递归式就是一个等式，它通过通常更小的函数参数值来描述一个函数。
递归算法:
```
void mergesort(int a[],int i.int j)
{
int m;
if (i!=j)
{
m=(1+j)/2
mergesort(a,i,m);
mergesort(a,m+1,j);
merge(a,i,j,m);
}
}
```
mergesort()用于数组a[0...n01]（设n=2^k.这里的k为正整数)的归并排序。
调用该函数方式为mergesort(a,0,n-1)
merge(a,i,j,m)用于两个有序子序列a[i...j]和a[j+1...m]的有序合并，是非递归函数，它的时间复杂度为O(n)(n=j-i+1)
设mergesort(a,0,n-1)的执行时间为T（n)
由其执行过程得到以下求执行时间的递归关系（递推关系式）
> T(n)=O(1)，当n=1
>
> T(n)=2T(n/2)+O(n),当n>1
其中O(n)为merge()所需的时间，设为cn(c为正常量)
$$
T(n)=2T(n/2)+cn=2^2T(n/2^2)+2cn \\ =2^kT(n/2^k)+kcn \\ =nO(1)+cnlog_2n // 假设n=2^k \\ = O(nlog_2n)
$$
## 递归算法
在定义一个过程或函数时出现调用本过程或者本函数的成分，称之为递归
若调用自身，称之为直接递归。若过程或函数p调用过程或函数q而q又调用p，称之为间接递归
任何间接递归都可以等价地转换为直接递归
如果一个递归过程或递归函数中递归调用语句时最后一句执行语句，则称这种递归调用为尾递归
```
int fun(int n)
{
if(n==1)
return (1);
else
return (fun(n-1)*n);
}
```
直接调用fun(n-1),所以一个直接递归函数，且是最后一条语句，又属于尾递归。
能够用递归的方法应该满足以下条件：
1、 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。
2、 递归调用次数必须是有限的（必须有一个明确的递归结束条件，或称为递归出口，否则将无限进行下去）
3、 必须有结束递归的条件来中止
缺点：运行效率较低，堆栈溢出
什么时候使用递归？
1、 定义是递归地，如n！或斐波那契数列
2、 数据结构是递归的，如链表
3、 求解的方法是递归的
**（1）** 能够分析算法时间复杂度；能够求解递归式。
**汉诺塔问题**
设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上。递归分解的过程是：
$$
Hanoi(n-1,x,z,y);\\
move(n,x,z);\text {将第n个圆盘从x移到z} \\
Hanoi(n-1,y,x,z);
$$
大问题转化为若干个小问题求解
递归模型是递归算法的抽象，它反映一个递归问题的递归结构。
求n! 的算法对应递归模型：
$$\left\{ \begin{array}{lr}
fun\left( 1 \right) =1, & \left( 1 \right)\\
fun\left( n \right) =n*fun\left( n-1 \right) & n>1 \left( 2 \right)\\
\end{array} \right. $$
(1)给出递归的终止条件。 （2）给出fun(n)与fun(n-1)之间的关系，前者称为递归出口，后者称为递归体。
一个递归模型是由递归出口和递归体两部分组成、
递归出口的一般格式如下：f(s1)=m1
递归体的一般格式如下：
$f(s_n+1)=g(f(s_i),f(s_{i+1}),...,f(s_n),c_j,c_{j+1},...,c_m)$
$s_{n+1}$是递归的“大问题”，$s_i,s_{i+1},s_n$为递归“小问题”，$c_j,c_{j+1},...,c_m$是若干个可以直接（用非递归）解决的问题，g是一个非递归函数，可以直接求值
S1与m1均为常量，有些递归问题可能有几个递归出口
递归算法的执行过程
递归程序虽然每次调用的是相同的子程序，但是它的参量、输入数据等均有变化
随着调用的不断深入，必定会出现调用到某一层的函数时，不再执行递归调用而种植函数的执行，即遇到递归出口。
递归调用是函数嵌套调用的一种特殊情况，即它是调用自身代码
由于每次调用时，它的参量和局部变量均不同，因而保证了各个复制执行时的独立性。
系统为每一次调用开辟一组存储单元，用来存放本次调用的返回地址以及被中断的函数的参量值。
这些单元以系统栈的形式存放，每调用一次进栈一次。当返回时出栈，把当前栈顶保留的值送回相应的参量中进行恢复，并按栈顶中的返回地址，从断点继续执行。
每递归调用一次，就需进栈一次。最多的进栈元素个数称为递归深度。当n越大，递归深度越深，开辟的栈空间也越大。
每当遇到递归出口或完成本次执行时，需要退栈一次，并恢复参量值，当全部执行完毕，栈应为空。
递归调用分两步：1分解过程，将大问题分解成小问题，直到递归出口。2、然后进行第二步的求值。即已知小问题求大问题
对于给定的含有n个元素的数组a，分别采用简单的选择排序和冒泡排序方法对其按元素递增排序
**简单选择排序**
f(a,n,i)用于对a[i...n-1]元素序列（共n-i个元素）进行简单的选择排序。是”大问题“
f(a,n,i+1)用于对a[i+1...n-1]元素序列（共n-i-1个元素）进行简单选择排序，是”小问题“
当i=n-1时所有元素有序，算法结束。
>f(a,n,i)=不做任何事情，算法结束.当i=n-1
>
>f(a,n,i)=通过简单比较挑选a[i...n-1]中的最小元素 a[k]放在a[i]处；否则f(a,n,i+1);
```
void SelectSort(int a[],int n,int i)
{
int j,k;
if (i==n-1) return ;//满足递归出口
else
{
k=i; //k记录a[i...n-1]中最小元素的下标
for (j=i+1;jf(a,n,i)=不做任何事情，算法结束.当i=n-1
>
>f(a,n,i)=对a[i...n-1]元素序列，从a[n-1] 开始进行相邻元素比较;否则
>
>若相邻元素反序则将两者交换
>
>若没有交换则返回，否则执行f(a,n,i+1);
整数划分问题：把一个正整数表示成一系列正整数之和
$$ n=n1+n2+..+n_k,n1 \ge n2 \ge ... \ge n_k \ge 1,k\ge 1$$
正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记为p(n)
p(6)=11
如果{n1,n2,..,ni}中最大加数s 不超过m，即s=max(n1,n2,...,ni)≤m
则称它属于n的一个m划分。我们记n的m划分个数为f(n,m).该问题就转化为求n的所有划分个数f(n,n)
f(n,m)的递归关系
1. f(1,m)=1,m≥1
当n=1时，不论m值为多少，只有一个划分即1个1.
2. f(n,1)=1,n≥1
当m=1，不论n的值为多少，只有一种划分即n个1
3. f(n,m)=f(n,n)，m≥n
最大加数实际上不能超过n。例如f(3,5)=f(3,3)
4. f(n,n)=1+f(n,n-1)
正整数n的划分是由s=n的划分和s≤n-1的划分构成。例如，f(6,6)=1+f(6,5)
5. f(n,m)=f(n,m-1)+f(n-m,m),n＞m＞1
正整数n的最大加数s不大于m的划分，是由s=m的划分(即有一个加数已经是m了)和s≤m-1的划分组成
\[
p(n)=f(n,m) =
\left\{
\begin{array}{ll}
1, &n=1,m=1 \\
f(n,n), & nm>1
\end{array}
\right.
\]
## 递推
递推问题求解的基本步骤
鸽巢原理也称抽屉原理，是组合数学中一个重要的原理.
l 重点：递推关系式求解方法
l 难点：分治递推关系求解
即使得不到通项公式，也可以用递推公式，加上循环得到。
除了循环（递推），还可以写成递归
能不用递归就不用递归，效率慢
自上而下是递归，自下而上是递推。
递推问题
[Problem - 2050](http://acm.hdu.edu.cn/showproblem.php?pid=2050)
首先，确认能否容易得到最简单情况的解（n=1、2）
然后，假设规模为N-1的情况已经得到解决
最后。当扩大到N，求递推公式。
1. 空间换时间的思想，程序实现的时候开辟一个数组
2. 并不一定是N-1到N的分析
[Problem - 2046](http://acm.hdu.edu.cn/showproblem.php?pid=2046)
先前的递推，是根据N-1，来分析加上N的结果
这个题目时将大问题分解成小问题
首先将根据最后一列是竖着还是横着放分成两种
竖着放，那么剩下的N-1列随便排
横着放，剩下的N-2列随便排
2. 骨牌铺满方格
[Problem - 1297](http://acm.hdu.edu.cn/showproblem.php?pid=1297)
找合法的情况
1、队列尾是M,那么前面N-1是合法的，他就是合法的；如果是非法的，就是非法的。
2、队列尾是F，那么倒数第二个必须是F；那么N-2个前面的，如果合法，则合法；如果非法，也不一定；再根据两个，如果MF，则合法。因此三种情况合法。
可以推出二维的公式
$$\begin{cases}
F_1\left( n \right) =F_1\left( n-2 \right) +2F_2\left( n-2 \right)\\
F_2\left( n \right) =F_1\left( n-2 \right) +F_2\left( n-2 \right) +F_2\left( n-3 \right)\\
F\left( n \right) =F_1\left( n \right) +F_2\left( n \right)\\
\end{cases}$$
或者
$$\begin{cases}
F_1\left( n \right) =F_1\left( n-1 \right) +F_2\left( n-1 \right)\\
F_2\left( n \right) =F_1\left( n-2 \right) +F_2\left( n-1 \right)\\
F\left( n \right) =F_1\left( n \right) +F_2\left( n \right)\\
\end{cases}$$
长度为n的字符串，用HDU来，但是H后面不能接D，D后面不能接U。请问有多少种可能？
$$\begin{cases}
H_n=H_{n-1}+D_{n-1}+U_{n-1}\\
D_n=D_{n-1}+U_{n-1}\\
U_n=H_{n-1}+U_{n-1}\\
\end{cases}$$
总而言之，就是找合法的结果。非法的如何变成合法就是关键。不能有遗漏和重复。
[Problem - 2045](http://acm.hdu.edu.cn/showproblem.php?pid=2045)
同样的，如果N-1合法，那么最后一个只有一种情况。
如果N-1不合法，那么只可能是首尾不一样，那么最后一个有两种 情况
因此为F(n)=F(n-1)+2F(n-2)
[Problem - 1465](http://acm.hdu.edu.cn/showproblem.php?pid=1465)
有 n封信和 n 个对应的信封，把所有信都装错信封（即没有一封信装入它对应的信封），求装法的总数 Dn（称为**错排数**）。D1=0,D2=1
考虑第 n 封信，它不能装进第 n 个信封，所以它只能放进前 n-1 个信封中的某一个，有 n−1 种选择。
当N-1封全错，任意一个和第N个交换，就构成了全错的情况，
当N-1封有对的一个，即N-2封错的，那就把那一个和第N个交换,就构成了全错
或者假设第 n 封信放进了第 k 个信封（k ≠ n），那么第 k 封信有两种情况：
- 第 k 封信放进第 n 个信封 → 剩下的 n-2 封信错排，即 Dn−2种。
- 第 k 封信不放进第 n 个信封 → 相当于把第 k 封信和剩下的n-2封信看作“禁止对应”的新问题，等价于 n-1 封信的错排，即 Dn−1种。
递推公式:
$D(n)=(n-1)(D_{n-1}+D_{n-2})$
圆连线问题
圆周上按顺序标有2n个点，顺时针或者逆时针围成一个圆，将n个线段把这2n个数字连在一起，线段不交叉一共有多少种？
固定一个点，比如1号点，它必须连到某个偶数号点。
假设1号点连到2k号点，那么圆被分成两段弧，分别有2k-2和2n-2k个点。
$C_n=\Sigma_{k=1}^n C_{k-1}C_{n-k}$
F0=1
$F_n=\Sigma_{i=0}^{n-1}F_iF_{n-1-i}$
k-1=i
优美的卷积公式
卡特兰数列
$$C_n=\frac{\left( \begin{array}{c}
2n\\
n\\
\end{array} \right)}{n+1}$$
爬楼梯
搞定一步就可以了，走到第n层，要么n-1，要么n-2
$F1=1,F2=2,F_n=F_{n-1}+F_{n-2}$
## 分治法
l 排序算法：合并排序、快速排序、随机排序
l 寻找中项和第K小元素
l 大整数乘法
l 矩阵乘法
l 最近点对问题
基本情况：问题足够小我们可以直接解决，不需要递归
分解（divide）：将原问题分解成一些列子问题，形式与原问题一致
求解（conquer）：递归地求解各子问题，若子问题足够小，则停止递归，直接求解
归并（merge）：将子问题的解合并成原问题的解
各个子问题独立，即子问题之间不包含公共的子问题。
对于一个规模为n的问题:若该问题可以容易地解决则直接解决，否则将其分解为k个规模较小的子问题。子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。即分治法。
问题特征：
1. 该问题的规模缩小到一定的程度就可以容易地解决
2. 该问题可以分解为若干个规模较小的相同问题
3. 分解出的子问题的解可以合并为该问题的解
4. 各个子问题相互独立，即子问题之间不包含公共子问题
divide-and-conquer (P)
```
{
if |P|≤n0 return adhoc(P);
将P分解为较小的子问题P1,P2,..,Pk；
for (i=1;i≤k;i++)//循环处理k次
yi=divide-and-conquer(Pi)//递归解决Pi
return merge(y1,y2,...,yk)//合并子问题
}
```
原问题应该分为多少个子问题才较适宜？子问题的规模应该怎样才为适当？
这些问题很难予以肯定的回答。但用分治法设计算法时，最好使子问题的规模大致相同。
换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。
k=1，减治法；k=2，称为二分法；
分治法是问题分成多个子问题，然后最后将问题合并起来，从而求得其解。
减治法是将问题分解，但是没有将解合并，解就在子问题的解中。折半查找属于减治法。
### 折半查找
```
int BinSearch(int a[],int low,int high,int k)
{
int mid ;
if (low <=high)
{
mid=(low+high)/2;
if (a[mid]==k)
return mid;
if (a[mid]>k)
return BInsearch(a,low,mid-1,k)
else
return BinSearch(a,mid+1,high,k)
}
else return -1;
}
```
折半查找算法的主要时间花费在元素比较上，对于含有n个元素的有序表，采用折半查找时最坏情况下的元素比较次数为C(n)
> C(n)=1,当n=1
>
> $C(n)\le 1+C(\lfloor n/2 \rfloor)$,当n≥2
由此得到:$C(n)\le \lfloor log_2 n \rfloor+1$
折半查找的主要时间花在元素比较上，所以算法的时间复杂度为$O(log_2 n)$
### 快速排序
基本思想：在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在两个子序列中间，这个过程称为划分。
对两个子序列分别重复上述过程，直至每个子序列内只有一个记录或空为止。
$a[s]..a[i-1]\ a[i] \ a[i+1] ..a[t]$
> f(a,s,t)=不做任何事情 当a[s...t]中长度小于2
>
> f(a,s,t)=i=Partition(a,s,t);其他情况
>
> f(a,s,i-1);f(a,i+1,t)
1. 分解：将原序列a[s...t]分解成两个子序列a[s...i-1]和a[i+1...t]，其中i为划分的基准位置
2. 求解子问题：若子序列的长度为0或为1，则它是有序的，直接返回，否则递归地求解各个子问题
3. 合并：由于整个序列放在数组a中，排序过程是就地进行的，合并过程不需要执行任何操作
```
int Partition(int a[],int s,int t)
{
int i=s,j=t;
int tmp=a[s];
while (i!=j)
{
while (j>i && a[j]>=tmp)
j--;
a[i]=a[j];
while(i>1,i=l,j=mid+1,cnt=0;
while(i<=mid && j<=r)
{if (a[i]<=a[j]) tmp[++cnt] =a[i++];
else tmp[++cnt]=a[j++];}
while(i<=mid ) tmp[++cnt] =a[i++];
while(j<=r) tmp[++cnt] =a[j++];
for (int i=l,j=1;i<=r &&j <=cnt;i++,j++)
a[i]=tmp[j];
}
```
设MergeSort(a,0,n-1 )算法执行时间为T(n)
Merge(a,0,n/2,n-1)的执行时间为O(n)
> T(n)=1 n=1
>
> T(n)=2T(n/2)+O(n)+(O(1)) ,n>1
$T(n)=O(nlog_2 n)$
算法的执行时间为T（n）
分解的算法为O(1)
合并的算法O（n）
给定一个有n(n≥1)个整数的序列，要求求出其中最大连续子序列的和
（-2，11，-4，13，-5，-2）最大子序列为20
规定一个序列最大连续子序列和至少是0
对于含有n个整数的序列a[0...n-1]若n=1，表示该序列仅含一个元素，如果该元素大于0，则返回该元素；反则返回0
n>1,取其中间位置$mid =\lfloor (n-1)/2 \rfloor$
该子序列之可能出现3个地方
1. 该子序列完全落在左半部即a[0...mid]中，采用递归求出最大连续子序列maxLeftSum
2. 该子序列完全落在右半部分a[mid+1m,,n-1]中，采用递归求出最大连续子序列maxRightSum
$$
\underset{\max RightSum}{\underbrace{a_{mid+1}a_{mid+2}...a_j...a_{n-1}}}
$$
3. 该子序列跨越序列a的中部而占据左右两部分
$$
\underset{\max LeftBorderSum}{\underbrace{a_ia_{i+1}...a_{mid}}}+\underset{\max RightBorderSum}{\underbrace{a_{mid+1...}a_j}}
$$
$max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)$
```
long maxSubSum(int a[],int left,int right)
{
int i,j;
long maxLeftSum,maxRightSum;
long maxLeftBorderSum,leftBorderSum;
long maxRightBorderSum,rightBorderSum;
if (left==right) //子序列只有一个元素
{
if (a[left]>0)
rerturn a[left];
else
return 0;
}
maxLeftBorderSum=0,leftBorderSum=0;
for (i=mid;i>=left;i--)//求出以左边加上a[mid]元素
{
leftBorderSum+=a[i];//构成序列的最大和
if (leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum=leftBorderSum;
}
maxRightBorderSum=0,rightBorderSum=0;
for (j=mid+1;jmaxRightBorderSum)
maxRightBorderSum=rightBorderSum;
}
return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
}
```
### 计算时间复杂度
#### 代换法
先猜测有某个界存在，然后利用数学归纳法。
#### 递归树法
分治法就是以2为底，就是$log_2 n=lgn$
将递归式转换为树形结构，树中的节点代表在不同递归层次付出的代价，
#### 主方法
主方法适用递归方程的形式$$T\left( n \right) =aT\left( n/b \right) +f\left( n \right) $$
a:子问题的个数
b:子问题的规模
\[
\left \{
\begin{array}{ll}
T(n)=\Theta(n^{log_b^a}), & n^{log_b^a}>f(n)\\
T(n)=\Theta(n^{log_b^a} log\ n)=\Theta{(f(n)log\ n)}, & n^{\log_b^a}=f(n)\\
T(n)=\Theta(f(n)) & n^{\log_b^a}