---
tags: [算法分析与设计]
abstract: 算法学习背景、问题建模与算法设计路线
finished: false
下一篇: [[计算机系/算法分析与设计/01 算法入门与正确性证明|下一篇]]
返回目录: [[计算机系/算法分析与设计/算法分析|算法分析与设计学习指南]]
---
# 算法学习导论

## 前言

AI:训练成本、推理能力、架构能力、算法的优化

我们在AI时代需要什么：独立思考的能力、分析用户的需求

> 程序=数据结构+算法
>
> 算法->智能

脚本语言vs系统语言

> **脚本语言**：Python、JavaScript、PHP、Ruby
>
> **特点**：开发快、动态、适合胶水代码、自动化任务
>
> **系统语言**：C/C++、Java、Go
>
> **特点**：性能强、类型安全、适合大型系统



**软件架构**

软件开发生命周期：可行性研究——需求分析——概要设计——详细设计——实现测试——使用维护

软件结构——Web Service

```mermaid
graph LR
	subgraph A_group 
        A["服务代理"]
        D["UDDI注册中心（统一描述、发现与集成）"]
    end
    B["服务提供者"] -->|发布/UDDI（统一描述、发现与集成）/WSDL（Web服务描述语言）| A
    C["服务请求者"] -->|查找/UDDI（统一描述、发现与集成）/WSDL（Web服务描述语言）| A
    C -->|绑定/调用| B

    E["客户端应用"] --> |SOAP（简单对象访问协议）| F["Web服务"]
```

```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.时间效率
4.空间效率
5.效率评估方法主要分为两种：实际测试、理论估算
迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。
递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。

以求和函数为例，设问题 $f(n)=\sum^{n}_{i=1}i$
 

迭代：在循环中模拟求和过程，从 1遍历到 n，每轮执行求和操作，即可求 f(n)。
递归：将问题分解为子问题 f(n)=n+f(n-1)，不断（递归地）分解下去，直至基本情况 f(1)=1时终止。

递归（ recursion）是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段。

递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。
而从实现的角度看，递归代码主要包含三个要素。

终止条件：用于决定什么时候由“递”转“归”。
递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
返回结果：对应“归”，将当前递归层级的结果返回至上一层。

 

分析算法

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分支<br>（成本估计函数剪枝）]
    
    %% 可分解分支
    A -- "是" --> G{子问题是否重叠？}
    
    %% 无重叠 -> 分治
    G -- "否（子问题独立）" --> H[分治法]
    
    %% 有重叠 -> 进一步判断
    G -- "是" --> I{是否有最优子结构？}
    
    I -- "是" --> J[动态规划<br>（结果复用）]
    I -- "否（但局部最优即全局最优）" --> K[贪心算法<br>（每一步选当前最优）]
    
    %% 特殊情况
    A -.-> L[特殊情况]
    L --> M[概率算法<br>拉斯维加斯、蒙特卡洛等]
    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、减小搜索空间——回溯法+剪枝

- **核心思想**：在解空间树中搜索，遇到不可能的分支就提前返回
- **剪枝策略**：
  - 可行性剪枝
  - 最优性剪枝（上界/下界估计）
  - 对称性剪枝
- **理解**：回溯法本质是暴力搜索 + 智能剪枝

 **近似算法**