【算法】算法大纲

这篇文章介绍计算机算法的各个思维模式。

包括 计数原理、数组、树型结构、链表递归栈、查找排序、管窥算法、图论、贪心法和动态规划、以及概率论：概率分治和机器学习。没有办法逐个说明，算法本身错综复杂，不同的算法对应着不同的实用场景，也需要根据具体情况设计与调整。介绍仅仅提供了一个整体知识结构树，有利于在后期系统性的思维框架。

参考书目：

1. 算法设计与分析（第3版）（美）Anany Levitin 著 潘彦 译 清华大学出版社
2. [数据结构(C语言版)].严蔚敏_吴伟民. 著
3. 数据结构与算法分析——C语言描述（第2版）（美）Mark Allen Weiss 著. 冯舜玺 译
4. 数据结构与算法图解 (杰伊•温格罗, 袁志鹏译) (Z-Library 上可免费获取)
5. 算法设计与分析 Dexter C · Kozen.康奈尔大学 版权由SpringerSperlag公司提供

---

我将算法主要分为三大部分：

• 算法基础：包含算法的基本概念、复杂度分析和数学基础。
• 算法设计策略：常用的算法设计方法，如管窥、分治、贪心、动态规划、线性规划等。
• 高级算法：包括图论、概率论、NP完全性、近似算法、分布式算法、加密算法和机器学习等等。

算法基础

参考文章：【算法】算法初步 中的内容。
除此之外，还包括算法的历史背景和重要性；算法在计算机科学中的作用。

• 介绍了算法的五大特性：输入、输出、确定性、有穷性、有效性。
• 算法的一些应用领域：排序、搜索、图算法、优化问题、数据分析、数据处理、机器视觉、运动控制等。

算法的基础分析

• 主要内容：
  • 时间复杂度和空间复杂度的基本概念；算法效率的衡量标准；最坏情况、最优情况和平均情况分析。
  • 渐进符号：O（大O）、Ω（大欧米伽）、Θ（大Theta）。
  • 常见复杂度函数（如常数、对数、线性、多项式、指数等）的增长趋势。

数学基础

• 主要内容：
  • 计数原理：排列、组合。
  • 数学归纳法。
  • 递归方程及其求解方法。递归关系的求解（迭代法、主定理、递归树）。
  • 模运算和数论基础；模运算在算法设计中的应用。

算法设计策略

分治策略

分治思想：分治策略是一种将大问题划分为规模较小的子问题，递归解决子问题，最后合并子问题解以获得原问题解的方法。

经典算法：

1. 二分搜索。
2. 合并排序（Merge Sort）。
3. 快速排序（Quick Sort）。
4. 最近点对问题。

重点包括分治法的递归结构；主定理在分治策略中的应用；归并排序和快速排序的时间复杂度分析等等。

管窥算法

管窥算法是一种通过局部观察和处理问题的局部特征来逐步求解整体问题的方法。

实现方式：
管窥算法用于解决需要动态调整范围或局部处理问题的场景：

1. 连续子数组问题（如最大子数组和、最小窗口子串）。
2. 字符串匹配&#x