算法设计与分析课程的时间空间复杂度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法设计与分析课程的时间空间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1722字，纯文字阅读大概需要3分钟。

内容图文

算法设计与分析课程的时间空间复杂度：

总结

算法	时间复杂度	空间复杂度	说明
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|+|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)\)	搜索法
最大团问题	\(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)\)	搜索法

内容总结

以上是互联网集市为您收集整理的算法设计与分析课程的时间空间复杂度全部内容，希望文章能够帮你解决算法设计与分析课程的时间空间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---