Rac*_*hel 106 algorithm time-complexity
我们每天使用的具有O(1),O(n log n)和O(log n)复杂度的算法是什么？
小智 218
如果您想要问题中给出的具有时间复杂度的算法/语句组的示例,这里有一个小列表 -
O(1)时间
1.访问数组索引(int a = ARR [5];)
2.在链接列表中插入节点
3.在堆栈上推送和弹出
4.从队列中插入和删除
5.找出父节点或左侧/存储在数组
6 中的树中节点的右子节点.跳转到双链接列表中的下一个/上一个元素
,你可以找到更多这样的例子......
O(n)时间
1.遍历数组
2.遍历链表
3.线性搜索
4.删除链接列表中的特定元素(未排序)
5.比较两个字符串
6.检查回文
7.计数/桶排序
,在这里你也可以找到更多这样的例子......
简而言之,所有需要线性的Brute Force算法或Noob基于O(n)时间复杂度
O(log n)时间
1.二进制搜索
2.在二叉搜索树中查找最大/最小数字
3.基于线性功能的某些划分和征服算法
4.计算斐波纳契数 - 最佳方法
这里的基本前提是不使用完整的数据,并减少每次迭代的问题大小
O(nlogn)时间
1.合并排序
2.堆排序
3.快速排序
4.基于优化O(n ^ 2)算法
的某些划分和征服算法通过考虑划分和征服引入'log n'因子.其中一些算法是经过最佳优化的算法并经常使用.
O(n ^ 2)时间
1.冒泡排序
2.插入排序
3.选择排序
4.遍历简单的2D阵列
如果存在O(nlogn)对应物,则这些算法应该是效率较低的算法.一般申请可能是Brute Force.
我希望这能很好地回答你的问题.如果用户有更多的例子要添加,我会非常高兴:)
Ale*_*lli 28
一个简单的例子O(1)可能是return 23;- 无论输入什么,这将在固定的有限时间内返回.
一个典型的例子是O(N log N)用一个好的算法(例如mergesort)对输入数组进行排序.
一个典型的例子O(log N)是如何通过二分查找排序的输入数组中的值.
Chi*_*hii 24
O(1) - 大多数烹饪程序都是O(1),也就是说,即使有更多的人做饭也需要一定的时间(在某种程度上,因为你的锅/锅可能用完了空间)并需要分开烹饪)
O(logn) - 在电话簿中找到一些东西.想二元搜索.
O(n) - 读一本书,其中n是页数.这是阅读书籍所需的最短时间.
O(nlogn) - 不能立即想到每天可能会做的事情,除非你通过合并或快速排序来分类卡片!
Sca*_*rew 10
我可以为你提供一些通用算法......
这些将是直觉反应,因为这听起来像家庭作业/面试的问题.如果你正在寻找更具体的东西,那就更难了,因为公众通常不知道流行应用程序的底层实现(当然是开源),这个概念一般也不适用于"应用程序"