由数据范围反推算法复杂度及算法种类

本文主要是介绍由数据范围反推算法复杂度及算法种类，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一般OJ的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 10^7 ∼ 10^8为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

• n <= 12
  算法复杂度：n!
  一般算法：暴力dfs

• n <= 30
  算法复杂度：2^n
  一般算法: dfs+剪枝，状态压缩dp

• n <= 100
  算法复杂度：O(n^3)
  一般算法: floyd，dp，高斯消元

• n <= 1000
  算法复杂度：O(n^2), O(n^2logn)
  一般算法：二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford，冒泡， dp

• n <= 10000
  算法复杂度：O(n * n^(1/2))
  常见算法：块状链表、分块、莫队

• n <= 100000 (10^5重要)
  算法复杂度：O(nlogn)
  常见算法：各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树

• n <= 1000000
  算法复杂度： O(n), 以及常数较小的 O(nlogn)
  常见算法：单调队列、 hash、双指针扫描、并查集，kmp、AC自动机
  常数比较小的 O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa

• n <= 10000000
  算法复杂度：O(n)
  常见算法：双指针扫描、kmp、AC自动机、线性筛素数

• n<= 10^9
  算法复杂度: O(n^(1/2))
  常见算法：判断质数

• n<=10^18
  算法复杂度：O(logn)
  常见算法：最大公约数，快速幂，数位DP

这篇关于由数据范围反推算法复杂度及算法种类的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！