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

简介: 由数据范围反推算法复杂度以及算法内容

文章目录



一、由数据范围反推算法复杂度以及算法内容


一般 ACM 或者笔试题的时间限制是 1s 或 2s。

在这种情况下,C++ 代码中的操作次数控制在 107∼108 为最佳。

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

(1) n ≤ 30 => 指数级别 => dfs + 剪枝,状态压缩 DP。

(2) n ≤ 100 => O(n3) => Floyd,DP,高斯消元。

(3) n ≤ 1000 => O(n2),O(n2logn) => DP,二分,朴素版 Dijkstra、朴素版 Prim、Bellman-Ford。

(4) n ≤ 10000 => O(n∗√n) => 块状链表、分块、莫队。

(5) n ≤ 100000 => O(nlogn) => 各种 sort,线段树、树状数组、set / map、heap、拓扑排序、Dijkstra + heap、Prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树。

(6) n ≤ 1000000 => O(n),以及常数较小的 O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集、KMP、AC自动机;常数比较小的 O(nlogn) 的做法:sort、树状数组、heap、Dijkstra、spfa。

(7) n ≤ 10000000 => O(n) => 双指针扫描、KMP、AC 自动机、线性筛素数。

(8) n ≤ 109 => O(n√) => 判断质数。

(9) n ≤ 1018 => O(logn) => 最大公约数,快速幂,数位 DP。

(10) n ≤ 101000 => O((logn)2) => 高精度加减乘除。

(11) n ≤ 10100000 => O(logk×loglogk) => k 表示位数,高精度加减、FFT / NTT。


二、数据范围


3.png


  • long long 内的最大阶乘20!
  • int 内的最大阶乘12!



三、其他知识点

1. long 和 int 的大小跟系统位数有关

系统位数 long 和 int 的大小
16位系统 long 是 4 字节,int 是 2 字节
32位系统 long 是 4 字节,int 是 4 字节
64位系统 long 是 8 字节,int 是 4 字节


2. memset 常用赋值


  • 头文件 <cstring>
  • memset(f, 0, sizeof(f));
  • (1) 0
  • (2) -1
  • (3) 0x3f(正无穷 1,061,109,567)
  • (4) -0x3f(负无穷 -1,044,266,559)


















相关文章
|
29天前
|
存储 编解码 负载均衡
数据分片算法
【10月更文挑战第25天】不同的数据分片算法适用于不同的应用场景和数据特点,在实际应用中,需要根据具体的业务需求、数据分布情况、系统性能要求等因素综合考虑,选择合适的数据分片算法,以实现数据的高效存储、查询和处理。
|
29天前
|
存储 缓存 算法
分布式缓存有哪些常用的数据分片算法?
【10月更文挑战第25天】在实际应用中,需要根据具体的业务需求、数据特征以及系统的可扩展性要求等因素综合考虑,选择合适的数据分片算法,以实现分布式缓存的高效运行和数据的合理分布。
|
2月前
|
机器学习/深度学习 人工智能 算法
"拥抱AI规模化浪潮:从数据到算法,解锁未来无限可能,你准备好迎接这场技术革命了吗?"
【10月更文挑战第14天】本文探讨了AI规模化的重要性和挑战,涵盖数据、算法、算力和应用场景等方面。通过使用Python和TensorFlow的示例代码,展示了如何训练并应用一个基本的AI模型进行图像分类,强调了AI规模化在各行业的广泛应用前景。
32 5
|
1月前
|
存储 JSON 算法
TDengine 检测数据最佳压缩算法工具,助你一键找出最优压缩方案
在使用 TDengine 存储时序数据时,压缩数据以节省磁盘空间是至关重要的。TDengine 支持用户根据自身数据特性灵活指定压缩算法,从而实现更高效的存储。然而,如何选择最合适的压缩算法,才能最大限度地降低存储开销?为了解决这一问题,我们特别推出了一个实用工具,帮助用户快速判断并选择最适合其数据特征的压缩算法。
38 0
|
2月前
|
人工智能 算法 前端开发
无界批发零售定义及无界AI算法,打破传统壁垒,累积数据流量
“无界批发与零售”是一种结合了批发与零售的商业模式,通过后端逻辑、数据库设计和前端用户界面实现。该模式支持用户注册、登录、商品管理、订单处理、批发与零售功能,并根据用户行为计算信用等级,确保交易安全与高效。
|
2月前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
2月前
|
机器学习/深度学习 算法 数据处理
EM算法对人脸数据降维(机器学习作业06)
本文介绍了使用EM算法对人脸数据进行降维的机器学习作业。首先通过加载ORL人脸数据库,然后分别应用SVD_PCA、MLE_PCA及EM_PCA三种方法实现数据降维,并输出降维后的数据形状。此作业展示了不同PCA变种在人脸数据处理中的应用效果。
35 0
|
2月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
2天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。