第1章：引言
1.1 算法与问题的定义
算法的定义：
- 算法是解决问题的一组明确的指令或步骤，用于将输入转换为输出。
- 一个好的算法应该具备清晰的正确性、效率和可理解性。
算法的三个主要方面：
- 输入：算法接受的初始数据。
- 输出：算法计算后的结果。
- 过程：算法执行的步骤。
1.2 算法的特性
正确性：
- 一个算法必须在所有输入情况下产生正确的输出。
效率：
- 主要指算法的时间复杂度和空间复杂度。
- 时间复杂度：执行步骤的数量。
- 空间复杂度：算法需要的额外内存。
可理解性：
- 算法应该易于理解和实现。
1.3 算法分析的基本方法
时间复杂度分析：
- 时间复杂度用来衡量算法执行所需的时间量，通常用大O符号表示，如O(n)、O(log n)、O(n²)等。
- 通过分析基本操作的执行次数来估计时间复杂度。 大O符号（Big O）：表示算法在最坏情况下的时间增长率。
空间复杂度分析：
- 空间复杂度衡量的是算法在执行过程中所占用的内存。
- 类似于时间复杂度，也使用大O符号来表示。
1.4 常见算法的分析实例
顺序查找：
- 给定一个线性列表，寻找一个特定的元素。
- 时间复杂度是O(n)，因为需要检查每个元素。
二分查找：
- 在已排序的数组中查找元素，通过每次将搜索区间折半来优化搜索。
- 时间复杂度是O(log n)。
1.5 数学基础
常见数学概念：
对数函数：logarithms，主要用来表示算法的对数时间复杂度。
指数函数：exponential functions，常见于某些暴力搜索算法的分析中。
数学技巧：
求和公式：掌握一些常见的求和公式，比如算术级数和几何级数的求和。
不等式：常用的数学不等式，如Cauchy-Schwarz不等式，帮助分析复杂度。
1.6 算法设计策略
分治法：
- 将一个大问题分解成若干小问题，递归求解后再合并结果。
-
示例：归并排序、快速排序。 动态规划：
-
将复杂问题分解为子问题，并通过保存子问题的解来避免重复计算。
-
示例：背包问题、最短路径问题。 贪心算法：
-
每次选择当前看似最优的解，尽量优化局部结果，逐步逼近全局最优。
- 示例：最小生成树（Kruskal、Prim算法）。
1.7 算法的伪代码与实现
伪代码：
- 伪代码是一种简化的程序语言，用来描述算法的步骤，避免与具体编程语言的细节相关联。
-
目的是帮助理解算法的核心思想。 代码实现：
-
学习如何将伪代码转化为实际的编程代码（如Python、C++等）。