热门

最新

红包

立Flag

投票

同城

发布
weixin_45920495
秋名山码民
4 年前
trueweixin_45920495

一般 ACMACM ,NOI(CSP)NOI(CSP)或者笔试题的时间限制是11秒或22秒。
在这种情况下，C++代码中的操作次数控制在10，7为最佳。

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

n≤30n≤30, 指数级别, dfs+剪枝，状态压缩dp
n≤100n≤100 => O(n3)O(n3)，floyd，dp
n≤1000n≤1000 => O(n2)O(n2)，O(n2log(n))O(n2log(n))，dp，二分
n≤10000n≤10000 => O(nn√)O(nn)，块状链表
n≤100000n≤100000 => O(nlog(n))O(nlog(n)) => 各种sort，线段树、树状数组、set/map、heap、dijkstra+heap、spfa、求凸包、求半平面交、二分
n≤1000000n≤1000000 => O(n)O(n), 以及常数较小的O(nlogn)O(nlogn)算法 => hash、双指针扫描、kmp、AC自动机，常数比较小的O(nlogn)O(nlogn)的做法：sort、树状数组、heap、dijkstra、spfa
n≤107n≤107 => O(n)O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n≤109n≤109 => O(√n)O(√n)，判断质数
n≤1018n≤1018 => O(logn)O(logn)，最大公约数
算法交流区
1
3
打赏
  • 复制链接
  • 举报
下一条：
👉 [2022-03-31]| CSDN每日推荐｜c/c++1.[麒麟系统开发笔记（二）：国产麒麟系统搭建Qt开发环境安装Qt5.12](https://blog.csdn.net/qq21497936/article/details/123840699?utm_source=702048761)[质量分：96；难度等级：初(关键词-安装)]摘要：开发国产应用，使用到银河麒麟V4，V10，本篇以V10记录，参照上一篇可安装V4、V7、V10三个版本，麒麟V4系自带了Qt，麒麟V10没有自带Qt，需要自己编译搭建环境。2.[【C++基础】三、类和对象（中篇）](https://blog.csdn.net/QIYICat/article/details/123837799?utm_source=702048761)[质量分：99；难度等级：初(关键词-基础)]摘要：https:https:https:https:https:https:https:https:https:https:https:https:https:https:https:https:https:https:https:https:https:3.[【C++】模板](https://blog.csdn.net/Suk_god/article/details/123804492?utm_source=702048761)[质量分：99；难度等级：初(置信度-99%)]摘要：以上就是对模板这块知识的总结归纳，感觉有所帮助的小伙伴们请留下你的足迹~~我们下期再见！https:https:https:https:https:https:https:https:https:https:https:https:https:更多请看：https://bbs.csdn.net/topics/605660469?utm_source=702048761