目录1. 时间复杂度和空间复杂度的定义及意义2. 时间复杂度2.1 时间复杂度的表达方法2.2 时间复杂度的计算2.3 从实例中理解时间复杂度3. 空间复杂度3.1 计算 BubbleSort 的空间复杂度3.2 计算 Fibonacci 的空间复杂度4. 总结与对比1. 时间复杂度和空间复杂度的定义及意义在计算机科学中算法是解决问题的核心。一个问题的解决方案最终会通过编写代码来实现。那么如何衡量一个算法的好坏呢答案就是通过计算它的时间复杂度和空间复杂度。时间复杂度简单理解就是代码运行所花费的时间。它反映了算法执行效率的高低。空间复杂度简单理解就是代码运行过程中所需要的额外内存空间。它反映了算法对存储资源的占用情况。毫无疑问在能够满足功能需求的前提下这两者都是越小越好。一个优秀的算法应当既快又省即在尽可能短的时间内完成任务同时占用尽可能少的额外内存。2. 时间复杂度2.1 时间复杂度的表达方法大O符号Big O notation是用于描述函数渐进行为的数学符号。它关注的是算法运行时间随输入规模增长的趋势而不是具体的执行次数。函数表达式时间复杂度阶数名称5201314O(1)常数阶3n4O(n)线性阶3n^24n5O(n^2)平方阶3log(2)n4O(logn)对数阶2n3nlog(2)n14O(nlogn)nlogn阶n32n24n6O(n^3)立方阶2^nO(2^n)指数阶 小贴士常见的复杂度从优到劣大致排序为O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n)。在实际开发中应尽量避免使用指数阶的算法。2.2 时间复杂度的计算时间复杂度的计算核心是算法中基本操作的执行次数即为算法的时间复杂度。我们需要找出基本操作的执行次数与输入规模 n 之间的函数关系然后只保留最高阶项、去掉系数。重点理解时间复杂度关注的是数量级而不是真的具体执行了多少次。计算的基本原则① 只关注最高阶项T ( n ) 3 n 2 4 n 5 ⇒ O ( n 2 ) T(n) 3n^2 4n 5 \Rightarrow O(n^2)T(n)3n24n5⇒O(n2)因为当 n 很大时n 2 n^2n2起主导作用其他项的影响可以忽略不计。② 忽略常数系数T ( n ) 100 n ⇒ O ( n ) T(n) 100n \Rightarrow O(n)T(n)100n⇒O(n)T ( n ) 5 ⇒ O ( 1 ) T(n) 5 \Rightarrow O(1)T(n)5⇒O(1)2.3 从实例中理解时间复杂度2.3.1 计算 strchr 的时间复杂度// strchr 模拟实现constchar*strchr(constchar*str,intcharacter){while(*str!\0){if(*strcharacter){returnstr;}str;}returnNULL;}假设数组 str 的长度为 N我们来分析不同情况下的比较次数情况说明比较次数复杂度最好情况目标字符就在字符串第一个位置1 次O ( 1 ) O(1)O(1)最坏情况目标字符在末尾或根本不存在N1 次O ( N ) O(N)O(N)平均情况目标字符随机分布约 N/2 次O ( N ) O(N)O(N)时间复杂度取最坏情况T ( n ) O ( N ) T(n) O(N)T(n)O(N) 小贴士在分析算法复杂度时我们通常关注最坏情况因为它保证了算法在任何输入下都不会超过这个时间上限。2.3.2 计算 BubbleSort 的时间复杂度// 冒泡排序voidbubble(int*a,intn){for(intendn;end0;--end){intflag0;for(inti0;in-1;i){if(a[i]a[i1]){swap(a[i],a[i1]);flag1;}}if(flag0)break;}}冒泡排序是循环的嵌套。外层循环end每次减一最坏情况下要执行 n-1 次内层循环i最坏情况下也要执行 n-1 次。因此总执行次数约为T ( n ) ( n − 1 ) ( n − 2 ) ⋯ 1 n ( n − 1 ) 2 ⇒ O ( n 2 ) T(n) (n-1) (n-2) \dots 1 \frac{n(n-1)}{2} \Rightarrow O(n^2)T(n)(n−1)(n−2)⋯12n(n−1)⇒O(n2)所以冒泡排序的时间复杂度为O ( n 2 ) O(n^2)O(n2)。2.3.3 计算 BinarySearch 的时间复杂度intbinarysearch(int*a,intn,intx){intbegin0;intendn-1;while(beginend){intmidbegin((end-begin)1);if(a[mid]x){beginmid1;}elseif(a[mid]x){endmid-1;}elsereturnmid;}return-1;}二分查找每次把查找区间缩小一半n → n 2 → n 4 → ⋯ → 1 n \rightarrow \frac{n}{2} \rightarrow \frac{n}{4} \rightarrow \dots \rightarrow 1n→2n→4n→⋯→1假设最多比较k kk次后区间缩小到 1n 2 k 1 \frac{n}{2^k} 12kn1解得k log 2 n k \log_2 nklog2n所以比较次数约为log 2 n \boldsymbol{\log_2 n}log2n即二分查找的时间复杂度为O ( log n ) O(\log n)O(logn)。 小贴士二分查找的效率非常高但前提是数组必须是有序的。这也是为什么很多算法会先排序再查找的原因。2.3.4 计算斐波那契递归 Fib 的时间复杂度longlongFib(size_tN){if(N3)return1;returnFib(N-1)Fib(N-2);}每个节点都分裂成两个子节点树的高度大约是 N节点数量呈指数增长。因此T ( n ) O ( 2 n ) T(n) O(2^n)T(n)O(2n)⚠️ 注意递归实现的斐波那契数列时间复杂度极高当 N 较大时如 N50计算量将非常庞大。实际开发中应改用循环或动态规划来实现。3. 空间复杂度空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少 bytes 的空间因为这个数值没有太大意义。空间复杂度计算的是变量的个数。空间复杂度的计算规则基本与时间复杂度类似也使用大O渐进表示法。注意函数运行时所需要的栈空间存储参数、局部变量、一些寄存器信息等在编译期间已经确定好了因此空间复杂度主要通过函数在运行时显式申请的额外空间来确定。3.1 计算 BubbleSort 的空间复杂度voidbubble(int*a,intn){for(intendn;end0;--end){intflag0;for(inti0;in-1;i){if(a[i]a[i1]){swap(a[i],a[i1]);flag1;}}if(flag0)break;}}分析只用了end、i、flag等几个固定变量没有额外数组没有递归调用。因此额外空间不随 n 增长空间复杂度为O ( 1 ) O(1)O(1)。3.2 计算 Fibonacci 的空间复杂度longlong*Fibonacci(size_tn){if(n0)returnNULL;longlong*fibArray(longlong*)malloc((n1)*sizeof(longlong));fibArray[0]0;fibArray[1]1;for(inti2;in;i){fibArray[i]fibArray[i-1]fibArray[i-2];}returnfibArray;}分析递归调用栈最深为 n 层每层栈帧占常数空间。所以总栈空间与 n 成正比空间复杂度为O ( n ) O(n)O(n)。4. 总结与对比算法时间复杂度空间复杂度strchr线性查找O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)冒泡排序O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)二分查找O ( log n ) O(\log n)O(logn)O ( 1 ) O(1)O(1)斐波那契递归O ( 2 n ) O(2^n)O(2n)O ( n ) O(n)O(n)斐波那契循环O ( n ) O(n)O(n)O ( n ) O(n)O(n) 核心要点时间复杂度关注的是数量级而非具体执行次数分析复杂度时通常取最坏情况空间复杂度计算的是额外变量的个数而非字节数递归算法往往以空间换时间需权衡使用。
目录1. 时间复杂度和空间复杂度的定义及意义2. 时间复杂度2.1 时间复杂度的表达方法2.2 时间复杂度的计算2.3 从实例中理解时间复杂度3. 空间复杂度3.1 计算 BubbleSort 的空间复杂度3.2 计算 Fibonacci 的空间复杂度4. 总结与对比1. 时间复杂度和空间复杂度的定义及意义在计算机科学中算法是解决问题的核心。一个问题的解决方案最终会通过编写代码来实现。那么如何衡量一个算法的好坏呢答案就是通过计算它的时间复杂度和空间复杂度。时间复杂度简单理解就是代码运行所花费的时间。它反映了算法执行效率的高低。空间复杂度简单理解就是代码运行过程中所需要的额外内存空间。它反映了算法对存储资源的占用情况。毫无疑问在能够满足功能需求的前提下这两者都是越小越好。一个优秀的算法应当既快又省即在尽可能短的时间内完成任务同时占用尽可能少的额外内存。2. 时间复杂度2.1 时间复杂度的表达方法大O符号Big O notation是用于描述函数渐进行为的数学符号。它关注的是算法运行时间随输入规模增长的趋势而不是具体的执行次数。函数表达式时间复杂度阶数名称5201314O(1)常数阶3n4O(n)线性阶3n^24n5O(n^2)平方阶3log(2)n4O(logn)对数阶2n3nlog(2)n14O(nlogn)nlogn阶n32n24n6O(n^3)立方阶2^nO(2^n)指数阶 小贴士常见的复杂度从优到劣大致排序为O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n)。在实际开发中应尽量避免使用指数阶的算法。2.2 时间复杂度的计算时间复杂度的计算核心是算法中基本操作的执行次数即为算法的时间复杂度。我们需要找出基本操作的执行次数与输入规模 n 之间的函数关系然后只保留最高阶项、去掉系数。重点理解时间复杂度关注的是数量级而不是真的具体执行了多少次。计算的基本原则① 只关注最高阶项T ( n ) 3 n 2 4 n 5 ⇒ O ( n 2 ) T(n) 3n^2 4n 5 \Rightarrow O(n^2)T(n)3n24n5⇒O(n2)因为当 n 很大时n 2 n^2n2起主导作用其他项的影响可以忽略不计。② 忽略常数系数T ( n ) 100 n ⇒ O ( n ) T(n) 100n \Rightarrow O(n)T(n)100n⇒O(n)T ( n ) 5 ⇒ O ( 1 ) T(n) 5 \Rightarrow O(1)T(n)5⇒O(1)2.3 从实例中理解时间复杂度2.3.1 计算 strchr 的时间复杂度// strchr 模拟实现constchar*strchr(constchar*str,intcharacter){while(*str!\0){if(*strcharacter){returnstr;}str;}returnNULL;}假设数组 str 的长度为 N我们来分析不同情况下的比较次数情况说明比较次数复杂度最好情况目标字符就在字符串第一个位置1 次O ( 1 ) O(1)O(1)最坏情况目标字符在末尾或根本不存在N1 次O ( N ) O(N)O(N)平均情况目标字符随机分布约 N/2 次O ( N ) O(N)O(N)时间复杂度取最坏情况T ( n ) O ( N ) T(n) O(N)T(n)O(N) 小贴士在分析算法复杂度时我们通常关注最坏情况因为它保证了算法在任何输入下都不会超过这个时间上限。2.3.2 计算 BubbleSort 的时间复杂度// 冒泡排序voidbubble(int*a,intn){for(intendn;end0;--end){intflag0;for(inti0;in-1;i){if(a[i]a[i1]){swap(a[i],a[i1]);flag1;}}if(flag0)break;}}冒泡排序是循环的嵌套。外层循环end每次减一最坏情况下要执行 n-1 次内层循环i最坏情况下也要执行 n-1 次。因此总执行次数约为T ( n ) ( n − 1 ) ( n − 2 ) ⋯ 1 n ( n − 1 ) 2 ⇒ O ( n 2 ) T(n) (n-1) (n-2) \dots 1 \frac{n(n-1)}{2} \Rightarrow O(n^2)T(n)(n−1)(n−2)⋯12n(n−1)⇒O(n2)所以冒泡排序的时间复杂度为O ( n 2 ) O(n^2)O(n2)。2.3.3 计算 BinarySearch 的时间复杂度intbinarysearch(int*a,intn,intx){intbegin0;intendn-1;while(beginend){intmidbegin((end-begin)1);if(a[mid]x){beginmid1;}elseif(a[mid]x){endmid-1;}elsereturnmid;}return-1;}二分查找每次把查找区间缩小一半n → n 2 → n 4 → ⋯ → 1 n \rightarrow \frac{n}{2} \rightarrow \frac{n}{4} \rightarrow \dots \rightarrow 1n→2n→4n→⋯→1假设最多比较k kk次后区间缩小到 1n 2 k 1 \frac{n}{2^k} 12kn1解得k log 2 n k \log_2 nklog2n所以比较次数约为log 2 n \boldsymbol{\log_2 n}log2n即二分查找的时间复杂度为O ( log n ) O(\log n)O(logn)。 小贴士二分查找的效率非常高但前提是数组必须是有序的。这也是为什么很多算法会先排序再查找的原因。2.3.4 计算斐波那契递归 Fib 的时间复杂度longlongFib(size_tN){if(N3)return1;returnFib(N-1)Fib(N-2);}每个节点都分裂成两个子节点树的高度大约是 N节点数量呈指数增长。因此T ( n ) O ( 2 n ) T(n) O(2^n)T(n)O(2n)⚠️ 注意递归实现的斐波那契数列时间复杂度极高当 N 较大时如 N50计算量将非常庞大。实际开发中应改用循环或动态规划来实现。3. 空间复杂度空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少 bytes 的空间因为这个数值没有太大意义。空间复杂度计算的是变量的个数。空间复杂度的计算规则基本与时间复杂度类似也使用大O渐进表示法。注意函数运行时所需要的栈空间存储参数、局部变量、一些寄存器信息等在编译期间已经确定好了因此空间复杂度主要通过函数在运行时显式申请的额外空间来确定。3.1 计算 BubbleSort 的空间复杂度voidbubble(int*a,intn){for(intendn;end0;--end){intflag0;for(inti0;in-1;i){if(a[i]a[i1]){swap(a[i],a[i1]);flag1;}}if(flag0)break;}}分析只用了end、i、flag等几个固定变量没有额外数组没有递归调用。因此额外空间不随 n 增长空间复杂度为O ( 1 ) O(1)O(1)。3.2 计算 Fibonacci 的空间复杂度longlong*Fibonacci(size_tn){if(n0)returnNULL;longlong*fibArray(longlong*)malloc((n1)*sizeof(longlong));fibArray[0]0;fibArray[1]1;for(inti2;in;i){fibArray[i]fibArray[i-1]fibArray[i-2];}returnfibArray;}分析递归调用栈最深为 n 层每层栈帧占常数空间。所以总栈空间与 n 成正比空间复杂度为O ( n ) O(n)O(n)。4. 总结与对比算法时间复杂度空间复杂度strchr线性查找O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)冒泡排序O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)二分查找O ( log n ) O(\log n)O(logn)O ( 1 ) O(1)O(1)斐波那契递归O ( 2 n ) O(2^n)O(2n)O ( n ) O(n)O(n)斐波那契循环O ( n ) O(n)O(n)O ( n ) O(n)O(n) 核心要点时间复杂度关注的是数量级而非具体执行次数分析复杂度时通常取最坏情况空间复杂度计算的是额外变量的个数而非字节数递归算法往往以空间换时间需权衡使用。
