一、算法基础

1. 算法定义与特性

算法定义：算法是解决特定问题的步骤描述，是精确定义的计算过程。

程序 = 数据结构 + 算法

• 数据结构：如何把现实世界的问题信息化，将信息存进计算机
• 算法：如何处理这些信息，以解决实际问题

算法五大特性：

• 有穷性：算法必须在有限步骤内结束
• 确定性：相同输入必须得到相同输出
• 可行性：算法步骤必须可执行
• 输入：零个或多个输入
• 输出：一个或多个输出

好算法的特质：

• 正确性：能正确解决问题
• 可读性：易于理解和维护
• 健壮性：能处理非法输入
• 高效率与低存储量需求

2. 算法效率分析

时间复杂度

定义：算法执行时间与问题规模n的关系（T(n)）

大O表示法：描述算法执行时间随输入规模增长的趋势

常见时间复杂度（从小到大）：

• O(1)：常数时间复杂度（最佳）
• O(log n)：对数时间复杂度
• O(n)：线性时间复杂度
• O(n log n)：线性对数时间复杂度
• O(n²)：平方时间复杂度
• O(n³)：立方时间复杂度
• O(2ⁿ)：指数时间复杂度（较差）
• O(n!)：阶乘时间复杂度（最差）

分析技巧：

1. 顺序执行的代码只影响常数项，可忽略
2. 只需分析循环中的基本操作与n的关系
3. 多层嵌套循环只需关注最深层循环
4. 加法规则：多项相加保留最高阶项
5. 乘法规则：多项相乘全部保留

三种时间复杂度：

• 最坏时间复杂度：最坏情况下算法的执行时间
• 平均时间复杂度：所有输入等概率出现时的期望运行时间
• 最好时间复杂度：最好情况下算法的执行时间

空间复杂度

定义：算法占用的内存空间与问题规模n的关系（S(n)）

常见空间复杂度：

• O(1)：常数空间（原地工作算法）
• O(n)：线性空间
• O(n²)：平方空间

分析技巧：

1. 只需关注与问题规模相关的变量
2. 递归调用的空间复杂度 = 递归深度

二、基本算法思想

1. 贪心算法

核心思想：在每一步选择中都采取在当前状态下最好或最优的选择，希望通过局部最优解达到全局最优解。

适用条件：

• 最优子结构
• 贪心选择性质

常用场景：

• 活动选择问题（选择最多不重叠活动）
• 零钱找零问题（特定面额下找零最少硬币数）
• 哈夫曼编码（数据压缩）

局限性：不总是能得到全局最优解

2. 分治算法

核心思想：将问题分解为若干个规模较小的相同问题，递归求解这些子问题，然后合并子问题的解得到原问题的解。

三步过程：

1. 分解：将原问题分解为若干个规模较小的子问题
2. 解决：递归地求解各子问题
3. 合并：将子问题的解合并成原问题的解

经典应用：

• 归并排序
• 快速排序
• 大整数乘法

3. 动态规划

核心思想：将原问题分解为相互重叠的子问题，通过保存子问题的解避免重复计算，自底向上求解。

适用条件：

• 最优子结构
• 重叠子问题

实现方式：

• 自顶向下（记忆化搜索）
• 自底向上（表格法）

经典问题：

• 背包问题
• 最长公共子序列
• 最短编辑距离
• 切割钢条问题

4. 回溯算法

核心思想：系统地搜索问题的所有可能解，通过"试错"的方式，当发现当前选择不满足条件时，回退到上一步重新选择。

实现方式：

• 递归实现
• 使用剪枝优化

经典问题：

• 八皇后问题
• 图的着色问题
• 0-1背包问题
• 全排列问题

三、常用排序算法

1. 冒泡排序 (Bubble Sort)

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定
• 核心思想：重复遍历要排序的数列，一次比较两个元素，如果顺序错误就交换
• 适用场景：小规模数据排序

2. 选择排序 (Selection Sort)

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定
• 核心思想：每次从未排序部分找出最小（或最大）元素，放到已排序部分的末尾
• 适用场景：小规模数据排序，内存受限环境

3. 插入排序 (Insertion Sort)

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定
• 核心思想：将数组分为已排序和未排序两部分，每次将未排序部分的第一个元素插入到已排序部分的适当位置
• 适用场景：小规模或基本有序的数据排序

4. 快速排序 (Quick Sort)

• 时间复杂度：平均O(n log n)，最坏O(n²)
• 空间复杂度：O(log n)
• 稳定性：不稳定
• 核心思想：选择一个基准元素，将数组分为两部分（小于基准和大于基准），递归排序两部分
• 适用场景：大规模数据排序，实际应用中最常用的排序算法

5. 归并排序 (Merge Sort)

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定
• 核心思想：将数组分成两半，递归排序，然后合并两个有序数组
• 适用场景：大规模数据排序，外部排序，需要稳定排序的场景

四、常用搜索算法

1. 线性搜索 (Linear Search)

• 时间复杂度：O(n)
• 核心思想：从数组的第一个元素开始，逐个比较，直到找到目标元素或遍历完所有元素
• 适用场景：无序数组或小规模数据

2. 二分搜索 (Binary Search)

• 时间复杂度：O(log n)
• 前提条件：数组必须有序
• 核心思想：每次将搜索范围缩小一半，比较中间元素与目标值
• 适用场景：有序数组的查找，大规模数据

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

3. 深度优先搜索 (DFS)

• 实现方式：递归或栈
• 核心思想：沿着树的深度遍历节点，尽可能深地搜索树的分支
• 适用场景：路径问题、连通性问题、拓扑排序

4. 广度优先搜索 (BFS)

• 实现方式：队列
• 核心思想：从根节点开始，沿着树的宽度遍历节点，直到所有节点都被访问
• 适用场景：最短路径问题、连通性问题

五、常用字符串匹配算法

1. 暴力匹配算法 (Brute Force)

• 时间复杂度：O(mn)，m为模式串长度，n为主串长度
• 核心思想：逐个字符比较，不匹配时模式串后移一位
• 适用场景：小规模字符串匹配

2. KMP算法

• 时间复杂度：O(m+n)
• 核心思想：利用已匹配部分的信息，避免重复比较
• 关键：部分匹配表(PMT)或next数组
• 适用场景：大规模文本搜索，需要高效匹配的场景

六、实用技巧与建议

1. 算法选择指南

• 小规模数据：插入排序、冒泡排序
• 大规模通用排序：快速排序
• 需要稳定排序：归并排序
• 有序数组查找：二分搜索
• 字符串匹配：KMP算法

2. 常见时间复杂度对比

算法	时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n²)	O(1)	是	小规模数据
选择排序	O(n²)	O(1)	否	小规模数据
插入排序	O(n²)	O(1)	是	小规模/基本有序数据
快速排序	O(n log n)	O(log n)	否	大规模通用排序
归并排序	O(n log n)	O(n)	是	大规模稳定排序
二分搜索	O(log n)	O(1)	-	有序数组查找
KMP	O(m+n)	O(m)	-	字符串匹配

3. 算法学习建议

1. 理解算法思想比记忆代码更重要
2. 动手实现核心算法，加深理解
3. 通过LeetCode等平台练习常见题型
4. 学会分析算法的时间/空间复杂度
5. 针对不同问题选择合适的算法

提示：掌握以上内容足以应对80%的算法应用场景。不必记忆所有算法细节，重要的是理解算法思想，学会分析问题并选择合适的解决方案。在实际工作中，可以随时查阅资料，但对基础算法的理解和应用能力是核心竞争力。