【数据结构与算法】时间复杂度和空间复杂度

今天药忘吃喽~ 2024-04-26 02:11 74阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年9月16日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  前言
 *  算法复杂度
 *  时间复杂度
 *   *  普通函数
     *  递归函数
     *  常见的时间复杂度
 *  空间复杂度
 *   *  普通函数
     *  递归函数

## 前言 ##

我们如何判断一个算法的好坏？我们如何比较不同算法？

## 算法复杂度 ##

算法的复杂性体现在运行该算法时所有占用计算机资源的多少上，计算机最重要的资源是时间（**CPU**）和空间（**内存**），因此复杂度分为时间和空间复杂度

渐进时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间

## 时间复杂度 ##

时间复杂度最简单的描述就是计算机运行算法时，程序代码被执行的总次数，而程序代码的执行总次数一般与问题规模（需要处理的数据量）有关

一般情况下，算法中基本语句重复执行的次数是问题规模 **n** 的某个函数 **f(n)**，算法的时间量度记作 **T(n) = O(f(n))**，**T** 表示 **time**，它表示随问题规模 **n** 的增大，算法执行时间的增长率和 **f(n)** 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度

### 普通函数 ###

我们来看下面这段代码

int sum(int n)
    {
        
    	int value = 0;
    	int i = 1;
    	while (i <= n) 
    	{
        
    		value += i;
    		i++;
    	}
    	return value;
    }

![在这里插入图片描述][e15c1825bff0496a84a960d6ae185230.png]

我们假设传入的 **n=100**，那么程序将会被执行 **1+1+100+100+100+1=303** 次，也就是 **3n+3** 次，记作 **T(n) = O(3n+3)**

时间复杂度关心的是数量级，所以我们要对 **f(n)** 函数表达式进行简化，具体的原则是：

*  略去常数
 *  只保留最高阶的项
 *  变最高阶项的系数为 **1**

也就是说对于普通的函数，我们只需要关心代码中最内层循环的次数就 **OK** 了

所以前面那段代码的时间复杂度写为 **O(n)** 即可

常见的时间复杂度按数量级递增排列依次为：常量阶 **O(1)**、对数阶 **O(log2n)**、线性阶 **O(n)**、线性对数阶 **O(nlog2n)**、平方阶 **O(n2)**、立方阶 **O(n3)**、… 、**k** 次方阶 **O(nk)**、指数阶 **O(2n)** 等等

**O(1)** < **O(log2n)** < **O(n)** < **O(nlog2n)** < **O(n2)** < **O(n3)** < **O(2n)** < **O(n!)** < **O(nn)**

![在这里插入图片描述][4691ac0b1bd64c7298bcc6750b78eba5.png]

注意：

1.  别把 **log2n** 当成系数
2.  如果输入的参数有两个 **m** 和 **n**，时间复杂度可以表示为 **O(max(m, n))**、**O(max(m2, n2))**

时间复杂度有 **最好时间复杂度**、**最坏时间复杂度** 和 **平均时间复杂度** 之分，通常我们只讨论算法在最坏情况下的时间复杂度，即分析在最坏情况下，算法执行时间的上界

### 递归函数 ###

对于递归函数，我们不仅要关心它最内层循环的次数，还要关心它递归的次数

*  下面这个递归函数的时间复杂度为 **O(1) \* O(n)**，也就是 **O(n)**
    
        int sum(int n)
        {
               
        	if (n == 0) return 0;
        	return n + sum(n - 1);
        }
 *  下面这个递归函数的时间复杂度为 **O(n) \* O(n/2)**，也就是 **O(n2)**
    
        int sum(int n)
        {
              
        	if (n == 0) return 0;
        	
        	int value = 0;
        	int i = 1;
        	while (i <= n) 
        	{
              
        		value += i;
        		i++;
        	}
        	
        	return value + sum(n - 1);
        }

### 常见的时间复杂度 ###

*  O(1)
    
        int x = 0;
        int y = 1;
        int temp = x;
        x = y;
        y = temp;
 *  O(n)
    
        for (int i = 1; i <= n; i++) {
              
        	x++;
        }
 *  O(logN)
    
        int i = 1;
        while (i < n) {
              
        	i *= 2;
        }
 *  O(nlogN)
    
        for (int i = 1; i <= n; i++) {
              
        	int x = 1;
        	while (x < n) {
              
        		x *= 2;
        	}
        }
 *  O(n2)
    
        for (int i = 1; i <= n; i++) {
              
        	for (int j = 1; j <= n; j++) {
              
        		x++;
        	}
        }

## 空间复杂度 ##

空间复杂度 **S(n)** 是指算法消耗的内存空间，也是问题规模（需要处理的数据量）**n** 的函数，**S(n) = O(f(n))**，**S** 表示 **space**

### 普通函数 ###

还是这段代码

int sum(int n)
    {
        
    	int value = 0;
    	int i = 1;
    	while (i <= n) 
    	{
        
    		value += i;
    		i++;
    	}
    	return value;
    }

不管 **n** 怎么变，算法所需要的内存空间都是一个固定的常数，空间复杂度为 **S(n) = O(1)**

然后我们再来看下面这个函数

int sum(int n)
    {
        
    	int i;
    	int arr[n];
    
    	...
    }

如果 **int** 占用的内存是 **4B**，这个函数所需空间是 **4+4+4n**，所以 **S(n) = O(n)**

int sum(int n)
    {
        
    	int i;
    	int arr1[n];
    	int arr2[n][n];
    
    	...
    }

这个函数所需空间是 **4+4+4n+4n2**，所以 **S(n) = O(n2)**

### 递归函数 ###

递归函数嵌套地调用自己，函数的参数和局部变量占用的内存空间在递去的过程中会持续增长，在归来的时候才逐层释放。当递归的深度达到一定量级，可能会造成栈内存空间不足的情况

int sum(int n)
    {
        
    	if (n == 0) return 0;
    	int i, j, k;
    	return n + sum(n - 1);
    }

**4** 个变量，递归的深度为 **n**，所以空间复杂度为 **O(4n)**，即 **O(n)**

再来看一下下面这两个有意思的例子

*  空间复杂度为 **O(n)\*O(n/2) = O(n2/2)**，即 **O(n2)**
    
        int sum(int n)
        {
              
        	if (n == 0) return 0;
        	int arr[n];
        	int value = n + sum(n - 1);
        	return value;
        }
 *  空间复杂度为 **O(n)+O(n/2) = O(3n/2)**，即 **O(n)**
    
        int sum(int n)
        {
              
        	if (n == 0) return 0;
        	int value = n + sum(n - 1);
        	int arr[n];
        	return value;
        }

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482
[e15c1825bff0496a84a960d6ae185230.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/a0eb11d1dec2465a805c518a3c9ecd12.png
[4691ac0b1bd64c7298bcc6750b78eba5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/668e82a41e8241f78abd1442e4005c0c.png