一尘不染

具有O(1),O(n log n)和O(log n)复杂度的算法示例

algorithm

我们每天使用哪些复杂度为O(1),O(n log n)和O(log n)的算法?


阅读 222

收藏
2020-07-28

共1个答案

一尘不染

如果您要使用问题中给出的具有时间复杂度的算法/语句组示例,请查看以下清单-

O(1) 时间

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

O(n) 时间

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

  • 遍历数组
  • 遍历链接列表
  • 线性搜寻
  • 删除链接列表中的特定元素(未排序)
  • 比较两个字符串
  • 检查回文
  • 计数/桶排序,在这里您还可以找到更多这样的示例…。

O(log n) 时间

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

O(n log n) 时间

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

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

O(n^2) 时间

如果存在与它们对应的O(nlogn),则这些算法的效率较低。此处的通用应用程序可能是蛮力。

  • 气泡排序
  • 插入排序
  • 选择排序
  • 遍历简单的2D数组
2020-07-28