141

我们日常使用的算法有哪些复杂度为 O(1)、O(n log n) 和 O(log n)？

4

11 回答 11

282

如果您想要问题中给出的具有时间复杂度的算法/语句组的示例，这里有一个小列表 -

O(1)时间

  • 访问数组索引 (int a = ARR[5];)
  • 在链表中插入一个节点
  • 在堆栈上推送和弹出
  • 从队列中插入和删除
  • 找出存储在数组中的树中节点的父节点或左/右子节点
  • 跳转到双向链表中的下一个/上一个元素

O(n)时间

简而言之，所有需要线性的蛮力算法或 Noob 算法都基于 O(n) 时间复杂度

  • 遍历数组
  • 遍历链表
  • 线性搜索
  • 删除链表中的特定元素（未排序）
  • 比较两个字符串
  • 检查回文
  • 计数/桶排序，在这里你也可以找到一百万个这样的例子......

O(log n)时间

  • 二进制搜索
  • 在二叉搜索树中查找最大/最小数
  • 基于线性功能的某些分而治之的算法
  • 计算斐波那契数 - 最佳方法这里的基本前提是不使用完整的数据，并减少每次迭代的问题大小

O(n log n)时间

考虑到分而治之，引入了“log n”因子。其中一些算法是最优化的并且经常使用。

  • 合并排序
  • 堆排序
  • 快速排序
  • 基于优化 O(n^2) 算法的某些分而治之的算法

O(n^2)时间

如果存在 O(nlogn) 对应物，则这些算法应该是效率较低的算法。这里的一般应用可能是蛮力。

  • 冒泡排序
  • 插入排序
  • 选择排序
  • 遍历一个简单的二维数组
于 2012-07-23T11:37:22.267 回答
34

O(1) - 大多数烹饪程序都是 O(1)，也就是说，即使有更多的人要做饭，它也需要一定的时间（在一定程度上，因为你的锅/平底锅的空间可能会用完并且需要分开烹饪）

O(logn) - 在你的电话簿中找到一些东西。考虑二进制搜索。

O(n) - 阅读一本书，其中 n 是页数。这是阅读一本书所需的最少时间。

O(nlogn) - 不能立即想到一个人每天可能会做的事情是 nlogn……除非你通过合并或快速排序来对卡片进行排序！

于 2009-10-20T05:57:25.570 回答
30

一个简单的例子O(1)可能是return 23;——无论输入什么，它都会在固定的有限时间内返回。

一个典型的例子是O(N log N)用一个好的算法（例如mergesort）对一个输入数组进行排序。

一个典型的例子O(log N)是通过二分法在排序的输入数组中查找一个值。

于 2009-10-20T05:43:24.450 回答
10

我可以为您提供一些通用算法...

  • O(1)：访问数组中的元素（即 int i = a[9]）
  • O(n log n)：快速或归并排序（平均）
  • O(log n)：二分查找

这些将是直觉反应，因为这听起来像是家庭作业/面试之类的问题。如果您正在寻找更具体的东西，那就有点困难了，因为公众通常不知道流行应用程序的底层实现（当然是保留开源），这个概念通常也不适用于“应用程序”

于 2009-10-20T05:43:12.157 回答
4

O(1)：在国际象棋中找到最好的下一步（或围棋）。由于游戏状态的数量是有限的，它只有 O(1) :-)

于 2009-10-20T05:50:33.620 回答
3

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

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}
于 2009-10-20T09:13:13.460 回答
2

You can add following algorithms to your list:

O(1) - Determining if a number is even or odd; Working with HashMap

O(logN) - computing x^N,

O(N Log N) - Longest increasing subsequence

于 2009-10-20T07:01:44.417 回答
2

软件应用程序的复杂性没有被测量，也不是用大 O 表示法编写的。它仅用于衡量算法复杂度和比较同一域中的算法。最有可能的是，当我们说 O(n) 时，我们的意思是它是“O(n)比较”或“O(n) 算术运算”。这意味着，您无法比较任何一对算法或应用程序。

于 2009-10-20T05:40:44.580 回答
1

O (n log n) 是众所周知的对任意集合进行排序的速度上限（假设是标准而非高度并行的计算模型）。

于 2009-10-20T05:47:21.597 回答
0

0(logn)-二分查找，数组中的峰值元素（可以有多个峰值） 0(1)-python 中计算列表或字符串的长度。len() 函数需要 0(1) 时间。访问数组中的元素需要 0(1) 时间。堆栈中的推送操作需要 0(1) 时间。0(nlogn) - 合并排序。在 python 中排序需要 nlogn 时间。因此，当您使用 listname.sort() 时，它需要 nlogn 时间。

由于冲突，在哈希表中进行注释搜索有时会花费超过恒定时间。

于 2018-10-17T13:36:37.343 回答
0

O( 2N )

O(2 N ) 表示一种算法，其增长随着输入数据集的每个添加而翻倍。O(2 N ) 函数的增长曲线是指数型的 - 从非常浅的开始，然后迅速上升。O(2 N ) 函数的一个示例是斐波那契数的递归计算：

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
于 2018-10-29T15:38:13.037 回答