📑 目录

• 1. 时间复杂度和空间复杂度的定义及意义
• 2. 时间复杂度
  • 2.1 时间复杂度的表达方法
  • 2.2 时间复杂度的计算
  • 2.3 从实例中理解时间复杂度
• 3. 空间复杂度
  • 3.1 计算 BubbleSort 的空间复杂度
  • 3.2 计算 Fibonacci 的空间复杂度
• 4. 总结与对比

1. 时间复杂度和空间复杂度的定义及意义

在计算机科学中，算法是解决问题的核心。一个问题的解决方案，最终会通过编写代码来实现。那么，如何衡量一个算法的好坏呢？答案就是通过计算它的时间复杂度和空间复杂度。

• 时间复杂度：简单理解，就是代码运行所花费的时间。它反映了算法执行效率的高低。
• 空间复杂度：简单理解，就是代码运行过程中所需要的额外内存空间。它反映了算法对存储资源的占用情况。

毫无疑问，在能够满足功能需求的前提下，这两者都是越小越好。一个优秀的算法，应当既快又省，即在尽可能短的时间内完成任务，同时占用尽可能少的额外内存。

2. 时间复杂度

2.1 时间复杂度的表达方法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。它关注的是算法运行时间随输入规模增长的趋势，而不是具体的执行次数。

💡 小贴士：常见的复杂度从优到劣大致排序为：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)=3n2+4n+5⇒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(*str==character){returnstr;}str++;}returnNULL;}

假设数组 str 的长度为 N，我们来分析不同情况下的比较次数：

时间复杂度取最坏情况：

T ( n ) = O ( N ) T(n) = O(N)T(n)=O(N)

💡 小贴士：在分析算法复杂度时，我们通常关注最坏情况，因为它保证了算法在任何输入下都不会超过这个时间上限。

2.3.2 计算 BubbleSort 的时间复杂度

// 冒泡排序voidbubble(int*a,intn){for(intend=n;end>0;--end){intflag=0;for(inti=0;i<n-1;i++){if(a[i]>a[i+1]){swap(&a[i],&a[i+1]);flag=1;}}if(flag==0)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)+⋯+1=2n(n−1)​⇒O(n2)

所以冒泡排序的时间复杂度为：O ( n 2 ) O(n^2)O(n2)。

2.3.3 计算 BinarySearch 的时间复杂度

intbinarysearch(int*a,intn,intx){intbegin=0;intend=n-1;while(begin<=end){intmid=begin+((end-begin)>>1);if(a[mid]<x){begin=mid+1;}elseif(a[mid]>x){end=mid-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次后区间缩小到 1：

n 2 k = 1 \frac{n}{2^k} = 12kn​=1

解得：

k = log ⁡ 2 n k = \log_2 nk=log2​n

所以比较次数约为log ⁡ 2 n \boldsymbol{\log_2 n}log2​n，即二分查找的时间复杂度为O ( log ⁡ n ) O(\log n)O(logn)。

💡 小贴士：二分查找的效率非常高，但前提是数组必须是有序的。这也是为什么很多算法会先排序再查找的原因。

2.3.4 计算斐波那契递归 Fib 的时间复杂度

longlongFib(size_tN){if(N<3)return1;returnFib(N-1)+Fib(N-2);}

每个节点都分裂成两个子节点，树的高度大约是 N，节点数量呈指数增长。因此：

T ( n ) = O ( 2 n ) T(n) = O(2^n)T(n)=O(2n)

⚠️ 注意：递归实现的斐波那契数列时间复杂度极高，当 N 较大时（如 N=50），计算量将非常庞大。实际开发中应改用循环或动态规划来实现。

3. 空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度不是程序占用了多少 bytes 的空间，因为这个数值没有太大意义。空间复杂度计算的是变量的个数。

空间复杂度的计算规则基本与时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时显式申请的额外空间来确定。

3.1 计算 BubbleSort 的空间复杂度

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

分析：

• 只用了end、i、flag等几个固定变量；
• 没有额外数组；
• 没有递归调用。

因此，额外空间不随 n 增长，空间复杂度为O ( 1 ) O(1)O(1)。

3.2 计算 Fibonacci 的空间复杂度

longlong*Fibonacci(size_tn){if(n==0)returnNULL;longlong*fibArray=(longlong*)malloc((n+1)*sizeof(longlong));fibArray[0]=0;fibArray[1]=1;for(inti=2;i<=n;++i){fibArray[i]=fibArray[i-1]+fibArray[i-2];}returnfibArray;}

分析：

• 递归调用栈最深为 n 层；
• 每层栈帧占常数空间。

所以总栈空间与 n 成正比，空间复杂度为O ( n ) O(n)O(n)。

4. 总结与对比

💡 核心要点：

1. 时间复杂度关注的是数量级，而非具体执行次数；
2. 分析复杂度时通常取最坏情况；
3. 空间复杂度计算的是额外变量的个数，而非字节数；
4. 递归算法往往以空间换时间，需权衡使用。