算法ALGO

7 minute read

算法系统学习大纲（以python示例）

葵花宝典：hello算法
力扣刷题：力扣LeetCode

一、算法基础

1.1 算法定义与特性
- 什么是算法
- 算法的五个特性：有穷性、确定性、可行性、输入、输出
- 算法与程序的区别
1.2 算法复杂度分析
- 时间复杂度
- 空间复杂度
- 大O表示法
- 最好、最坏、平均情况复杂度
- 时间复杂度比较
1.3 算法效率评估方法
- 理论分析
- 实验测量
- 渐近分析
1.4 算法描述方法
- 自然语言
- 流程图
- 伪代码
- 编程语言实现

二、基础数据结构

2.1 数组

数组基本操作
多维数组
动态数组

# 数组基本操作
arr = [1, 2, 3, 4, 5]

# 访问元素
print(arr[0])  # 输出: 1

# 插入元素
arr.insert(2, 10)  # 在索引2插入10

# 删除元素
arr.pop(3)  # 删除索引3的元素

# 遍历数组
for i in range(len(arr)):
    print(arr[i])

2.2 链表

单向链表
双向链表
循环链表
链表基本操作

# 单链表节点定义
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 链表遍历
def traverse_list(head):
    current = head
    while current:
        print(current.val)
        current = current.next

2.3 栈

栈的定义与特性
栈的实现
栈的应用

# 栈的实现
class Stack:
    def __init__(self):
        self.items = []
        
    def push(self, item):
        self.items.append(item)
        
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        
    def is_empty(self):
        return len(self.items) == 0
        
    def size(self):
        return len(self.items)

2.4 队列

队列的定义与特性
普通队列
双端队列
优先队列
循环队列

# 队列实现
class Queue:
    def __init__(self):
        self.items = []
        
    def enqueue(self, item):
        self.items.insert(0, item)
        
    def dequeue(self):
        if not self.is_empty():
            return self.items.pop()
        
    def is_empty(self):
        return len(self.items) == 0
        
    def size(self):
        return len(self.items)

2.5 哈希表

哈希函数
冲突解决
装载因子
哈希表实现

# 哈希表简单实现
class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
        
    def _hash(self, key):
        return hash(key) % self.size
        
    def put(self, key, value):
        hash_key = self._hash(key)
        for i, (k, v) in enumerate(self.table[hash_key]):
            if k == key:
                self.table[hash_key][i] = (key, value)
                return
        self.table[hash_key].append((key, value))
        
    def get(self, key):
        hash_key = self._hash(key)
        for k, v in self.table[hash_key]:
            if k == key:
                return v
        return None

三、排序算法

3.1 排序算法分类
- 比较排序 vs 非比较排序
- 内部排序 vs 外部排序
- 稳定排序 vs 不稳定排序

3.2 简单排序

冒泡排序
选择排序
插入排序

# 冒泡排序
def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

3.3 高级排序

快速排序
归并排序
堆排序
希尔排序

# 快速排序
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.4 线性排序
- 计数排序
- 桶排序
- 基数排序
3.5 排序算法比较
- 时间复杂度对比
- 空间复杂度对比
- 稳定性对比
- 适用场景

四、搜索算法

4.1 线性搜索

顺序查找
哨兵查找

# 线性搜索
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

4.2 二分搜索

二分查找原理
二分查找实现
二分查找变体

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

4.3 哈希搜索
- 哈希查找
- 布隆过滤器
4.4 树形搜索
- 二叉搜索树
- B树/B+树

4.5 字符串搜索

KMP算法
Boyer-Moore算法
Rabin-Karp算法

# KMP算法
def kmp_search(text, pattern):
    def build_lps(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length-1]
                else:
                    lps[i] = 0
                    i += 1
        return lps
        
    lps = build_lps(pattern)
    i = j = 0
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            return i - j
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1
    return -1

五、递归与分治

5.1 递归基础
- 递归定义
- 递归三要素
- 递归调用栈
5.2 递归算法设计
- 递归式求解
- 递归树
- 主定理

5.3 分治算法

分治策略
分治算法设计
分治算法分析

# 归并排序（分治算法）
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

5.4 递归与迭代转换
- 尾递归优化
- 递归转迭代
5.5 分治算法应用
- 大整数乘法
- 快速傅里叶变换
- 最近点对问题

六、动态规划

6.1 动态规划基础
- 最优子结构
- 重叠子问题
- 状态转移方程
6.2 动态规划步骤
- 定义状态
- 确定状态转移
- 确定初始条件
- 计算顺序

6.3 经典动态规划问题

斐波那契数列
最长公共子序列
最长递增子序列
0-1背包问题
完全背包问题

# 斐波那契数列（动态规划）
def fibonacci_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]

# 0-1背包问题
def knapsack_01(weights, values, capacity):
    n = len(weights)
    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]

6.4 动态规划优化
- 空间优化
- 状态压缩
- 记忆化搜索
6.5 动态规划应用
- 编辑距离
- 矩阵链乘法
- 最优二叉搜索树
- 旅行商问题

七、贪心算法

7.1 贪心算法基础
- 贪心选择性质
- 最优子结构
- 贪心算法与动态规划区别
7.2 贪心算法设计
- 贪心策略选择
- 算法正确性证明

7.3 经典贪心算法问题

活动选择问题
霍夫曼编码
最小生成树
单源最短路径

# 活动选择问题
def activity_selection(start, finish):
    n = len(start)
    activities = []
        
    # 按结束时间排序
    sorted_activities = sorted(zip(finish, start))
    finish_sorted, start_sorted = zip(*sorted_activities)
        
    i = 0
    activities.append(0)
        
    for j in range(1, n):
        if start_sorted[j] >= finish_sorted[i]:
            activities.append(j)
            i = j
        
    return activities

7.4 贪心算法应用
- 找零钱问题
- 区间调度问题
- 任务调度问题
- 集合覆盖问题

八、回溯算法

8.1 回溯算法基础
- 回溯法定义
- 解空间树
- 剪枝函数
8.2 回溯算法框架
- 递归回溯
- 迭代回溯

8.3 经典回溯问题

N皇后问题
子集和问题
全排列
组合问题

# N皇后问题
def solve_n_queens(n):
    def is_safe(board, row, col):
        # 检查列
        for i in range(row):
            if board[i][col] == 'Q':
                return False
            
        # 检查左上对角线
        i, j = row-1, col-1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
            
        # 检查右上对角线
        i, j = row-1, col+1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
            
        return True
        
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
            
        for col in range(n):
            if is_safe(board, row, col):
                board[row][col] = 'Q'
                backtrack(row+1)
                board[row][col] = '.'
        
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0)
    return result

8.4 回溯算法优化
- 可行性剪枝
- 最优性剪枝
- 记忆化
8.5 回溯算法应用
- 数独求解
- 图的着色问题
- 哈密顿回路
- 0-1背包问题

九、图算法

9.1 图的基本概念

图的定义
图的表示
图的基本术语

# 图的邻接表表示
class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = {v: [] for v in range(vertices)}
        
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)  # 无向图

9.2 图的遍历

深度优先搜索
广度优先搜索

# 深度优先搜索
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
        
    for neighbor in graph.adj_list[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
        
    return visited

9.3 最短路径算法
- Dijkstra算法
- Bellman-Ford算法
- Floyd-Warshall算法
9.4 最小生成树
- Kruskal算法
- Prim算法
9.5 拓扑排序
- 拓扑排序算法
- 应用场景
9.6 强连通分量
- Kosaraju算法
- Tarjan算法
9.7 网络流算法
- 最大流
- 最小割
- Ford-Fulkerson算法
- Edmonds-Karp算法

十、高级数据结构

10.1 树

二叉树
二叉搜索树
平衡二叉树
B树/B+树
线段树
树状数组

# 二叉搜索树
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None
        
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(self.root, val)
        
    def _insert(self, node, val):
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
            else:
                self._insert(node.left, val)
        else:
            if not node.right:
                node.right = TreeNode(val)
            else:
                self._insert(node.right, val)

10.2 堆
- 二叉堆
- 优先队列
- 左偏树

10.3 并查集

并查集操作
路径压缩
按秩合并

# 并查集
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
        
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
            
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
            return True
        return False

10.4 Trie树
- Trie树实现
- 应用场景
10.5 跳表
- 跳表原理
- 跳表操作
10.6 布隆过滤器
- 布隆过滤器原理
- 应用场景

十一、字符串算法

11.1 字符串匹配
- 朴素算法
- KMP算法
- Rabin-Karp算法
11.2 字符串处理
- 字符串反转
- 字符串分割
- 字符串替换
11.3 正则表达式
- 正则语法
- 正则引擎
11.4 字典树
- Trie树
- 后缀树
- 后缀数组
11.5 字符串压缩
- 哈夫曼编码
- LZW算法

十二、数论算法

12.1 基本数论
- 质数判定
- 最大公约数
- 最小公倍数
12.2 模运算
- 模运算性质
- 模逆元
- 中国剩余定理

12.3 素数算法

埃拉托斯特尼筛法
欧拉筛法
米勒-拉宾素性测试

# 埃拉托斯特尼筛法
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
        
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
        
    primes = [i for i in range(2, n+1) if is_prime[i]]
    return primes

12.4 快速幂
- 快速幂算法
- 矩阵快速幂
12.5 组合数学
- 排列组合
- 二项式系数
- 卡特兰数

十三、计算几何

13.1 基本几何对象
- 点
- 向量
- 直线
- 多边形
13.2 几何运算
- 点积
- 叉积
- 距离计算
13.3 几何算法
- 凸包算法
- 线段相交判断
- 多边形包含判断
13.4 扫描线算法
- 扫描线原理
- 应用场景

十四、近似算法

14.1 近似算法基础
- 近似比
- 近似方案
14.2 经典近似问题
- 旅行商问题
- 顶点覆盖
- 集合覆盖
14.3 随机化算法
- 随机化快速排序
- 随机化选择算法
14.4 启发式算法
- 遗传算法
- 模拟退火
- 蚁群算法

十五、算法设计范式

15.1 穷举法
- 朴素穷举
- 分支限界
15.2 递推法
- 递推关系
- 递推求解
15.3 迭代法
- 迭代改进
- 不动点迭代
15.4 随机化方法
- 蒙特卡洛方法
- 拉斯维加斯方法
15.5 并行算法
- 并行计算模型
- 并行算法设计

十六、算法优化

16.1 时间优化
- 减少循环
- 提前终止
- 记忆化
16.2 空间优化
- 原地操作
- 滚动数组
- 压缩存储
16.3 代码优化
- 避免重复计算
- 使用内置函数
- 选择合适数据结构
16.4 算法选择策略
- 问题特征分析
- 算法适用性评估
- 性能权衡

十七、算法竞赛

17.1 竞赛平台
- LeetCode
- Codeforces
- AtCoder
- HackerRank
17.2 竞赛技巧
- 问题分析
- 解题策略
- 调试技巧
17.3 常用模板
- 输入输出模板
- 常用算法模板
- 数据结构模板
17.4 比赛策略
- 时间管理
- 题目选择
- 团队协作

十八、学习资源

18.1 经典书籍
- 《算法导论》
- 《算法》
- 《编程珠玑》
18.2 在线课程
- 中国大学MOOC
- Coursera
- 极客时间
18.3 刷题平台
- LeetCode
- 牛客网
- 洛谷
18.4 实践项目
- 实现经典算法
- 参与开源项目
- 算法可视化
18.5 社区资源
- 算法论坛
- 技术博客
- GitHub仓库

Share on

X Facebook LinkedIn Bluesky

xdh2580

算法ALGO

算法系统学习大纲（以python示例）

一、算法基础

二、基础数据结构

三、排序算法

四、搜索算法

五、递归与分治

六、动态规划

七、贪心算法

八、回溯算法

九、图算法

十、高级数据结构

十一、字符串算法

十二、数论算法

十三、计算几何

十四、近似算法

十五、算法设计范式

十六、算法优化

十七、算法竞赛

十八、学习资源

Share on

You may also enjoy

进阶-python函数相关

进阶-pytest配置文件

PO模式（Page Object Model）

计算机网络

xdh2580

算法 系统学习大纲（以python示例）

一、算法基础

二、基础数据结构

三、排序算法

四、搜索算法

五、递归与分治

六、动态规划

七、贪心算法

八、回溯算法

九、图算法

十、高级数据结构

十一、字符串算法

十二、数论算法

十三、计算几何

十四、近似算法

十五、算法设计范式

十六、算法优化

十七、算法竞赛

十八、学习资源

Share on

You may also enjoy

进阶-python函数相关

进阶-pytest配置文件

PO模式（Page Object Model）

计算机网络

算法系统学习大纲（以python示例）