算法设计与分析课程的时间空间复杂度
算法设计与分析课程的时间空间复杂度:
总结
算法 |
时间复杂度 |
空间复杂度 |
说明 |
Hanoi |
$ O(2^n) $ |
$ O(n) $ |
递归使用 |
会场安排问题 |
(O(nlogn)) |
(O(n)) |
贪心 |
哈夫曼树编码 |
(O(nlogn)) |
$$O(n)$$ |
贪心 $$O(n^2) $$(未采用特殊数据结构) |
dijkstra |
(O(n^2)) |
(O(n)) |
单源最短路径问题,贪心 |
Prim |
(O(n^2)) |
(O(n)) |
最小生成树 |
Kruskal |
$$O(eloge)$$ |
(O(e)) |
最小生成树 |
大整数乘法(四次) |
(O(n^2)) |
(O(log_2n)) |
分治 |
大整数乘法(三次) |
(O(n^{log_23})) |
(O(log_2n)) |
分治 |
二分查找(递归) |
(O(log_2n)) |
(O(log_2n)) |
分治 |
二分查找(非递归) |
(O(log_2n)) |
(O(1)) |
分治 |
循环日程表 |
(O(n^2)) |
(O(log_2n)) |
分治 |
归并排序 |
$$O(nlog_2n)$$ |
(O(n)) |
分治 |
快速排序 |
$$O(nlog_2n)$$ |
(O(n)) |
分治 |
棋盘覆盖问题 |
$$O(4^k)$$ |
$$ O(k)$$ |
分治 |
Fibonacci(递归) |
$$ O({1.628}^n) $$ |
(O(n)) |
动态规划 |
Fibonacci(非递归) |
(O(n)) |
(O(n)) |
动态规划 |
最长公共子序列(非递归) |
(O(mn)-O(n^2)) |
(O(mn)-O(n^2)) |
动态规划 |
最长公共子序列(递归) |
(O(2^{min(m,n)})) |
(O(min(m,n))) |
动态规划 |
矩阵连乘(递归) |
(O(2^n)) |
(O(n^2)) |
动态规划 |
矩阵连乘(DP) |
(O(n^3)) |
(O(n^2)) |
动态规划 |
0-1背包(DP) |
(O(nw)->O(n2^n)) |
(O(nw)) |
动态规划 |
0-1背包(贪心) |
(O(nlog_2n)) |
(O(n)) |
贪心法 |
DFS |
$$O( |
V |
+ |
BFS |
$$O( |
V |
+ |
子集树递归回溯 |
(O(2^n)) |
|
搜索法 |
排列树递归回溯 |
(O(n!)) |
|
搜索法 |
满m叉树递归回溯 |
(O(m^n)) |
|
搜索法 |
n皇后满m叉树 |
(O(nm^n)) |
(O(n^n)) |
搜索法 |
n皇后排列树 |
(O(n^2(n-1)!)) |
(O(n!)) |
搜索法 |
0-1背包回溯法 |
(O(n2^n)) |
(O(2^n)) |
搜索法 |
最大团问题 |
(O(n2^n)) |
(O(2^n)) |
搜索法 |
旅行商问题TSP |
(O(n!)) |
(O(n!)) |
搜索法 |
图的m着色GCP |
(O(nm^n)) |
(O(m^n)) |
搜索法 |
队列式0-1背包 |
$$O(n2^n)$$ |
(O(2^n)) |
搜索法 |
优先队列0-1背包 |
(O(n2^n)) |
(O(2^n)) |
搜索法 |
队列式旅行商 |
(O(n!)) |
(O(n!)) |
搜索法 |
优先队列式旅行商 |
(O(n!)) |
(O(n!)) |
搜索法 |
布线问题 队列式 |
(O(nm)) |
(O(nm)) |
搜索法 |
原文地址:https://www.cnblogs.com/pprp/p/9947537.html