时间复杂度
yiyuhang123 · · 算法·理论
时间复杂度速查表（基于现代CPU 1s算力）
数据规模 (n) 可接受复杂度 典型算法与应用场景 理论计算量参考 (1s)
案例研究：区间最大和问题（洛谷P5745）
问题描述：在长度为n的数列中寻找和不超过M的最大连续子区间。
解法演进与性能对比
1. 暴力法（O(n³)）
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=i;k<=j;k++)
sum += a[k];-
适用场景：仅
n≤100 -
性能缺陷：
n=3000 时计算量达2.7×10⁹
2. 前缀和（O(n²)）
for(int i=1;i<=n;i++) s[i] = s[i-1]+a[i];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
sum = s[j]-s[i-1];-
优化点：消除最内层循环
-
瓶颈：
n=10⁴ 时计算量10⁸
3. 二分法（O(nlogn)）
for(int i=1;i<=n;i++){
int j = upper_bound(s+i,s+n+1,s[i-1]+M)-s-1;
sum = s[j]-s[i-1];
}-
关键技巧：利用前缀和单调性
-
实测性能：
n=10⁵ 仅需16ms
4. 滑动窗口法（O(n)）
int l=1, r=1;
while(l<=n){
while(r<=n && sum+a[r]<=M) sum+=a[r++];
update_answer();
sum-=a[l++];
}-
算法优势：单次线性扫描
-
极限测试：
n=4×10⁶ 仅162ms （快读优化）
性能对比表格
解法\hspace{0.35cm} 3000数据\hspace{0.35cm} 10⁴数据\hspace{0.35cm} 10⁵数据\hspace{0.35cm} 4×10⁶数据
竞赛优化技巧
IO优化模板
inline int read(){
int x=0; char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}效果对比
- cin版：
n=4×10⁶ 耗时893ms - 快读版：同数据
162ms 近似算法示例（模拟退火）
double T=1e5, d=0.9995; while(T>1e-4){ int new_ans = random_modify(); if(exp((new_ans-now)/T) > rand()) update(); T *= d; }竞赛实战建议
- 树退化成链：改用线性DP
- 完全图：使用贪心算法
- 大数据小范围：考虑桶排序
复杂度预判 编码前估算最大数据量下的计算次数
- 20%小数据 保证暴力分
- 30%特殊数据 针对性优化
避免vector<bool>，减少模运算
备用方案：准备随机化算法，编写部分分特判
可视化工具推荐： Desmos复杂度分析
尾
可直观比较不同算法在n增长时的表现差异
通过系统性的复杂度分析和渐进式优化，可以在竞赛中高效稳定地获得高分。建议在训练时建立自己的"时间复杂度-算法"映射表，提升解题效率。