Python 基础算法介绍

---

目录

1. 算法与复杂度分析
   1.1 什么是算法
   1.2 时间复杂度
   1.3 空间复杂度
2. 排序算法
   2.1 冒泡排序
   2.2 选择排序
   2.3 插入排序
   2.4 归并排序
   2.5 快速排序
3. 搜索算法
   3.1 线性搜索
   3.2 二分搜索
4. 递归与分治
   4.1 递归的基本思想
   4.2 分治法的步骤与实例
5. 动态规划
   5.1 动态规划的核心概念
   5.2 经典问题：斐波那契数列
   5.3 经典问题：0/1 背包问题
6. 贪心算法
   6.1 贪心策略
   6.2 经典问题：找零钱
   6.3 经典问题：活动选择
7. 图算法基础
   7.1 图的表示
   7.2 广度优先搜索（BFS）
   7.3 深度优先搜索（DFS）
8. 常用技巧与总结

---

1. 算法与复杂度分析

1.1 什么是算法

算法（Algorithm）是解决特定问题的一系列明确、有限的步骤。对相同输入，算法会给出相同输出，并能在有限时间内完成。

1.2 时间复杂度

时间复杂度描述算法的执行时间随输入规模增长的变化趋势，常用大O符号表示，如：

• O(1)：常数时间
• O(log n)：对数时间
• O(n)：线性时间
• O(n²)：平方时间
• O(2^n)：指数时间

1.3 空间复杂度

空间复杂度衡量算法运行过程中临时占用的存储空间大小，同样使用大O表示法。

---

2. 排序算法

2.1 冒泡排序（Bubble Sort）

反复遍历列表，比较相邻元素并交换顺序错误者，每一轮将最大（或最小）元素“浮”到顶端。
时间复杂度：O(n²)，空间复杂度：O(1)。

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

2.2 选择排序（Selection Sort）

每次从未排序部分找出最小元素，放到已排序部分的末尾。
时间复杂度：O(n²)，空间复杂度：O(1)。

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

2.3 插入排序（Insertion Sort）

将数组分为已排序和未排序两部分，每次取未排序部分第一个元素，插入到已排序部分的正确位置。
时间复杂度：O(n²)，空间复杂度：O(1)，对近乎有序的数据效率高。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

2.4 归并排序（Merge Sort）

采用分治策略，将数组递归分成两半，分别排序后再合并。
时间复杂度：O(n log n)，空间复杂度：O(n)。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

2.5 快速排序（Quick Sort）

选择一个基准元素，将数组划分为小于和大于基准的两部分，然后递归排序。
平均时间复杂度：O(n log n)，最坏 O(n²)；空间复杂度：O(log n)（递归栈）。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

---

3. 搜索算法

3.1 线性搜索（Linear Search）

依次检查每个元素，找到目标则返回索引。
时间复杂度：O(n)，空间复杂度：O(1)。

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

3.2 二分搜索（Binary Search）

要求数组有序。每次将搜索范围缩小一半，通过比较中间元素与目标值决定继续向左或向右搜索。
时间复杂度：O(log n)，空间复杂度：O(1)（迭代版）或 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

---

4. 递归与分治

4.1 递归的基本思想

递归是函数直接或间接调用自身。关键要素：

• 基线条件（停止递归）
• 递归条件（将问题分解为更小的子问题）

4.2 分治法的步骤与实例

分治法将问题分成若干子问题，分别求解，最后合并结果。归并排序和快速排序都是典型代表。示例：计算数组元素之和。

def sum_recursive(arr):
    if not arr:
        return 0
    return arr[0] + sum_recursive(arr[1:])

---

5. 动态规划

5.1 动态规划的核心概念

动态规划（DP）通过存储子问题的解避免重复计算，适用于具有重叠子问题和最优子结构性质的问题。常用方法：

• 自顶向下（记忆化递归）
• 自底向上（迭代填表）

5.2 经典问题：斐波那契数列

Fibonacci 数列：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。
用 DP 优化：

def fib_dp(n):
    if n <= 1:
        return 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(n)，空间复杂度 O(n)（可优化为 O(1)）。

5.3 经典问题：0/1 背包问题

给定物品重量和价值，在背包容量限制下最大化总价值。
状态定义：dp[i][w] 表示前 i 件物品在容量 w 下的最大价值。
转移方程：dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])。

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] = dp[i - 1][w]
            else:
                dp[i][w] = max(dp[i - 1][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

---

6. 贪心算法

6.1 贪心策略

贪心算法每步选择当前最优解，希望最终得到全局最优。它不总是有效，但在一些问题（如最小生成树、最短路径）中可以得到最优解。

6.2 经典问题：找零钱

假设硬币面额满足贪心性质（如人民币），用最少硬币找零：

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        if amount >= coin:
            num = amount // coin
            count += num
            amount -= num * coin
    return count if amount == 0 else -1

6.3 经典问题：活动选择

给定一系列活动的开始和结束时间，选出最多不冲突的活动。贪心策略：每次选结束时间最早且不与已选活动冲突的活动。

def activity_selection(activities):
    # activities 为 (start, end) 列表
    activities.sort(key=lambda x: x[1])
    selected = []
    last_end = 0
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

---

7. 图算法基础

7.1 图的表示

• 邻接矩阵：graph[i][j] 表示边的权重
• 邻接表：字典或列表，graph[node] 存储邻居节点

7.2 广度优先搜索（BFS）

使用队列，逐层遍历，常用于求最短路径（无权图）。

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

7.3 深度优先搜索（DFS）

尽可能深地访问节点，使用递归或栈实现。

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

---

8. 常用技巧与总结

• 双指针：在有序数组中寻找两数之和等场景应用广泛。
• 滑动窗口：用于求满足条件的连续子数组（串）。
• 前缀和：快速计算区间和，常用于数组问题。
• 位运算：提高效率，处理子集、状态压缩等问题。