算法的例子，其中有O(1),O(n记录n)和O(日志n)的复杂性

StackOverflow https://stackoverflow.com/questions/1592649

  •  22-09-2019
  •  | 
  •  

题

什么是一些算法，我们日常使用，已O(1),O(n记录n)和O(日志n)复杂?

有帮助吗？

解决方案

如果你想算法的例子/组发言的与时间的复杂程度给出一个问题，这里是一个小的列表

O(1) 时间

  • 访问阵列索引(int a=ARR[5];)
  • 插入一个节点联系名单
  • 推动和油炸上堆
  • 插入和脱离的队列
  • 找出的父母或左右儿童的一个节点在一棵树上存在阵列
  • 跳到下一步之前素双向链表

O(n) 时间

简而言之，所有暴力的算法，或小白那些要求直线性的，是根据O(n)一次的复杂性

  • 穿越一系列
  • 遍历的链表
  • 直线索
  • 删除一个特定的元素中的一个链表(不排序)
  • 比较两个字符串
  • 检查回文
  • 计/桶的排序 和这里也可以找到一百万更多这样的例子。...

O(log n) 时间

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

O(n log n) 时间

该因素的记录n'是引入带来虑到分而治之。一些算法是最好的优化的和经常使用。

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

O(n^2) 时间

这些人被认为是低效率的算法，如果他们O(nlogn)对应方都存在。一般应用程序可能是暴力破解这里。

  • 泡沫进行排序
  • 插入排序
  • 选择排序
  • 穿越一个简单的2D阵列

其他提示

O(1)的一个简单的例子可以是return 23; - 无论输入，这将在固定，有限的时间内返回

O(N log N)的典型例子是分选具有良好的算法的输入阵列（例如归并）。

如果O(log N)将查找在通过平分一个排序的输入数组的值的典型例子。

O（1） - 最烹饪程序是O（1），也就是说，它需要即使有更多的人来煮（到一定程度的时候一定量的，因为你可以在空间中运行你的锅/平底锅和需要分割了烹饪）

O（LOGN） - 找到的东西在你的电话簿。想想二进制搜索。

为O（n） - 读书，其中n是页数。它是最小时间量才能阅读书籍。

O（nlogn） - 着马上会想到一个事情可以做日常是nlogn ......除非你排序卡做合并或快速排序

我可以为你提供一些一般性的算法...

  • O(1):访问的一个元件阵列(即int i=a[9])
  • O(n记录n)：快速成了归并排序或(月平均)
  • O(日志n)：二进制的搜索

这些会是肠道的反应，因为这听起来像家庭作业/采访样的问题。如果你是在寻找更具体的东西它有点困难，因为一般公众没有思想的基础的执行情况(备用开放源码的课程)的一个受欢迎的应用程序，也没有一概念在一般适用于一个"程序"

在软件应用程序的复杂性，不测量，并且未在大O符号编写的。测量算法的复杂性，并在同一个域中比较算法这是唯一有用的。最有可能的，当我们说O（n）的，我们的意思是它的 “O（N）的对比的” 或 “O（n）的算术运算”。这意味着，不能比较任何对算法或应用程序。

O（1）：找到在国际象棋的最佳下移动（或转到也如此）。作为游戏状态的数量是有限的，这只是O（1）： - ）

O（1） - 从一个双向链表删除的元素。 e.g。

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


void delete(node **head, node *to_delete)
{
    .
    .
    .
}

您可以添加以下算法列表：

O(1) - 确定一个数是否为偶数还是奇数;与HashMap的工作

O(logN) - 计算的x ^ N，

O(N Log N) - 最长递增子

为O（n log n）的被最著名的是上界可以如何快速排序的任意集合（假设标准，而不是高度并行计算模型）。

0（logn）时间 - 二进制搜索，在一个数组峰值元件（可以有一个以上的峰） 0（1）-in蟒计算列表或字符串的长度。该LEN（）函数取0（1）时间。在阵列中访问的元素取0（1）时间。堆栈中的推操作花费O（1）时间。 0（nlogn）-MERGE排序。在python排序需要nlogn时间。所以，当使用listname.sort（）所花费的时间nlogn

请注意，在搜索在哈希表中有时需要超过因为碰撞恒定时间。

<强> O（2 Ñ）结果

O（2 Ñ）表示的算法其生长双打与每个additon到输入数据集。的O的生长曲线（2 Ñ）函数是指数 - 出发很浅，然后meteorically上升。 （2 Ñ）函数是斐波那契数的递归计算的O的示例：

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top