【转载】由数据范围反推算法复杂度以及算法内容

2023-01-11 / 0 评论 / 0 点赞 / 635 阅读 / 523 字

01/11

温馨提示：

本文最后更新于 2023-01-13，若内容或图片失效，请留言反馈。部分素材来自网络，若不小心影响到您的利益，请联系我们删除。

本文原作者：yxc

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 $10^7\sim10^8$ 为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

数据范围	时间复杂度	算法选择
$n \le 30$	指数级别	DFS+剪枝、状态压缩DP
$n\le100$	$O(n^3)$	Floyd、DP、高斯消元
$n\le1000$	$O(n^2)、O(n^2\log{n})$	DP、二分、朴素版Dijkstra、朴素版Prim、Bellman-Ford
$n\le10000$	$O(n\sqrt{n})$	块状链表、分块、莫队
$n\le100000(10^5)$	$O(n\log{n})$	各种Sort、线段树、树状数组、Set/Map、Heap、拓扑排序、堆优化版Dijkstra、堆优化版Prim、Kruskal、SPFA、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
$n\le1000000(10^6)$	$O(n)$ 常数较小的 $O(n\log{n})$	单调队列、Hash、双指针扫描、并查集，kmp、AC自动机 Sort、树状数组、Heap、Dijkstra、SPFA
$n\le10000000(10^7)$	$O(n)$	双指针扫描、KMP、AC自动机、线性筛素数
$n\le10^9$	$O(\sqrt{n})$	判断质数
$n\le10^{18}$	$O(\log{n})$	最大公约数、快速幂、数位DP
$n\le10^{1000}$	$O((\log{n})^2)$	高精度加减乘除
$n\le 10^{100000}$	$O(\log{k} \cdot \log{\log{k}})$ , $k$ 表示位数	高精度加减、FFT/NTT

评论区