算法演示 | CC408

查找专题 · 5 项

查找算法

进入查找实验室

算法	适用结构	最好	平均	最坏	空间
顺序查找Linear Search	线性表查找	`O(1)`	`O(n)`	`O(n)`	`O(1)`
二分查找Binary Search	有序表查找	`O(1)`	`O(log n)`	`O(log n)`	`O(1)`
分块查找Block Search	索引查找	`O(1)`	`O(sqrt(n))`	`O(sqrt(n))`	`O(sqrt(n))`
二叉搜索树查找BST Search	树表查找	`O(1)`	`O(log n)`	`O(n)`	`O(1)`
哈希查找Hash Search	散列查找	`O(1)`	`O(1)`	`O(n)`	`O(n)`

排序专题 · 9 项

排序算法

进入排序实验室

算法	类别	最好	平均	最坏	空间	稳定	原地
冒泡排序Bubble Sort	交换排序	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`	是	是
选择排序Selection Sort	选择排序	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`	否	是
直接插入排序Insertion Sort	插入排序	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`	是	是
希尔排序Shell Sort	插入排序	`取决于增量`	`约 O(n^1.3)`	`O(n^2)`	`O(1)`	否	是
归并排序Merge Sort	归并排序	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	是	否
快速排序Quick Sort	交换排序	`O(n log n)`	`O(n log n)`	`O(n^2)`	`O(log n) 平均`	否	是
堆排序Heap Sort	选择排序	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	否	是
计数排序Counting Sort	非比较排序	`O(n+k)`	`O(n+k)`	`O(n+k)`	`O(n+k)`	是	否
基数排序Radix Sort	非比较排序	`O(d(n+r))`	`O(d(n+r))`	`O(d(n+r))`	`O(n+r)`	是	否

树专题 · 5 项

树算法

进入树实验室

算法	结构	平均时间	空间
二叉树遍历Binary Tree Traversal	树遍历	`O(n)`	`O(h)`
由遍历序列重建二叉树Rebuild Binary Tree	树构造	`O(n)`	`O(n)`
AVL 树插入AVL Tree Insertion	平衡二叉搜索树	`O(log n)`	`O(h)`
哈夫曼编码Huffman Coding	最优二叉树	`O(n log n)`	`O(n)`
并查集Union-Find	不相交集合	`O(alpha(n))`	`O(n)`

图专题 · 8 项

图算法

进入图实验室

算法	问题类型	平均时间	空间
深度优先搜索Depth-First Search	图遍历	`O(V+E)`	`O(V)`
广度优先搜索Breadth-First Search	图遍历	`O(V+E)`	`O(V)`
Prim 最小生成树Prim Minimum Spanning Tree	最小生成树	`O(E log V)`	`O(V+E)`
Kruskal 最小生成树Kruskal Minimum Spanning Tree	最小生成树	`O(E log E)`	`O(V)`
Dijkstra 最短路径Dijkstra Shortest Path	单源最短路径	`O(E log V)`	`O(V+E)`
Floyd 全源最短路径Floyd-Warshall	全源最短路径	`O(V^3)`	`O(V^2)`
拓扑排序Topological Sort	有向无环图	`O(V+E)`	`O(V)`
关键路径Critical Path	AOE 网	`O(V+E)`	`O(V+E)`

动态规划专题 · 5 项

动态规划

进入动态规划实验室

算法	状态类型	平均时间	空间
斐波那契数列Fibonacci	动态规划入门	`O(n)`	`O(n)`
0/1 背包0/1 Knapsack	选择型动态规划	`O(nC)`	`O(nC)`
最长公共子序列Longest Common Subsequence	序列动态规划	`O(mn)`	`O(mn)`
矩阵连乘Matrix Chain Multiplication	区间动态规划	`O(n^3)`	`O(n^2)`
编辑距离Edit Distance	字符串动态规划	`O(mn)`	`O(mn)`