算法設(shè)計(jì)與分析課程的時(shí)間空間復(fù)雜度：

總結(jié)

算法時(shí)間復(fù)雜度空間復(fù)雜度說明

Hanoi	$ O(2^n) $	$ O(n) $	遞歸使用
會(huì)場(chǎng)安排問題	\(O(nlogn)\)	\(O(n)\)	貪心
哈夫曼樹編碼	\(O(nlogn)\)	\[O(n)\]	貪心 \[O(n^2) \]（未采用特殊數(shù)據(jù)結(jié)構(gòu)）
dijkstra	\(O(n^2)\)	\(O(n)\)	單源最短路徑問題，貪心
Prim	\(O(n^2)\)	\(O(n)\)	最小生成樹
Kruskal	\[O(eloge)\]	\(O(e)\)	最小生成樹
大整數(shù)乘法（四次）	\(O(n^2)\)	\(O(log_2n)\)	分治
大整數(shù)乘法（三次）	\(O(n^{log_23})\)	\(O(log_2n)\)	分治
二分查找（遞歸）	\(O(log_2n)\)	\(O(log_2n)\)	分治
二分查找（非遞歸）	\(O(log_2n)\)	\(O(1)\)	分治
循環(huán)日程表	\(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)\)	動(dòng)態(tài)規(guī)劃
Fibonacci（非遞歸）	\(O(n)\)	\(O(n)\)	動(dòng)態(tài)規(guī)劃
最長(zhǎng)公共子序列（非遞歸）	\(O(mn)-O(n^2)\)	\(O(mn)-O(n^2)\)	動(dòng)態(tài)規(guī)劃
最長(zhǎng)公共子序列（遞歸）	\(O(2^{min(m,n)})\)	\(O(min(m,n))\)	動(dòng)態(tài)規(guī)劃
矩陣連乘（遞歸）	\(O(2^n)\)	\(O(n^2)\)	動(dòng)態(tài)規(guī)劃
矩陣連乘（DP）	\(O(n^3)\)	\(O(n^2)\)	動(dòng)態(tài)規(guī)劃
0-1背包（DP）	\(O(nw)->O(n2^n)\)	\(O(nw)\)	動(dòng)態(tài)規(guī)劃
0-1背包（貪心）	\(O(nlog_2n)\)	\(O(n)\)	貪心法
DFS	\[O(|V|+|E|)\]		搜索法
BFS	\[O(|V|+|E|)\]		搜索法
子集樹遞歸回溯	\(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)\)	搜索法
最大團(tuán)問題	\(O(n2^n)\)	\(O(2^n)\)	搜索法
旅行商問題TSP	\(O(n!)\)	\(O(n!)\)	搜索法
圖的m著色GCP	\(O(nm^n)\)	\(O(m^n)\)	搜索法
隊(duì)列式0-1背包	\[O(n2^n)\]	\(O(2^n)\)	搜索法
優(yōu)先隊(duì)列0-1背包	\(O(n2^n)\)	\(O(2^n)\)	搜索法
隊(duì)列式旅行商	\(O(n!)\)	\(O(n!)\)	搜索法
優(yōu)先隊(duì)列式旅行商	\(O(n!)\)	\(O(n!)\)	搜索法
布線問題 隊(duì)列式	\(O(nm)\)	\(O(nm)\)	搜索法

轉(zhuǎn)載于:https://www.cnblogs.com/pprp/p/9947537.html

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析课程的时间空间复杂度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。