侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-01-11 / 0 评论 / 0 点赞 / 599 阅读 / 523 字
温馨提示:
本文最后更新于 2023-01-13,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
本文原作者:yxc

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

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

评论区