具有O(1),O(n log n)和O(log n)复杂性的algorithm的例子

O(1),O(n log n)和O(log n)的复杂性,我们每天使用的algorithm是什么?

如果您想要问题中给出的具有时间复杂度的algorithm/语句组的例子,这里是一个小列表 –

O(1)次
1.访问数组索引(int a = ARR [5];)
2.在链接列表中插入一个节点
3.在堆栈上推送和popup
4.从队列中插入和删除
5.查找Array中存储的树中父节点或左/右节点的子节点
6.跳转到双链表中的下一个/上一个元素
你可以find更多的例子

准时
1.遍历一个数组
2.遍历一个链表
3.线性search
4.删除链接列表中的特定元素(未sorting)
5.比较两个string
6.检查回文
7.计数/桶分类
在这里也可以find更多的这样的例子。
简而言之,所有需要线性的蛮力algorithm或Noobalgorithm都基于O(n)时间复杂度

O(log n)时间
1.二进制search
2.在二叉search树中查找最大/最小的数字
3.基于线性function的某些分治algorithm
4.计算斐波纳契数 – 最好的方法
这里的基本前提是不使用完整的数据,并在每次迭代中减less问题的大小

O(nlogn)时间
1.合并sorting
2.堆sorting
3.快速sorting
4.基于优化O(n ^ 2)algorithm的分治algorithm
考虑分而治之,引入“log n”的因素。 其中一些algorithm是最优化的,经常使用。

O(n ^ 2)时间
1.泡沫sorting
2.插入sorting
3.selectsorting
遍历一个简单的二维数组
如果它们的O(nlogn)对象存在,这些algorithm应该是效率较低的algorithm。 一般的应用可能是蛮力的。

我希望这能很好地回答你的问题。 如果用户有更多的例子添加,我会更感到高兴:)

O(1)一个简单例子可能是return 23; – 无论input什么,这将返回一个固定的,有限的时间。

O(N log N)的典型例子是用一个好的algorithm(例如mergesort)对input数组进行sorting。

一个典型的例子,如果O(log N)将在一个sorting后的input数组中查找一个值。

O(1) – 大多数的烹饪程序是O(1),也就是说,即使有更多的人要烹饪也需要一定的时间(在某种程度上,因为你的锅/饭可能用完了并需要分割烹饪)

O(logn) – 在你的电话簿中find一些东西。 认为二进制search。

O(n) – 读一本书,其中n是页数。 这是阅读一本书的最less时间。

O(nlogn) – 不能立即想到一个可能每天都是nlogn的东西,除非你通过合并或快速sorting来排列卡片!

我可以为您提供一些通用algorithm…

  • O(1):访问数组中的元素(即int i = a [9])
  • O(n log n):quick或mergesort(平均)
  • O(log n):二进制search

这听起来像是家庭作业/面试这样的问题。 如果你正在寻找更具体的东西,那么一般的公众都不知道一个stream行的应用程序的底层实现(当然是开源),这个概念也不适用于“应用程序”

软件应用程序的复杂性不是测量的,也不是用大O表示的。 测量algorithm的复杂性并比较相同域中的algorithm是有用的。 很可能,当我们说O(n)时,我们的意思是它是“O(n) 比较 ”或“O(n)算术运算”。 这意味着,您无法比较任何一对algorithm或应用程序。

O(1):find国际象棋中最好的下一步棋(或者就此而言)。 由于游戏状态的数量是有限的,所以只有O(1):-)

O(1) – 从双向链表中删除一个元素。 例如

 typedef struct _node { struct _node *next; struct _node *prev; int data; } node; void delete(node **head, node *to_delete) { . . . } 

O(n log n)是您能够以多快的速度对任意集进行sorting的上界(假设一个标准的并不是高度并行的计算模型)。

您可以将以下algorithm添加到列表中:

O(1) – 确定一个数字是偶数还是奇数; 使用HashMap

O(logN) – 计算x ^ N,

O(N Log N) – 最长的子序列