991 字
5 分钟
算法
算法入门指南
算法是一种被定义好的计算机可执行其指示的有限步骤或秩序，常用于计算、数据处理和自动推理。
说白话一点：算法就是人们用来解决问题的工具，提高效率的法子。
欧几里德算法的由来
人们常说欧几里德算法是史上的第一个算法。它由古希腊数学家欧几里德在《几何原本》里提出，用来计算两个正整数的最大公因数（GCD）。如今它不仅用于数学，还广泛应用于密码学、计算机科学和图形处理等领域。
算法的核心性质（高德纳归纳）
美国计算机科学家唐纳德·E. 高德纳在《计算机程序设计艺术》（The Art of Computer Programming）中，对算法的本质特征进行了经典归纳：
| 性质 | 含义 | 关键点 |
|---|---|---|
| 输入 | 一个算法必须有零个或以上输入量 | 至少要有一个入口 |
| 输出 | 算法应有一个或以上输出量，输出量是算法计算的结果 | 必须有明确的结果 |
| 明确性 | 算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际执行结果是确定的 | 不能含糊其辞 |
| 有限性 | 依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算。图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务 | 必须能在有限时间内终止 |
| 有效性 | 又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现 | 必须是真实可行的 |
基本算法分类
算法可以按不同维度分类，这里是常见的几大类：
1. 基础搜索与枚举
- 枚举法（Brute-force / Exhaustive Search）
- 深度优先搜索（DFS）
- 广度优先搜索（BFS）
- 启发式搜索
2. 进化类算法
- 遗传算法（Genetic Algorithm）
3. 数据结构算法
- 树的遍历（树的前序、中序、后序遍历）
- 图论相关
- 哈夫曼编码
- 最短路径算法
- 最小生成树算法
- 网络流算法
- 匹配算法
- 分团问题（Clique Problem）
4. 优化算法
- 贪心算法（专栏重点）
- 核心思想：从当前状态开始，总是选择当时看起来最好的局部解。
- 优点：速度快、实现简单。
- 缺点：不一定能找到全局最优解（可能陷入局部最优）。
- 经典应用：最小生成树（Kruskal、Prim、Sollin算法）、霍夫曼树编码。
5. 其他高级算法
- 动态规划（Dynamic Programming）
- 数值分析
- 加密算法
- 排序算法
- 检索算法
- 随机化算法
（并行算法建议单独查阅《并行计算》相关文献）
贪心算法专讲
贪心算法是算法世界里最优雅、最实用的优化工具之一。
工作原理
- 检查“子结构”或“最优子结构”。
- 从当前已知解（可能已构造好）开始，通过小的修改不断改进。
- 每次只做最“贪心”的选择（看局部最优）。
关键特点
- 最常用用途：寻找最小生成树（可以找到全局最优解）。
- 其他经典应用：霍夫曼树编码、克鲁斯卡尔、普里姆算法、Sollin算法。
- 部分问题能求出最优解，部分问题只能停留在局部最优（无法继续改进，但不是全局最优）。
经典比喻：
贪心算法就像一个人去超市买东西，总是买最便宜的单件商品（局部最优），最后可能比先买一整包更划算，但有时候也可能吃亏。