个人主页 流年如梦专栏 《C语言》 《数据结构》文章目录一.数据结构与算法基础二.算法效率与复杂度概念三.时间复杂度3.1定义3.2大O渐进表示法3.3最好、最坏、平均情况3.4举例3.4.1 双层循环 O(N²) 3.4.2 单层循环 O(N) 3.4.3 两个独立变量 O(MN) 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²2N10根据大O渐进表示法我们得知它的时间复杂度为O(N²)3.3最好、最坏、平均情况最好情况最少执行次数下界最坏情况最多执行次数上界平均情况期望次数注意❗复杂度默认取最坏情况3.4举例3.4.1 双层循环 O(N²) voidFunc1(intN){intcount0;for(inti0;iN;i)for(intj0;jN;j)count;for(intk0;k2*N;k)count;intM10;while(M--)count;}分析执行次数为T(N) N²2N10所以时间复杂度为O(N²)大O渐进表示法3.4.2 单层循环 O(N) voidFunc2(intN){for(intk0;k2*N;k)count;while(10--)count;}分析T(N)2N10时间复杂度为O(N)大O渐进表示法3.4.3 两个独立变量 O(MN) voidFunc3(intN,intM){for(intk0;kM;k);for(intk0;kN;k);}分析T(N)MN所以时间复杂度为O(MN)3.4.4 常数次 O(1) voidFunc4(intN){for(intk0;k100;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(intendn;end0;end--){intexchange0;for(inti1;iend;i){if(a[i-1]a[i]){swap(ai-1,ai);exchange1;}}if(exchange0)break;}}分析分两种情况如果是乱序即最坏情况则时间复杂度为O(N²)如果是已排序即最好情况则时间复杂度为O(N)一遍就行3.4.7 倍数增长 O(logN) voidfunc5(intn){intcnt1;while(cntn)cnt*2;}分析其中执行次数 x2ˣN--xlog₂N所以时间复杂度为O(logN)3.4.8 阶乘递归 O(N) longlongFac(size_tN){if(N0)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(N0)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--){intendnums[len-1];for(intilen-1;i0;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(inti0;ilen;i)tmp[(ik)%len]nums[i];for(inti0;ilen;i)nums[i]tmp[i];free(tmp);}分析时间复杂度为O(N)空间复杂度为O(N)相对于思路一它不会因为数据量大超时可行6.3方案三 -- 三次逆置最优方案voidreverse(int*nums,intbegin,intend){while(beginend){inttnums[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);}分析时间复杂度为O(N)空间复杂度为O(1)总结复杂度衡量时间快慢、空间大小时间复杂度看执行次数空间复杂度看额外开辟空间统一用大O渐进表示法只看最高阶算法默认取最坏复杂度复杂度从优到劣O(1)O(logN)O(N)O(NlogN)O(N²)…旋转数组最优三次逆置O(N)时间 O(1)空间⚠️易错点计算复杂度时保留低阶项或系数递归复杂度不会算看递归深度logN复杂度判断错误混淆时间或者空间复杂度暴力算法超时不会优化 关注我们一路同行从入门到大师慢慢沉淀、稳步成长❤️ 点赞鼓励原创让优质内容被更多人看见⭐ 收藏收好核心知识点与实战技巧需要时随时查阅 评论分享你的疑问或踩坑经历一起交流避坑、共同进步