【数据结构】详谈复杂度

谁借莪１个温暖的怀抱￠ 2024-03-27 09:05 75阅读 0赞

**目录**

1.前言

2.什么是复杂度

3.如何计算时间复杂度

1.引例

2.二分查找

3.常见的复杂度

4.如何计算空间复杂度

5.关于递归

6.总结

--------------------

### 1.前言 ###

我们在做一些算法题时，经常会发现题目会对时间复杂度或者空间复杂度有所要求，如果你不知道什么是复杂度时，你可能就无法正确的完成题目。因此，我们在学习数据结构与算法的第一步，就是要理解什么是复杂度。

### 2.什么是复杂度 ###

复杂度是衡量算法效率的标准，而算法分析效率分为两种：时间效率和空间效率。由此，复杂度也被分为两种：时间复杂度和空间复杂度。时间效率被称为时间复杂度， 而空间效率被称作空间复杂度。

时间复杂度主要衡量的是一个算法的运行速度。由于在不同的硬件上，程序运行的速度会有所不同，所以时间复杂度代表的并不是一个程序运行的时间，这并没有意义。而一个算法所花费的时间与其中语句的执行次数成正比，因此我们把算法中的基本操作的执行次数，称为算法的时间复杂度。

空间复杂度主要衡量一个算法所需要的额外空间。正如时间复杂度计算的不是时间，空间复杂度也不是计算程序占用了多少bytes的空间，因为这个也没太大意义，空间复杂度算的是变量的个数。

> 在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。 所以我们如今已经不需要再特别关注一个算法的空间复杂度。

### 3.如何计算时间复杂度 ###

#### 1.引例 ####

我们来看下面一道题目：

// 请计算一下Func1基本操作执行了多少次？
    void Func1(int N)    
    {
    	int count = 0;
    	for (int i = 0; i < N; ++i)
    	{
    		for (int j = 0; j < N; ++j)
    		{
    			++count;
    		}
    	}
    	for (int k = 0; k < 2 * N; ++k)
    	{
    		++count;
    	}
    	int M = 10;
    	while (M--)
    	{
    		++count;
    	}
    	printf("%d\n", count);
    }

我们通过分析得到Func1 执行的基本操作次数如下：

![F(N)=N^2+2\\times N+10][F_N_N_2_2_times N_10]

> N = 10 ，F(N) = 130
> 
> N = 100 ，F(N) = 10210
> 
> N = 1000 ，F(N) = 1002010

显然如果直接用来表示时间复杂度的话会显得太过复杂。实际上我们发现随之N的不断增大，F(N)后续两项对结果的影响越来越小。因此我们在计算时间复杂度时，并不一定要计算精确的执行次数，只需求大概的执行次数，因此，就有了大O渐进表示法。

> **大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。**
> 
> 推导大O阶方法：
> 
> 1、用常数1取代运行次数中的所有加法常数。
> 
> 2、在修改后的运行次数函数中，只保留最高阶项。
> 
> 3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
> 
> --------------------
> 
> **例如上述代码的时间复杂度就是O(![N^\{2\}][N_2])，![N^\{2\}][N_2]就是我们求得的大O阶。我们用O(![N^\{2\}][N_2])表示当N趋于无穷大时，Func1()算法执行基本操作的次数约为![N^\{2\}][N_2]次(后两项忽略不急)。**

> 几个小例子：
> 
> ![F(N)=2N^\{3\}+N^\{2\}+2N+1][F_N_2N_3_N_2_2N_1]\-------------------------------------------------->>> O(![N^\{3\}][N_3])
> 
> ![F(M,N)=M^\{2\}+M+N^\{2\}+N][F_M_N_M_2_M_N_2_N]\---------------------------------------------->>> O(![M^\{2\}+N^\{2\}][M_2_N_2])
> 
> ![F(N)=(N)+(N-1)+(N-2)+...+1][F_N_N_N-1_N-2_..._1]\------------------------------>>> O(![N^\{2\}][N_2])

#### 2.二分查找 ####

下面是我们常见的一段二分查找代码，你能算出它的时间复杂度吗？

// 计算BinarySearch的时间复杂度？
    
    int BinarySearch(int* a, int n, int x)
    {
    	assert(a);
    	int begin = 0;
    	int end = n;
    	while (begin < end)
    	{
    		int mid = begin + ((end - begin) >> 1);
    		if (a[mid] < x)
    			begin = mid + 1;
    		else if (a[mid] > x)
    			end = mid;
    		else
    			return mid;
    	}
    	return -1;
    }

> 由于二分查找每次都能去掉一半的元素，因此其时间复杂度应是以2为底的对数.
> 
> 但我们发现，在实际执行过程中，可能有三种情况：
> 
> --------------------
> 
> 1.运气极好，直接就找到，此时执行次数为1次
> 
> 2.运气中等，找了一半才找到，此时执行次数为![\\frac\{1\}\{2\}logn][frac_1_2_logn]次
> 
> 3.运气极差，最后才找到，此时执行次数为![logn][]次
> 
> --------------------
> 
> 那我们是要以那种情况的执行次数作为标准来计算时间复杂度呢？其实我们在实际中一般情况关注的是算法的最坏运行情况，所以此二分查找算法的时间复杂度为O(![logn][])。

#### 3.常见的复杂度 ####

我们常见的复杂度有以下几种：

> 第一级：O（1），O（logn）
> 
> 第二级：O（n），O（nlogn）
> 
> 第三级：O（![n^\{2\}][n_2]）,O（![2^\{n\}][2_n]），O（n！）
> 
> 从上往下，从左到右，算法效率依次降低，下图为各种复杂度对于n的变化曲线：

![b2aca74dd80e4be1a5d4aa0146e1b03c.png][]

> **我们发现，O（logn）与O（1）十分的接近，几乎达到了常数级，远超于其他复杂度。**

### 4.如何计算空间复杂度 ###

一样的，我们通过小例题来入手：

// 计算Fibonacci的空间复杂度？
    
    long long* Fibonacci(int n)
    {
    	if (n == 0)
    		return NULL;
    
    	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
    	fibArray[0] = 0;
    	fibArray[1] = 1;
    	for (int i = 2; i <= n; ++i)
    	{
    		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    	}
    	return fibArray;
    }

上面说到空间复杂度是统计变量的个数，因此通过分析得到Fibonacci() 创建的变量个数为：

![F(n)=n+1+1][F_n_n_1_1]

> 其中，n+1为malloc在堆上申请的空间，1为在栈上开辟的空间i（此处我们不考虑形参）。与时间复杂度相同，为了表达方便，空间复杂度同样采用大O的渐进表示法,通过保留最高项，去除常数项，我们得到Fibonacci()函数的空间复杂度为O(n）。

### 5.关于递归 ###

我们来分析斐波那契数列递归解法的时间复杂度和空间复杂度：

// 计算Fib的时间复杂度和空间复杂度？
    int Fib(int n)
    {
    	if (n == 1 || n == 2)
    	{
    		return 1;
    	}
    	else
    	{
    		return Fib(n - 1) + Fib(n - 2);
    	}
    }

我们知道，函数调用形成栈帧是需要成本，这个成本就体现在时间与空间上。(有关函数栈帧请点击传送门查看往期：[C语言之函数栈帧(动图详解)][C]) 。每一次函数调用，就会开辟空间，形成栈帧，消耗时间。直到函数调用结束返回，才会销毁栈帧，释放空间。我们画出递归树(假设n=6)：

![81c5766ea1954a60b68fdc35a7e9866f.png][]

> 对于时间复杂度，Fib每次调用都会进行一次加法操作。因此，我们可以认为每个子结点代表一次基本操作，而高度为k的二叉树最多![\{\\color\{Red\} \}2^\{k\}-1][color_Red_ _2_k_-1]个子结点(满二叉树)。于是我们得到基本操作次数![F(n)=2^\{n-1\}-1][F_n_2_n-1_-1]，其中n-1代表二叉树的高度。转化为时间复杂度则为O（![2^\{n\}][2_n]）。
> 
> --------------------
> 
> 而对于空间复杂度，我们需要知道的是，函数栈帧会在函数调用完毕后销毁，释放空间。所以当其中一个分支到达递归尽头时，就会开始返回，此时空间会被释放。下次再调用函数时，就可以将释放的空间重复利用起来。因此，我们只需找到最长的分支有几个结点（即高度）就可以得到关系式![F(n)=n-1][F_n_n-1]。转化为空间复杂度即为O（n）。

我们发现，用递归解决斐波那契数列是十分耗时的。其时间复杂度为O（![2^\{n\}][2_n]），属于是指数级的时间复杂度，这是因为在递归时会进行多次重复调用计算，造成大量的时间浪费。因此，我们就可以使用动态规划的方法，通过创建一个数组(甚至只需要两个变量)来保存每次计算的结果（详情可见往期：[C语言刷题之动态规划入门(二)][C 1]）。这种做法的时间复杂度为O（n），空间复杂度也为O（n），代码如下：

#include<stdio.h>
    #include<stdlib.h>
    int main() 
    {
    	int n = 0;
        scanf("%d",&n);
        //这里也可以只建立两个变量
        int* dp=(int*)malloc(n*sizeof(int));
        //对dp数组进行赋初值
    	dp[0] = 1;
    	dp[1] = 1;
    	for (int i = 2; i < n; i++)     //遍历dp数组
    	{
    		dp[i] = dp[i - 1] + dp[i - 2];  //递推公式
    	}
        printf("%d",dp[n-1]);
        free(dp);
        dp=NULL;
    	return 0;
    }

### 6.总结 ###

> **1.时间复杂度计算的是基本操作执行次数，空间复杂度计算的是变量的个数，二者都采用大O渐进表示法。**
> 
> **2.时间/空间复杂度都是在最坏情况下所得到的。**
> 
> **3.时间一去不复返，是累积的；而空间是可以释放并重复利用的，是不累积的。**

--------------------

***以上，就是本期的全部内容。***

***制作不易，能否点个赞再走呢qwq***

[F_N_N_2_2_times N_10]: https://latex.csdn.net/eq?F%28N%29%3DN%5E2&plus;2%5Ctimes%20N&plus;10
[N_2]: https://latex.csdn.net/eq?N%5E%7B2%7D
[F_N_2N_3_N_2_2N_1]: https://latex.csdn.net/eq?F%28N%29%3D2N%5E%7B3%7D&plus;N%5E%7B2%7D&plus;2N&plus;1
[N_3]: https://latex.csdn.net/eq?N%5E%7B3%7D
[F_M_N_M_2_M_N_2_N]: https://latex.csdn.net/eq?F%28M%2CN%29%3DM%5E%7B2%7D&plus;M&plus;N%5E%7B2%7D&plus;N
[M_2_N_2]: https://latex.csdn.net/eq?M%5E%7B2%7D&plus;N%5E%7B2%7D
[F_N_N_N-1_N-2_..._1]: https://latex.csdn.net/eq?F%28N%29%3D%28N%29&plus;%28N-1%29&plus;%28N-2%29&plus;...&plus;1
[frac_1_2_logn]: https://latex.csdn.net/eq?%5Cfrac%7B1%7D%7B2%7Dlogn
[logn]: https://latex.csdn.net/eq?logn
[n_2]: https://latex.csdn.net/eq?n%5E%7B2%7D
[2_n]: https://latex.csdn.net/eq?2%5E%7Bn%7D
[b2aca74dd80e4be1a5d4aa0146e1b03c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4f5c5fc3298c40ac953c6fee4e67540e.png
[F_n_n_1_1]: https://latex.csdn.net/eq?F%28n%29%3Dn&plus;1&plus;1
[C]: http://t.csdn.cn/J3cN7
[81c5766ea1954a60b68fdc35a7e9866f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/57ac27426fb04536ba489a7c6eab2ae4.png
[color_Red_ _2_k_-1]: https://latex.csdn.net/eq?%7B%5Ccolor%7BRed%7D%20%7D2%5E%7Bk%7D-1
[F_n_2_n-1_-1]: https://latex.csdn.net/eq?F%28n%29%3D2%5E%7Bn-1%7D-1
[F_n_n-1]: https://latex.csdn.net/eq?F%28n%29%3Dn-1
[C 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/7a94284267154aeaad1d46ddc5c99680.png