时间复杂度的计算方法
2026-08-22 09:38:19
发布于：广东
11阅读
0回复
0点赞
## 一、计算的“四步法”
### 第1步:找出“基本操作”
找出程序中最内层、执行次数最多的那行代码(通常是赋值、比较、算术运算)。
### 第2步:计算执行次数
T(n)分析这行代码一共被执行了多少次，写出关于n的数学表达式。
### 第3步:取最高次项
只保留表达式中增长最快的那一项(最高次幂)。
### 第4步:去掉系数
将该项的常数系数变为1，最后得到的就是大O表示法。
## 二、按结构类型秒算复杂度(CSP-J核心考点)
### 1.顺序结构:直接相加(取最大)
// O(1)
int a = n + 1;
// O(n)
for(int i=0; i<n; i++){ sum++; }
// 总复杂度 = O(1) + O(n) = O(n)（忽略常数和低阶项）
2.单层循环:看"步长”
规律:循环次数=(终值-初值)/步长。
for(i=1;i<=n;i++) 一 循环n次 一 0(n)
for(i=1;i<=n;i=i*2) (或i*=2) 一 循环log2n次 一 0(logn)
for(i=n;i>=1;i=i/2) — 同样循环log2n次 — 0(logn)
### CSP-J常考陷阱:
看到i*=2或i/=2，立刻反应出1ogn
3.双层循环:看“乘除关系”
·普通嵌套(外层n次，内层n次):总次数nxn=n2一0(n^2)
·内外有关联(如外层i=1~n，内层j=1~i):
总次数=1+2+3+...+n=n(n+1)/2最高次项是n^2/2,去掉系数0(n2)
外层n次，内层logn次:总次数n*logn一O(n*logn)(归并排序、快速排序的复杂度)
4.递归函数:画“递归树”或列"递推式”
CSP-J常考简单的递归，用递推式计算:
递推式T(n)=T(n-1)+O(1)(如单分支深度递归)一总共执行n层一0(n)
递推式T(n)=2T(n/2)+O(n)(如归并排序)一每层合并消耗O(n),共logn层0(n logn)
·递推式T(n)=2T(n-1)(如指数级枚举)一O(2^n)
三、结合2020年CSP-J真题实战演练
例1:阅读程序题(进制进位)
int d[10], ans=0;
for(inti=0;i<n;i++){ //外层循环n次
int p= 0;d[p]++;while(d[p] == k){d[p] - 0;p++;d[p]++;ans++;
//内层进位
计算:外层固定是n次。内层while总共发生多少次进位?一共加了n次1，每次进位最多波及l0g%.n位，但摊还分析下总进位次数约为n次。
答案:整体复杂度为0(n)。
例2:完善程序题(质因数分解)
for(int i=2;i*i<=n;it+){ //注意这里是*<=nwhile(n % i == 0){//分解操作n=n/i;
计算:外层for循环，因为条件i*i<=n，当n很大时，i最多遍历到√n。
答案:时间复杂度为0(Vn)(根号n)。
四、避坑指南(CSP-J高频失分点)
1.别把常数当回事 3n、100n、n/2 统统写成 0(n) ;1000 写成0(1)。
2.break和return的影响 虽然循环写的是n次，但如果中间有break提前结束，最好情况是O(1),但时间复杂度默认指“最坏情况”，所以仍算O(n)。
3.注意输入数据的改变 像上面质因数分解中，n在不断变小，所以不能简单认为外层是n次，而是√n.
4.多个变量 如果算法依赖两个输入规模(如n和m)，要写O(n+m)或O(nxm),不能丟项。
总结一句话:
拿到代码后，盯住最深层的循环体，计算它跑的次数:
加法变乘法(嵌套)，步长看乘除(log)，取大舍小(最高次)，常数去掉(0表示)
有帮助，赞一个