「 每日一句 · Daily Quote 」学而不思则罔思而不学则殆。”— 《论语·为政》文章目录前言一、算法效率1.1 复杂度的概念二、时间复杂度1.概念介绍2. 大O的渐进表示法3. 时间复杂度计算示例3.1 示例13.2 示例23.3 示例33.4 示例43.5 示例53.6 示例63.7 示例7三、空间复杂度1.空间复杂度计算示例1.1 示例11.2 示例2四、常见复杂度对比总结前言数据结构与算法是程序员的必修内功而衡量算法优劣的核心指标便是时间复杂度与空间复杂度。本文将从算法效率的概念入手讲解大O渐进表示法的核心规则通过多个经典代码示例循环、冒泡排序、二分查找、阶乘递归等逐步推导时间复杂度的计算方法并进一步分析空间复杂度的评估方式最后对比常见复杂度的增长趋势。掌握复杂度分析你就能理性评估算法性能写出更高效的代码。一、算法效率1.1 复杂度的概念算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。二、时间复杂度1.概念介绍定义在计算机科学中算法的时间复杂度是一个函数式T(N)它定量描述了该算法的运行时间。那么问题就来了,时间复杂度是衡量程序的时间效率那么为什么不去计算程序的运行时间呢因为程序运行时间和编译环境和运行机器的配置都有关系比如同一个算法程序用一个老编译器进行编译和新编译器编译在同样机器下运行时间不同。同一个算法程序用一个老低配置机器和新高配置机器运行时间也不同。并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。那么算法的时间复杂度是一个函数式T(N)到底是什么呢这个T(N)函数式计算了程序的执行次数。也就是说,我们计算T(N),实际是在计算一个程序的执行次数通过c语言编译链接章节学习我们知道算法程序被编译后生成二进制指令程序运行就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)假设每句指令执行时间基本一样(实际中有差别但是微乎其微)那么执行次数和运行时间就是等比正相关这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣.比如解决一个问题的算法a程序T(N) N算法b程序T(N) N^2那么算法a的效率一定优于算法b。// 请计算一下Func1中count语句总共执行了多少次voidFunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}for(intk0;k2*N;k){count;}intM10;while(M--){count;}}Func1执行的基本操作次数T ( N ) N 2 2 ∗ N 10 T(N) N^2 2 * N 10T(N)N22∗N10分析:这里有两层for循环执行了N^2次for(inti0;iN;i){for(intj0;jN;j){count;}}这里有一层for循环,执行了N次for(intk0;k2*N;k){count;}这里执行了十次intM10;while(M--){count;}所以总的执行次数T(N)是T ( N ) N 2 2 ∗ N 10 T(N) N^2 2 * N 10T(N)N22∗N10这里我们发现,通过对N取值的分析,对结果影响最大的一项是N^2实际中我们计算时间复杂度时计算的也不是程序的精确的执行次数,因为我们计算时间复杂度只是想比较算法程序的增长量级也就是当N不断变大时T(N)的差别,上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小所以我们只需要计算程序能代表增长量级的大概执行次数复杂度的表示通常使用大O的渐进表示法。2. 大O的渐进表示法大O符号Big O notation是用于描述函数渐进行为的数学符号大O记法的核心规则只保留最高阶项去掉低阶项. 比如T(N) N^3 2N^2 1,那就记为O(N^3).如果最高阶项存在且系数不是1则去除这个项的常数系数.比如,T(N)5N,那么掉系数5,记为O(N).常数项记为1.T(N)中如果没有N相关的项只有常数项用常数1取代所有加法常数.通过以上方法可以得到Func1的时间复杂度为O ( N 2 ) O(N^2)O(N2)3. 时间复杂度计算示例3.1 示例1// 计算Func2的时间复杂度voidFunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while(M--){count;}printf(%d\n,count);}Func2执行的基本操作次数T ( N ) 2 N 10 T (N) 2N 10T(N)2N10有一层for循环,执行了2N次.还有一个whlie循环,执行了10次.Func2的时间复杂度为O(N)3.2 示例2// 计算Func3的时间复杂度voidFunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}printf(%d\n,count);}Func3执行的基本操作次数T ( N ) M N T (N) M NT(N)MN第一个for循环执行了M次,第二个for循环执行了N次因此Func2的时间复杂度为O(N)3.3 示例3// 计算Func4的时间复杂度voidFunc4(intN){intcount0;for(intk0;k100;k){count;}printf(%d\n,count);}Func4执行的基本操作次数T ( N ) 100 T(N) 100T(N)100根据推到规则3可知Func4的时间复杂度为: O(1)3.4 示例4// 计算strchr的时间复杂度constchar*strchr(constchar*str,intcharacter){constchar*p_begins;while(*p_begin!character){if(*p_begin\0)returnNULL;p_begin;}returnp_begin;}strchr执行的基本操作次数若要查找的字符在字符串第一个位置则T (N) 1若要查找的字符在字符串最后的一个位置则T(N) N若要查找的字符在字符串中间位置则T (N) N / 2因此strchr的时间复杂度分为最好情况 : O(1)最坏情况 : O(N)平均情况 : O(N)通过上⾯我们会发现有些算法的时间复杂度存在最好、平均和最坏情况。最坏情况任意输入规模的最大运行次数(上界)平均情况任意输入规模的期望运行次数最好情况任意输入规模的最小运行次数(下界)大O的渐进表示法在实际中一般情况关注的是算法的上界也就是最坏运行情况。3.5 示例5// 计算BubbleSort的时间复杂度voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}BubbleSort执行的基本操作次数这是一个经典的冒泡排序, T(N)有以下几种情况:若数组有序,则:T ( N ) N T(N) NT(N)N若数组有序且为降序,则:T ( N ) N ∗ ( N 1 ) 2 T(N) \frac{N * (N 1)}{2}T(N)2N∗(N1)​若要查找的字符在字符串中间位置则N T ( N ) N ∗ ( N 1 ) 2 N T(N) \frac{N * (N 1)}{2}NT(N)2N∗(N1)​因此BubbleSort的时间复杂度取最差情况为O ( N 2 ) O(N^2)O(N2)3.6 示例6voidfunc5(intn){intcnt1;while(cntn){cnt*2;}}这里我们想要知道T(N)[执行次数],关键在cnt * 2和cnt n这两个公式上,也就是2 T ( N ) 2^{T(N)}2T(N)n,所以执行次数T(N)log ⁡ 2 n \log_2 nlog2​n.因此func5的时间复杂度取最差情况为O ( log ⁡ 2 n ) O(\log_2 n)O(log2​n)注意课件中和书籍中log ⁡ 2 n \log_2 nlog2​n、log ⁡ n \log nlogn、lg ⁡ n \lg nlgn的表示当 n 接近无穷大时底数的大小对结果影响不大。因此一般情况下不管底数是多少都可以省略不写即可以表示为log ⁡ n \log nlogn不同书籍的表示方式不同以上写法差别不大建议使用log ⁡ n \log nlogn3.7 示例7// 计算阶乘递归Fac的时间复杂度longlongFac(size_tN){if(0N)return1;returnFac(N-1)*N;}调用一次Fac函数的时间复杂度为O(1)而在Fac函数中存在n次递归调用Fac函数因此:阶乘递归的时间复杂度为O(n)三、空间复杂度空间复杂度也是一个数学表达式是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占用了多少bytes的空间因为常规情况每个对象大小差异不会很大所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定1.空间复杂度计算示例1.1 示例1// 计算BubbleSort的时间复杂度voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}函数栈帧在编译期间已经确定好了只需要关注函数在运行时额外申请的空间。BubbleSort额外申请的空间有exchange等有限个局部变量使用了常数个额外空间因此空间复杂度为O(1)1.2 示例2// 计算阶乘递归Fac的空间复杂度longlongFac(size_tN){if(N0)return1;returnFac(N-1)*N;}Fac递归调用了N次额外开辟了N个函数栈帧每个栈帧使用了常数个空间因此空间复杂度为O(N)四、常见复杂度对比常见函数增长率对照表 常见函数增长率对照表常见函数增长率对照表算法时间复杂度比较图 算法时间复杂度比较图算法时间复杂度比较图总结以上就是本篇博客的核心内容。我们学习了算法效率的衡量维度——时间复杂度和空间复杂度掌握了用大O渐进表示法保留最高阶、去除常数系数评估算法性能的方法并通过多个示例如冒泡排序O(N²)、二分查找O(logN)、阶乘递归O(N)进行了实战推导。空间复杂度则关注算法运行过程中额外开辟的空间。复杂度分析是数据结构与算法学习的基石它能帮助我们在设计程序时做出更优的决策。