算法
Algorithm 算法
为解决某一类特定问题而设计的、在有限步骤内可执行的、精确的指令序列 。
它规定了解题的输入、输出、操作步骤和逻辑流程，是计算机科学的核心概念之一。
一、算法的基本特性
算法研究的根本是各种现实问题的求解，将问题抽象为数学模型后。很多现实的问题的求解就可以归结为同一问题的求解。
- 有穷性 (Finiteness)：算法必须在有限的步骤内完成，不能无限循环。
- 确定性 (Definiteness)：算法的每一步都必须有确切的定义，没有歧义。
- 可行性 (Effectiveness)：算法的每一步都必须是可执行的，能够在有限时间内完成。
- 输入 (Input)：算法可以有零个或多个输入，这些输入是算法执行所需的数据。
- 输出 (Output)：算法必须有一个或多个输出，这些输出是算法执行的结果。
快速了解新的算法
-
明确算法定位与解决的问题：
- 这类算法是解决什么类型的问题？（排序？搜索？图论？优化？机器学习？）
- 输入是什么？输出是什么？
- 与哪些问题场景最相关？
-
把握算法的核心思想：理解算法背后的基本思想和策略。
-
从伪代码或流程图入手，画图模拟：通过具体例子手动模拟算法的执行过程，加深理解。
-
亲自实现 + debug + trace：通过编程实现算法，并进行调试和跟踪，发现并解决问题。
-
掌握复杂度、边界与变体：
- 时间/空间复杂度分析：评估算法的效率和资源消耗。
- 极端输入下表现：考虑算法在特殊情况下的行为。
- 该算法是否有改进版、并行版、近似版？：了解算法的演进和变种。
二、常用算法思想与类型
- 枚举：直接列举出所有可能情况并逐一验证。
- 搜索：从数据中寻找满足条件的目标（如深度优先搜索、广度优先搜索）。
- 排序：对数据按照某种规则进行有序排列（如冒泡排序、快速排序、归并排序）。
- 分治：将问题分解成规模更小的子问题递归求解，最后合并子问题的解得到原问题的解。
- 回溯：尝试探索所有可能解，通过“撤回上一步”回到分支点继续尝试，常用于解决组合优化问题。
- 动态规划：通过将问题分解为重叠的子问题，并保存子问题的解，避免重复计算，从而利用子问题最优解构建大问题最优解。
- 贪心算法：在每一步选择局部最优解，期望通过局部最优得到整体最优解。
- 差分与前缀和：处理区间更新与查询问题的高效技巧。
- 最短路径算法：寻找图中两点之间的最短路径（如Dijkstra算法、Floyd算法）。
- 启发式优化算法：通过概率或启发信息寻找近似解，常用于解决NP-hard问题（如遗传算法、模拟退火算法）。
三、参考资料
计算机科学
子问题分解
递归
复杂度分析
枚举
搜索
排序
分治
回溯
动态规划
贪心算法
差分与前缀和
最短路径算法
启发式优化算法