应粉丝要求出本期一、为什么需要时间复杂度？摘要：应粉丝要求出本期一、为什么需要时间复杂度？1.1 程序性能的度量问题：如何衡量不同算法的效率？// 示例1：求1+2+...+nintsum1(int n){ // 时间复杂度 O(n)int total = 0;for(int i=1; i
1.1 程序性能的度量
问题：如何衡量不同算法的效率？// 示例1：求1+2+...+nintsum1(int n){ // 时间复杂度 O(n)
int total = 0;
for(int i=1; i<=n; i++)
total += i;
return total;
}
intsum2(int n){ // 时间复杂度 O(1)
return n*(n+1)/2;
}
结论：sum2 比 sum1 更高效（尤其当n很大时）
1.2 时间复杂度的定义
定义：算法执行时间随输入规模增长的增长率特点：关注最坏情况下的时间消耗忽略常数项和低阶项（关注增长趋势）使用大O表示法（如 O(n²)）二、大O表示法核心规则2.1 常见时间复杂度
2.2 计算步骤
确定输入规模（n）统计基本操作的执行次数保留最高阶项，去掉系数示例：
for(int i=0; i}
// 总次数：n*n = n² → O(n²)
三、C++代码复杂度分析
3.1 典型代码模式
1. 单循环
for(int i=0; i}
2. 双重循环
for(int i=0; i}
}
3. 递归
intfactorial(int n){ // O(n)if(n <= 1) return1;
return n * factorial(n-1);
}
3.2 复杂度陷阱
错误示例：
// 计算斐波那契数列（低效版）intfib(int n){ // O(2ⁿ)
if(n <= 1) return n;
return fib(n-1) + fib(n-2);
}
优化方案：
intfib(int n){ // O(n)int a = 0, b = 1;
for(int i=2; i<=n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
四、复杂度对比实验
4.1 不同复杂度的增长趋势
4.2 实际运行时间对比
#include#include
usingnamespacestd;
// O(n) 算法
voidlinear(int n){
for(int i=0; i
// O(n²) 算法
voidquadratic(int n){
for(int i=0; i
intmain{
int n = 10000;
auto start = chrono::high_resolution_clock::now;
linear(n);
auto end = chrono::high_resolution_clock::now;
cout << "O(n) 耗时："
(end - start).count
<< " ms" << endl;
quadratic(n);
cout << "O(n²) 耗时："
<< " ms" << endl;
}
输出示例：
O(n) 耗时：0 msO(n²) 耗时：45 ms
五、复杂度优化技巧
5.1 优化策略
减少嵌套循环：用数学公式替代多重循环提前终止：利用break/continue减少不必要的循环空间换时间：使用哈希表（O(1)查找）算法选择：优先选择低复杂度算法（如快速排序 vs 冒泡排序）5.2 案例分析
问题：查找数组中是否存在重复元素
低效方案：
for(int i=0; i
returnfalse;
}
优化方案：
boolcontainsDuplicate(vector& nums){ // O(n)unordered_set s;
for(int num : nums) {
if(s.count(num)) returntrue;
s.insert(num);
}
returnfalse;
}
六、实战练习
6.1 基础题
题目：分析以下代码的时间复杂度
for(int i=0; i}
}
答案：O(n²)（等差数列求和：1+2+...+n-1 = n(n-1)/2）
6.2 进阶题
题目：优化以下代码的复杂度
// 原始版本：O(n³)intcountTriplets(vector& arr){
int count = 0;
for(int i=0; i
count++;
return count;
}
优化思路：
先排序（O(n log n)）固定第一个元素，双指针查找后两个元素（O(n²)）七、复杂度速查表来源：老胡侃侃说
