《算法思维导图》

I. 算法基础 (Algorithm Fundamentals)

A. 概念与特性 (Concepts and Characteristics)

1. 定义: 解决特定问题的有限步骤序列。
   2. 特性:
      • 输入 (Input): 零个或多个输入。
      • 输出 (Output): 至少一个输出。
      • 有穷性 (Finiteness): 在有限步骤内结束。
      • 确定性 (Determinism): 每个步骤都明确无歧义。
      • 可行性 (Feasibility): 每个步骤都可以在有限时间内完成。

B. 算法表示 (Algorithm Representation)

1. 自然语言: 直观，但容易产生歧义。
   2. 流程图: 图形化表示，易于理解。
      • 顺序结构
      • 选择结构 (if/else)
      • 循环结构 (for/while)
   3. 伪代码: 接近编程语言，表达更清晰。
   4. 编程语言: 可执行，但依赖特定语言。

C. 算法评价 (Algorithm Evaluation)

1. 时间复杂度 (Time Complexity):
   • 定义: 算法执行时间随输入规模增长的趋势。
   • 表示: 大O记号 (O(n), O(log n), O(n^2), O(2^n)等)。
   • 常见复杂度: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n), O(n!)
   • 分析方法: 计算基本操作的执行次数。
     2. 空间复杂度 (Space Complexity):
   • 定义: 算法占用内存空间随输入规模增长的趋势。
   • 表示: 大O记号 (O(1), O(n)等)。
   • 分析: 考虑算法使用的额外空间。
     3. 正确性 (Correctness): 算法能否正确解决问题。
   • 测试: 通过测试用例验证算法的正确性。
   • 证明: 形式化证明算法的正确性。
     4. 可读性 (Readability): 算法是否易于理解和维护。
     5. 健壮性 (Robustness): 算法在异常情况下是否能正常运行。

II. 常用算法 (Common Algorithms)

A. 排序算法 (Sorting Algorithms)

1. 比较排序: 基于元素之间的比较进行排序。
   • 冒泡排序 (Bubble Sort): O(n^2)，稳定。
   • 选择排序 (Selection Sort): O(n^2)，不稳定。
   • 插入排序 (Insertion Sort): O(n^2)，稳定，适用于小规模数据或基本有序的数据。
   • 希尔排序 (Shell Sort): O(n log n) ~ O(n^2)，不稳定，插入排序的改进。
   • 归并排序 (Merge Sort): O(n log n)，稳定，分治法。
   • 快速排序 (Quick Sort): O(n log n) (平均), O(n^2) (最坏)，不稳定，分治法。
   • 堆排序 (Heap Sort): O(n log n)，不稳定，基于堆数据结构。
     2. 非比较排序: 不基于元素之间的比较。
   • 计数排序 (Counting Sort): O(n+k)，稳定，k为数据范围。
   • 桶排序 (Bucket Sort): O(n+k)，平均情况下O(n)，稳定，k为桶的数量。
   • 基数排序 (Radix Sort): O(nk)，稳定，k为数字位数。

B. 搜索算法 (Searching Algorithms)

1. 线性搜索 (Linear Search): O(n)，逐个比较。
   2. 二分搜索 (Binary Search): O(log n)，有序数组。
   3. 哈希搜索 (Hash Search): O(1) (平均), O(n) (最坏)，哈希表。
   4. 深度优先搜索 (DFS): 用于图和树的遍历。
   5. 广度优先搜索 (BFS): 用于图和树的遍历。

C. 图算法 (Graph Algorithms)

1. 图的表示:
   • 邻接矩阵: 易于实现，但空间复杂度高。
   • 邻接表: 节省空间，但访问邻居节点效率稍低。
     2. 最小生成树 (Minimum Spanning Tree):
   • Prim 算法: 贪心算法。
   • Kruskal 算法: 贪心算法。
     3. 最短路径 (Shortest Path):
   • Dijkstra 算法: 单源最短路径，适用于非负权图。
   • Bellman-Ford 算法: 单源最短路径，适用于包含负权边的图。
   • Floyd-Warshall 算法: 所有顶点对之间的最短路径。
     4. 拓扑排序 (Topological Sort): 有向无环图 (DAG)。

D. 字符串算法 (String Algorithms)

1. 字符串匹配:
   • 暴力匹配 (Brute Force): O(mn)。
   • KMP 算法: O(m+n)。
   • Boyer-Moore 算法: 通常比KMP更快。
     2. 字符串编辑距离 (Edit Distance): 动态规划。

E. 动态规划 (Dynamic Programming)

1. 思想: 将问题分解为相互重叠的子问题，并保存子问题的解，避免重复计算。
   2. 适用场景: 最优子结构，重叠子问题。
   3. 步骤:
      • 定义状态: 描述子问题的解。
      • 状态转移方程: 描述状态之间的关系。
      • 初始化: 确定边界条件。
      • 计算顺序: 确保计算子问题之前，所有依赖的子问题都已经计算完毕。
   4. 常见问题: 背包问题，最长公共子序列，最长递增子序列。

F. 贪心算法 (Greedy Algorithm)

1. 思想: 每一步都做出当前看来最好的选择，期望最终得到全局最优解。
   2. 适用场景: 具有最优子结构性质的问题。
   3. 常见问题: 活动选择问题，哈夫曼编码。

G. 分治算法 (Divide and Conquer)

1. 思想: 将问题分解为规模更小的子问题，递归解决子问题，然后将子问题的解合并成原问题的解。
   2. 步骤:
      • 分解 (Divide): 将问题分解为相互独立的子问题。
      • 解决 (Conquer): 递归解决子问题。
      • 合并 (Combine): 将子问题的解合并成原问题的解。
   3. 常见问题: 归并排序，快速排序。

III. 数据结构 (Data Structures)

A. 线性数据结构 (Linear Data Structures)

1. 数组 (Array): 连续存储，随机访问，插入/删除效率低。
   2. 链表 (Linked List): 非连续存储，插入/删除效率高，随机访问效率低。
      • 单向链表
      • 双向链表
      • 循环链表
   3. 栈 (Stack): 后进先出 (LIFO)。
   4. 队列 (Queue): 先进先出 (FIFO)。

B. 树形数据结构 (Tree Data Structures)

1. 二叉树 (Binary Tree): 每个节点最多有两个子节点。
   • 满二叉树
   • 完全二叉树
     2. 二叉搜索树 (Binary Search Tree): 左子树小于根节点，右子树大于根节点。
     3. 平衡二叉树 (Balanced Binary Tree): AVL树，红黑树。
     4. 堆 (Heap): 最大堆，最小堆。
     5. 前缀树 (Trie Tree): 用于字符串存储和查找。

C. 图 (Graph)

1. 有向图 (Directed Graph)
   2. 无向图 (Undirected Graph)
   3. 加权图 (Weighted Graph)

D. 哈希表 (Hash Table)

1. 原理: 通过哈希函数将键映射到表中的位置。
   2. 冲突处理:
      • 链地址法
      • 开放寻址法

IV. 算法设计思想 (Algorithm Design Paradigms)

A. 递归 (Recursion)

B. 分治 (Divide and Conquer)

C. 动态规划 (Dynamic Programming)

D. 贪心 (Greedy)

E. 回溯 (Backtracking)

V. 算法的应用 (Algorithm Applications)

A. 搜索引擎 (Search Engine)

B. 推荐系统 (Recommendation System)

C. 图像处理 (Image Processing)

D. 机器学习 (Machine Learning)

E. 数据挖掘 (Data Mining)

上一个主题： 西游记思维导图 下一个主题： 思维导图太阳