算法入门 ​

什么是算法？ ​

算法是解决特定问题的一系列明确步骤。它就像烹饪食谱：输入食材，通过一系列操作，输出美味菜肴。算法的核心在于将复杂问题分解为可重复的简单动作。例如，计算两个数的最大公约数，可以使用欧几里得算法：反复用较小数除较大数，直到余数为零。

特点：

• 输入：算法接受零个或多个输入。
• 输出：产生至少一个输出。
• 明确性：每个步骤无歧义，如“如果 a 大于 b，则交换 a 和 b”。
• 有限性：在有限步骤后终止。
• 有效性：每个步骤可行，能在实际中执行。

示意图：

输入数据 --> [算法处理] --> 输出结果

例如，排序算法输入未排序数组，输出有序数组。

算法特点详解 ​

算法设计注重效率，主要通过时间复杂度和空间复杂度衡量。时间复杂度描述运行时间随输入规模的增长趋势，空间复杂度描述内存使用情况。常见复杂度有 O(1)、O(log n)、O(n)、O(n²) 等，其中 O(1) 表示常数时间，O(n²) 表示时间随输入平方增长。

特点：

• 确定性：相同输入总是产生相同输出。
• 通用性：适用于一类问题，而非单个实例。
• 最优性：某些算法可证明为最优解，如二分搜索在有序数组中的搜索。

示意图 (时间复杂度比较)：

O(1): 恒定如平地
O(log n): 缓坡上升
O(n): 直线上升
O(n²): 陡峭曲线上升

用文本高度表示增长：O(1) 为“—”，O(log n) 为“/”，O(n) 为“|”，O(n²) 为“/\”。

常见算法类型 ​

算法可分为多种类别，包括排序、搜索、图算法、动态规划等。排序算法重排数据顺序，搜索算法查找特定元素，图算法处理网络结构问题。入门阶段，排序和搜索是基础。

特点：

• 排序算法：注重稳定性和原地操作，稳定性指相等元素顺序不变，原地操作指无需额外内存。
• 搜索算法：强调预处理和查询效率，如二分搜索要求数据有序。
• 分治算法：将问题分解为子问题解决，再合并结果，如快速排序。

示意图 (算法分类树)：

算法
├── 排序（如冒泡排序、快速排序）
├── 搜索（如线性搜索、二分搜索）
├── 图算法（如Dijkstra最短路径）
└── 动态规划（如斐波那契数列优化）

排序算法 ​

排序算法将数据按特定顺序排列，如升序或降序。常见算法包括冒泡排序、快速排序等，各有特点。

冒泡排序 ​

冒泡排序通过反复交换相邻元素，将最大元素“冒泡”到数组末端。它简单易懂，但效率较低。

特点：

• 时间复杂度：平均和最坏情况 O(n²)，最好情况 O(n)(当数组已排序)。
• 空间复杂度：O(1)，原地排序。
• 稳定性：稳定，相等元素不交换。

示意图 (数组 [5，3，8，4，2] 的排序过程)：

初始: [5, 3, 8, 4, 2]
第一遍: 比较5和3 → 交换 → [3, 5, 8, 4, 2]
       比较5和8 → 不交换 → [3, 5, 8, 4, 2]
       比较8和4 → 交换 → [3, 5, 4, 8, 2]
       比较8和2 → 交换 → [3, 5, 4, 2, 8]
第二遍: 重复过程，最大元素已到位，继续...
最终: [2, 3, 4, 5, 8]

每一遍减少一个比较元素，直到全排序。

快速排序 ​

快速排序使用分治策略：选择一个基准元素，将数组分为小于和大于基准的两部分，递归排序子数组。它高效且广泛应用。

特点：

• 时间复杂度：平均 O(n log n)，最坏 O(n²)(当基准选择不佳)。
• 空间复杂度：O(log n)，由于递归栈。
• 稳定性：不稳定，可能改变相等元素顺序。

示意图 (数组 [5，3，8，4，2] 的快速排序，以第一个元素为基准)：

初始: [5, 3, 8, 4, 2]
选择基准5: 分区 → 小于5: [3, 4, 2], 大于5: [8]
递归排序左部[3,4,2]: 基准3 → 分区: [2] 和 [4] → 排序后[2,3,4]
递归排序右部[8]: 已排序
合并: [2,3,4,5,8]

分区过程通过交换实现，例如将元素与基准比较并移动。

搜索算法 ​

搜索算法在数据集中查找目标元素，常见有线性搜索和二分搜索。

线性搜索 ​

线性搜索从头到尾遍历每个元素，直到找到目标或遍历完。它适用于未排序数据。

特点：

• 时间复杂度：O(n)，最坏情况需检查所有元素。
• 空间复杂度：O(1)，无需额外内存。
• 通用性：适用于任何列表。

示意图 (在数组 [3，5，2，8，4] 中搜索 8)：

索引0: 3 ≠ 8 → 继续
索引1: 5 ≠ 8 → 继续
索引2: 2 ≠ 8 → 继续
索引3: 8 = 8 → 找到，返回索引3

用箭头表示遍历：3 -> 5 -> 2 -> 8 (命中)。

二分搜索 ​

二分搜索要求数据有序，通过反复将搜索区间减半来快速定位目标。它高效但依赖排序。

特点：

• 时间复杂度：O(log n)，每次比较减少一半数据。
• 空间复杂度：O(1)(迭代版本) 或 O(log n)(递归版本)。
• 预处理需求：必须先排序数据。

示意图 (在有序数组 [2，3，4，5，8] 中搜索 4)：

初始区间: 左=0, 右=4
中间索引=(0+4)/2=2, 值=4 → 匹配，返回索引2

如果搜索 5：

中间索引=2, 值=4 < 5 → 调整左=3
新区间: 左=3, 右=4
中间索引=(3+4)/2=3, 值=5 → 匹配

用区间缩小表示：[0-4] -> [3-4] -> 找到。

算法设计技巧 ​

入门算法常使用基本技巧，如贪心算法、分治和动态规划。贪心算法每步选择局部最优，希望达到全局最优；分治将问题分解；动态规划存储子问题解避免重复计算。

特点：

• 贪心算法：简单高效，但不总是最优，如背包问题。
• 分治：适合并行处理，但递归可能增加开销。
• 动态规划：通过表格存储解，提高效率，如计算斐波那契数。

示意图 (动态规划斐波那契计算，避免重复)：

F(0)=0, F(1)=1
F(2)=F(1)+F(0)=1
F(3)=F(2)+F(1)=2
...
用数组存储: [0,1,1,2,...] 而非递归树

对比递归树 (大量重复) 与动态规划表 (线性计算)。