根据题目的时间复杂度反推可能的算法

有时候,我们可以根据算法题目的可能时间复杂度来反推出用来解决该问题的对应算法。比如,我们需要用O(logn), O(n),O(nlogn)的复杂度来解决某道题,那么我们应该想到哪些可能可以用的算法?

这里总结了常见的时间复杂度对应的常用算法。

O(1)

一般都是数学方法或者找规律直接求解的方法

O(logn)

二分法或者位运算

O(√n)

几乎是分解质因数

O(n)

在面试题里高频出现。一般都是循环一遍得到解,简单的链表或者数组的题大都是O(n),

可能的算法有:

  1. 枚举
  2. 一维状态的动态规划
  3. 树,图的遍历算法,包括并查集
  4. 可能用到栈和队列这些数据结构
  5. 使用hash优化检索复杂度
  6. 双个指针遍历问题 (two-pointers)
  7. 贪心

O(nlogn)

  1. 排序,可能数据排序以后可以很容易解决
  2. 可能用到优先队列,比如用到堆
  3. 多次二分检索的问题
  4. 分治算法
  5. 可能用到线段树或者其他的高级数据结构

O(n^2)

该复杂度的算法一般就是两重循环

  1. 动态规划
  2. 枚举
  3. 数组

O(n^3)

  1. 动态规划
  2. 枚举
  3. 数组

O(a^n)、O(n!)等等非多项式复杂度(non-deterministic polynomial  NP)

  1. 搜索算法,包括回溯等等
  2. 状态压缩的动态规划问题
  3. 组合O(2^n)
  4. 排列O(n!)

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注