算法是程序员的必修课，它帮助我们编写高效的代码并解决复杂的问题。然而，对于初学者，算法看似高深，实际却可以从基础入手逐步掌握。本专栏旨在为零基础程序员提供一个系统、简单、易懂的算法入门指导。
目录
目录
1. 什么是算法？
算法是一组有序的指令，用于解决特定问题。可以把它想象成解决问题的“步骤清单”。例如，我们生活中经常使用的“做饭”就是一个算法：备料、加热、调味、出锅，这些步骤是按照一定顺序完成的。
特性
- 输入和输出：算法需要明确的输入和输出。
- 有限性：算法必须在有限步内结束。
- 明确性：每一步都清晰可执行。
- 高效性：好的算法在解决问题时速度快，占用资源少。
2. 算法与复杂度：从效率谈起
一个算法的效率通常通过 时间复杂度 和 空间复杂度 来评估。
时间复杂度
时间复杂度描述了算法运行时间与输入规模的关系。常见的时间复杂度有：
- O(1)：常数时间，例如数组访问。
- O(n)：线性时间，例如遍历列表。
- O(n²)：平方时间，例如嵌套循环。
举例：比较数组中的最大值
python
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
- 复杂度：O(n)，因为需要遍历整个数组。
时间复杂度的图解
以下图显示了不同时间复杂度的增长趋势：
时间 |
|
| O(n²)
| /
| /
| O(n)
| /
| /
| O(1)
------------------
输入规模
空间复杂度
描述算法占用的内存。比如，递归算法可能会占用较多内存，因为它需要保存每次递归调用的状态。
3. 排序算法详解与可视化
排序是程序员学习算法的必经之路。我们通过排序算法来学习基本的算法设计思路。
3.1 冒泡排序
原理：两两比较相邻元素，将较大的元素“冒泡”到最后。
代码实现：
python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
图解： 假设我们对数组 [5, 3, 8, 6] 进行冒泡排序：
第一轮：
[5, 3, 8, 6] -> [3, 5, 8, 6] -> [3, 5, 6, 8]
第二轮：
[3, 5, 6, 8] -> 无需交换
最终结果：
[3, 5, 6, 8]
时间复杂度：O(n²)，适合小规模数据。
3.2 插入排序
原理：将元素插入到已经排好序的子序列中。
代码实现：
python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
图解： 对 [5, 3, 8, 6] 使用插入排序：
- 初始：[5 | 3, 8, 6]
- 插入3：[3, 5 | 8, 6]
- 插入8：[3, 5, 8 | 6]
- 插入6：[3, 5, 6, 8]
3.3 快速排序
原理：选择一个“基准”元素，将小于基准的放左边，大于基准的放右边，递归处理子序列。
代码实现：
python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
图解： 对 [5, 3, 8, 6] 使用快速排序：
- 选基准5，分割为
[3]和[8, 6]。 - 递归排序：
[3]不变。[8, 6]基准为8，分割为[6]和[]。
- 合并结果：[3, 5, 6, 8]
4. 搜索算法：如何快速找到答案？
搜索算法用于从数据集中查找目标元素。
4.1 线性搜索
原理：逐一检查每个元素，直到找到目标。
代码实现：
python
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
时间复杂度：O(n)
4.2 二分搜索
原理：数据必须是有序的，每次将搜索范围缩小一半。
代码实现：
python
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
图解： 假设数组为 [1, 3, 5, 7, 9]，目标是 7：
- 初始范围：[1, 3, 5, 7, 9]，中间值为
5。 - 缩小范围：[7, 9]，中间值为
7。 - 找到目标。
时间复杂度：O(log n)
5. 递归与分治思想
递归是一种解决问题的方法，核心思想是将问题拆解为更小的子问题，并利用相同的方法来解决这些子问题，直到问题足够小以至于可以直接解决。
递归和分治常常结合使用。分治（Divide and Conquer）是一种将问题分成若干子问题，分别解决后再合并结果的算法设计策略。
5.1 什么是递归？
递归的定义：一个函数直接或间接地调用自身。
递归的三个要素：
- 递归终止条件：必须要有一个明确的终止条件，避免无限递归。
- 递归的逻辑：在每一次递归中，解决一个更小的子问题。
- 递归调用自身：通过改变输入参数使问题规模逐渐缩小。
5.2 递归代码示例：阶乘
计算一个数的阶乘 n!n!，公式为：
n!=n×(n−1)!n!=n×(n−1)! 0!=10!=1
递归实现：
python
def factorial(n):
if n == 0: # 递归终止条件
return 1
return n * factorial(n - 1) # 递归调用
调用过程：
当计算 factorial(4) 时，发生以下递归调用：
factorial(4)调用4 * factorial(3)factorial(3)调用3 * factorial(2)factorial(2)调用2 * factorial(1)factorial(1)调用1 * factorial(0)factorial(0)返回 1，递归停止。
最终结果为：
4×3×2×1=244×3×2×1=24
5.3 分治思想
分治算法的核心思想是将一个大问题分成若干小问题，每个子问题独立解决，最后将结果合并。
分治的步骤：
- 分解：将问题分成若干子问题。
- 解决：递归地解决这些子问题。
- 合并：将子问题的解合并成原问题的解。
5.4 快速排序：分治的典型应用
快速排序是分治思想的经典例子。算法核心是选择一个“基准值”，将数组划分为小于基准值的部分和大于基准值的部分，然后递归地对两部分排序。
快速排序代码：
python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
过程可视化： 对数组 [5, 3, 8, 6, 2] 执行快速排序：
- 选基准值
5，划分为[3, 2]和[8, 6]。 - 对
[3, 2]：- 选基准值
3，划分为[2]和[]。
- 选基准值
- 对
[8, 6]：- 选基准值
8，划分为[6]和[]。
- 选基准值
- 合并结果：
[2, 3, 5, 6, 8]
6. 动态规划的基础理解
动态规划（Dynamic Programming, DP）是一种将复杂问题分解为多个子问题，并利用子问题的解构建原问题解的算法思想。它常用于优化具有重叠子问题的问题。
6.1 动态规划的特点
- 最优子结构：问题的最优解可以由子问题的最优解构造。
- 重叠子问题：问题的不同部分会重复计算同一子问题。
- 状态转移方程：描述如何从子问题的解推导原问题的解。
6.2 动态规划的经典问题：斐波那契数列
斐波那契数列定义为： F(n)=F(n−1)+F(n−2)F(n)=F(n−1)+F(n−2) 其中 F(0)=0,F(1)=1F(0)=0,F(1)=1。
递归实现：
python
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
然而，这种递归效率低下，因为它重复计算了大量子问题。
优化：动态规划实现
通过记忆化存储已解决的子问题，避免重复计算。
python
def fibonacci_dp(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
对比：
- 递归时间复杂度：O(2ⁿ)
- 动态规划时间复杂度：O(n)
6.3 动态规划案例：背包问题
问题描述： 给定一个固定容量的背包和若干物品，每件物品有重量和价值，求在不超过背包容量的情况下，如何选择物品使总价值最大。
动态规划解法：
定义 dp[i][w] 为前 i 个物品在容量为 w 的背包中可获得的最大价值。
状态转移方程： dp[i][w]=max(dp[i−1][w],dp[i−1][w−wt[i]]+val[i])dp[i][w]=max(dp[i−1][w],dp[i−1][w−wt[i]]+val[i])
- 如果不选第
i个物品：价值为dp[i-1][w]。 - 如果选第
i个物品：价值为dp[i-1][w-wt[i]] + val[i]。
代码实现：
python
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
7. 图论算法的简单应用
图论是算法学习的重要组成部分，用于解决节点和边的关系问题。常见的图算法包括最短路径、最小生成树等。
7.1 深度优先搜索（DFS）
原理：从一个节点开始，沿着一条路径探索到尽头，再回溯继续探索其他路径。
代码实现：
python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
7.2 广度优先搜索（BFS）
原理：从一个节点开始，按层次依次遍历邻居。
代码实现：
python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
8. 总结与进阶学习建议
- 学习顺序：从基础排序和搜索开始，逐步深入动态规划和图论算法。
- 练习平台：尝试在 LeetCode、Codeforces、牛客网 上刷题。
- 进阶方向：研究高级算法如最短路径（Dijkstra）、最大流问题（Ford-Fulkerson）等。
通过本文的系统学习，你已经踏入算法的大门，接下来的关键是持续练习和思考！
标签：arr,入门,递归,复杂度,问题,程序员,算法,dp From： https://blog.csdn.net/hxyh888/article/details/144051812