我们日常使用的复杂度为 O(1)、O(n log n) 和 O(log n) 的算法有哪些？
如果您想要问题中给出的具有时间复杂度的算法/语句组的示例，这里有一个小列表 -
O(1) time
- 访问数组索引 (int a = ARR[5];)
- 在链表中插入节点
- 堆栈上的压入和弹出
- 插入队列和从队列中删除
- 找出存储在数组中的树中节点的父节点或左/右子节点
- 跳转到双向链表中的下一个/上一个元素
O(n) time
简而言之，所有暴力算法或需要线性的 Noob 算法都基于 O(n) 时间复杂度
- 遍历数组
- 遍历链表
- 线性搜索
- 删除链表中的特定元素（未排序）
- 比较两个字符串
- 检查回文
- 计数/桶排序
在这里你还可以找到一百万个这样的例子......
O(log n) time
- 二分查找
- 在二叉搜索树中查找最大/最小数
- 某些基于线性函数的分而治之算法
- 计算斐波那契数 - 最佳方法
这里的基本前提是不使用完整的数据，并通过每次迭代减少问题的规模
O(n log n) time
考虑到分而治之，引入了“log n”因子。其中一些算法是最优化的并且经常使用。
- 归并排序
- 堆排序
- 快速排序
- 某些基于优化 O(n^2) 算法的分治算法
O(n^2) time
如果存在 O(nlogn) 对应算法，这些算法应该是效率较低的算法。这里一般的应用可能就是Brute Force。
- 冒泡排序
- 插入排序
- 选择排序
- 遍历一个简单的二维数组
O(n!) time
- 通过暴力搜索解决旅行商问题
- 生成部分有序集的所有无限制排列；
- 用拉普拉斯展开式求行列式
- 枚举集合的所有分区
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
