由数据范围反推算法时间复杂度

本文主要是介绍由数据范围反推算法时间复杂度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AcWing算法基础课 算法时间复杂度分析笔记

---

系列文章目录

常用算法代码模板 (1) ：基础算法
常用算法代码模板 (2) ：数据结构
常用算法代码模板 (3) ：搜索与图论
常用算法代码模板 (4) ：数学知识
算法基础课 动态规划模板题笔记
算法基础课 贪心算法模板题笔记

---

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

数据范围	时间复杂度	算法
$n\le 30$	指数级别	dfs+剪枝、状态压缩dp
$n\le 100$	$O(n^3)$	floyd、dp、高斯消元
$n\le 1000$	$O(n^2),O(n^2\log n)$	dp、二分、朴素dijkstra、朴素prim、Bellman-Ford
$n\le 10000$	$O(n\sqrt{n})$	块状链表、分块
$n\le 100000$	$O(n\log n)$	sort、线段树、树状数组、set/map、heap、dijkstra+heap、spfa
$n\le 1000000$	$O(n)$ 常数比较小的 $O(n\log n)$	单调队列、hash、双指针、bfs、并查集、kmp、AC自动机 sort、树状数组、heap、dijkstra+heap、spfa
$n\le 10^7$	$O(n)$	双指针、kmp、AC自动机、线性筛素数
$n\le 10^9$	$O(\sqrt{n})$	判断质数
$n\le 10^{18}$	$O(\log n)$	欧几里得算法、快速幂、数位dp

这篇关于由数据范围反推算法时间复杂度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---