当前位置：首页 > news >正文

算法效率：复杂度原理解析

news 2026/4/28 18:53:01

个人主页：流年如梦

专栏：《C语言》《数据结构》

文章目录

一.数据结构与算法基础
二.算法效率与复杂度概念
三.时间复杂度
- 3.1定义
- 3.2大O渐进表示法
- 3.3最好、最坏、平均情况
- 3.4举例
- - 3.4.1 双层循环（ O(N²) ）
  - 3.4.2 单层循环（ O(N) ）
  - 3.4.3 两个独立变量（ O(M+N) ）
  - 3.4.4 常数次（ O(1) ）
  - 3.4.5 查找字符（ O(N) ）
  - 3.4.6 冒泡排序（ O(N²) 或 O(N) ）
  - 3.4.7 倍数增长（ O(logN) ）
  - 3.4.8 阶乘递归（ O(N) ）
四.空间复杂度
- 4.1定义
- 4.2举例
- - 4.2.1 冒泡排序
  - 4.2.2 阶乘递归
五.常见复杂度对比
六.复杂度算法题 --> 旋转数组
- 6.1方案一 --> 逐次移动（暴力美学）
- 6.2方案二 --> 创建新的数组
- 6.3方案三 --> 三次逆置（最优方案）
🎯总结
⚠️易错点

Ladies and gentlemen，本篇文章主要学的是时间复杂度、空间复杂度、大 O 表示法、复杂度计算与常见复杂度对比；全程高能，不容错过！！！

前言
算法复杂度是衡量算法快慢与耗内存的核心标准。不计算精确时间与空间，而是用大O渐进表示法估算增长趋势，用来在编码前就判断算法优劣，写出高效代码

一.数据结构与算法基础

数据结构：
数据结构是计算机存储、组织数据的方式，是数据元素之间的关系集合；常见的有顺序表、链表、栈、队列、二叉树、哈希表等

算法：
算法是一系列计算步骤，把输入转化为输出（为了效率高、资源省、逻辑清晰）

重要性：写出高效程序的基础；决定程序在大数据量下是否能跑；对今后的笔试和面试有着重要作用

二.算法效率与复杂度概念

衡量算法好坏主要看时间复杂度和空间复杂度：

时间复杂度--> 衡量算法运行快慢
空间复杂度--> 衡量算法额外占用内存

三.时间复杂度

3.1定义

时间复杂度是描述算法执行次数与数据规模N的函数关系，用大O表示法表示

不算真实运行时间（受机器或编译器影响），只算执行次数的增长趋势

3.2大O渐进表示法

只保留最高阶项
最高阶系数去掉
常数复杂度统一写O(1)

例如后面举例的双层循环：

其中执行次数为T(N) = N²+2N+10，根据大O渐进表示法我们得知它的时间复杂度为O(N²)

3.3最好、最坏、平均情况

最好情况：最少执行次数（下界）
最坏情况：最多执行次数（上界）
平均情况：期望次数

注意❗：复杂度默认取最坏情况

3.4举例

3.4.1 双层循环（ O(N²) ）

voidFunc1(intN){intcount=0;for(inti=0;i<N;i++)for(intj=0;j<N;j++)count++;for(intk=0;k<2*N;k++)count++;intM=10;while(M--)count++;}

🧐分析：执行次数为T(N) =N²+2N+10，所以时间复杂度为O(N²)（大O渐进表示法）

3.4.2 单层循环（ O(N) ）

voidFunc2(intN){for(intk=0;k<2*N;k++)count++;while(10--)count++;}

🧐分析：T(N)=2N+10，时间复杂度为O(N)（大O渐进表示法）

3.4.3 两个独立变量（ O(M+N) ）

voidFunc3(intN,intM){for(intk=0;k<M;k++);for(intk=0;k<N;k++);}

🧐分析：T(N)=M+N，所以时间复杂度为O(M+N)

3.4.4 常数次（ O(1) ）

voidFunc4(intN){for(intk=0;k<100;k++);}

🧐分析：执行次数固定，时间复杂度为O(1)

3.4.5 查找字符（ O(N) ）

constchar*strchr(constchar*str,intc){while(*str&&*str!=c)str++;returnstr;}

🧐分析：最好情况时时间复杂度为O(1)；最坏情况与平均情况的时间复杂度一样，为O(N)

3.4.6 冒泡排序（ O(N²) 或 O(N) ）

voidBubbleSort(int*a,intn){for(intend=n;end>0;end--){intexchange=0;for(inti=1;i<end;i++){if(a[i-1]>a[i]){swap(a+i-1,a+i);exchange=1;}}if(exchange==0)break;}}

🧐分析：分两种情况，如果是乱序（即最坏情况），则时间复杂度为O(N²)；如果是已排序（即最好情况），则时间复杂度为O(N)，一遍就行

3.4.7 倍数增长（ O(logN) ）

voidfunc5(intn){intcnt=1;while(cnt<n)cnt*=2;}

🧐分析：其中执行次数 x：2ˣ=N-->x=log₂N，所以时间复杂度为O(logN)

3.4.8 阶乘递归（ O(N) ）

longlongFac(size_tN){if(N==0)return1;returnFac(N-1)*N;}

🧐分析：递归N次，时间复杂度为O(N)

四.空间复杂度

4.1定义

空间复杂度衡量算法额外开辟的临时空间，不算输入输出本身占用的空间，同样与时间复杂度使用大O表示法

4.2举例

4.2.1 冒泡排序

voidBubbleSort(...){intexchange;}

🧐分析：因为只开辟常数个变量，所以空间复杂度为O(1)

4.2.2 阶乘递归

longlongFac(size_tN){if(N==0)return1;returnFac(N-1)*N;}

🧐分析：因为递归调用N层栈帧，所以空间复杂度为O(N)

五.常见复杂度对比

如下表格👇：

从快到慢依次为	复杂度
常数	`O(1)`
对数	`O(logN)`
线性	`O(N)`
线性对数	`O(NlogN)`
平方	`O(N²)`
立方	`O(N³)`
指数	`O(2ⁿ)`
阶乘	`O(N!)`

下面为时间复杂度对比曲线图👇：

六.复杂度算法题 --> 旋转数组

转跳力扣👉LeetCode 189：旋转数组

原题：

6.1方案一 --> 逐次移动（暴力美学）

voidrotate(int*nums,intlen,intk){while(k--){intend=nums[len-1];for(inti=len-1;i>0;i--)nums[i]=nums[i-1];nums[0]=end;}}

提交结果：

🧐分析：时间复杂度为O(N×K)即O(N²)，空间复杂度为O(1)；但缺点是数据量大超时

6.2方案二 --> 创建新的数组

voidrotate(int*nums,intlen,intk){int*tmp=(int*)malloc(len*sizeof(int));for(inti=0;i<len;i++)tmp[(i+k)%len]=nums[i];for(inti=0;i<len;i++)nums[i]=tmp[i];free(tmp);}

🧐分析：时间复杂度为O(N)，空间复杂度为O(N)；相对于思路一它不会因为数据量大超时，可行

6.3方案三 --> 三次逆置（最优方案）

voidreverse(int*nums,intbegin,intend){while(begin<end){intt=nums[begin];nums[begin]=nums[end];nums[end]=t;begin++;end--;}}voidrotate(int*nums,intlen,intk){k%=len;reverse(nums,0,len-k-1);reverse(nums,len-k,len-1);reverse(nums,0,len-1);}