【算法与数据结构 02】数据结构——将昂贵的“时间”转换为廉价的“空间”

一时失言乱红尘 2023-02-14 03:05 19阅读 0赞

### 文章目录 ###

*   *  1. 时间昂贵、空间廉价
     *  2. 程序优化核心思路
     *  3. 举例说明：代码优化

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

## 1. 时间昂贵、空间廉价 ##

不管是在面试中手撕代码，还是在实际应用中去优化代码效率。其核心就是要：**尽量降低时间复杂度和空间复杂度。**

一段代码会消耗计算时间、资源空间，从而产生时间复杂度和空间复杂度。代码效率的瓶颈一般也发生在时间或者空间这两个方面。如果是缺少计算空间，花钱买服务器就可以了。但是如果是计算时间太长，只能投入宝贵的人生去跑无限的程序了！

相比于空间复杂度，时间复杂度的降低就显得更加重要了。因此，你会发现这样的结论：空间是廉价的，而时间是昂贵的。

既然时间是昂贵的，空间是廉价的。那么自然想到一个问题：能不能通过损失一点空间，换得时间上的缩短呢？

![在这里插入图片描述][aHR0cHM6Ly9zMC5sZ3N0YXRpYy5jb20vaS9pbWFnZS9NMDAvMEUvMTYvQ2dxQ0hsN0U5YkdBS1hrQUFHclA4RnRsOXFFODM0LmdpZg_pic_center]  
注：图片来源：https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185\#/detail/pc?id=3340

其实这是可以的。举我们城市交通的例子：在市中心的十字路上，通行的车辆很多，常常需要设置交通灯维持秩序。这就会使得司机花费一些时间去等待，因此时间成本就会大大增加。但是当我们建立了交桥后，车辆就可以选择分流行驶，这会大大减小等待交通灯的时间，实现了以空间换取司机们宝贵的时间。

总结上面的例子，可以得到结论：可以用廉价的空间换取宝贵的时间。那么在代码中，也是遵循着一样的逻辑，可以通过用空间去换取时间，完成时间复杂度向空间复杂度的转换。 而在这个过程中，需要我们选择合适的数据结构。

## 2. 程序优化核心思路 ##

**降低时间复杂度**的方法有：递归、二分法、排序算法、动态规划等

**降低空间复杂度**的核心思路就是：能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

**程序优化的最核心的思路**，分如下三个步骤：

*  第一步，**暴力解法**。在没有任何时间、空间约束下，完成代码任务的开发。
 *  第二步，**去除无效操作**。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。
 *  第三步，**时空转换**。设计合理的数据结构，完成时间复杂度向空间复杂度的转移。

注：常用的算法、数据结构将会在后面陆续分享。

## 3. 举例说明：代码优化 ##

>  例1：假设小明有任意多张面额为 2 元、5元、10元的货币，现要用它们凑出 100 元，请问小明最多总能找出多少种方法？。

**第一种解法：**

#include<iostream>
    using namespace std;
    
    int main()
    { 
    	int count=0;
    	for(int i=0;i<=100/10;i++)
    	{ 
    		for(int j=0;j<=100/5;j++)
    		{ 
    			for(int k=0;k<=100/2;k++)
    			{ 
    			
    				if(10*i+5*j+2*k==100)
    					count+=1;
    			}
    		}	
    	}
    	cout<<"一共有"<<count<<"种解决方法"<<endl;
    	return 0; 
    }

运行结果：  
![在这里插入图片描述][20200601093953140.png_pic_center]  
分析：这段代码用了三层嵌套的for循环，所以时间复杂度是O( n 3 n^3 n3)。

**第二种解法：**

#include<iostream>
    using namespace std;
    
    int main()
    { 
    	int count=0;
    	for(int i=0;i<=100/10;i++)
    	{ 
    		for(int j=0;j<=100/5;j++)
    		{ 
    			if((100-10*i-5*j>=0)&&((100-10*i-5*j)%2==0))
    				count+=1;
    		}	
    	}
    	cout<<"一共有"<<count<<"种解决方法"<<endl;
    	return 0; 
    }

运行结果：  
![在这里插入图片描述][20200601094047534.png_pic_center]  
分析：对代码结构进行了优化，通过两个嵌套的for循环后，直接判断余下的钱能否被2整除。因此整个时间复杂度是O( n 2 n^2 n2)。

> 例2：查找出一个数组中，出现次数最多的那个元素的数值。例如，输入数组 a = \[1,6,3,5,5,5,6 \] 中，查找出现次数最多的数值。

**第一种解法：**

#include<iostream>
    using namespace std;
    
    int main()
    { 
    	int temp=0,max_temp=0,max=0;
    	int a[7]={ 1,6,3,5,5,5,6};
    	for(int i=0;i<7;i++)
    	{ 
    		temp=0; //清零 
    		for(int j=0;j<7;j++)
    		{ 
    			if(a[i]==a[j])
    				temp+=1;	//记录每一个元素出现的次数 
    		}
    		if(temp>max_temp)
    		{  
    			max_temp=temp;
    			max=a[i];
    		} 
    	}
    	cout<<"出现次数最多的数是："<<max<<endl;
    	return 0;
    }

运行结果：  
![在这里插入图片描述][20200601123557192.png_pic_center]  
分析：在这里，我们用了两个嵌套的for循环，用来统计每一个元素出现的次数。因此这种代码结构的时间复杂度是O( n 2 n^2 n2)。

**第二种解法：**

#include<iostream>
    #include<map>
    
    using namespace std;
    int main()
    { 
    	int max = 0; //出现最多的次数 
    	int max_num = 0; //出现次数最多的数 
    	int a[7]={ 1,6,3,5,5,5,6};
    	map<int, int>mymap; //创建一个新的字典 
    	for(int i=0;i<7;i++)
    	{ 
    		if(mymap.find(a[i])==mymap.end())  //判断字典中是否存在该键a[i] 
    		{ 
    			mymap.insert(pair<int, int>(a[i],1)); //如果不存在，插入一个键值对：{a[i]:1} 
    		}
    		else
    		{ 
    			mymap[a[i]]+=1; //如果存在，该键对应的值加1 （即该元素出现的次数加1） 
    		}
    		if(mymap[a[i]]>max)  //比较元素出现的次数次
    		{  
    			max = mymap[a[i]]; //取最大次数 
    			max_num = a[i];  //最大次数对应的键 
    		}
    	}
    	cout<<"出现次数最多的数是："<<max_num<<endl;
    	return 0;
    }

运行结果：  
![在这里插入图片描述][20200601171356847.png_pic_center]  
分析：这段代码采用字典map的数据结构，来存放 \{元素：元素出现的次数\}。整个代码结构上，新创建了一个字典用来存放键值对，因此空间复杂度是O(n)；只用了一个for循环，所以时间复杂度降低为O(n)。  
从这个案例可以看出，使用了合理的数据结构——字典，使得这个任务的时间复杂度向空间复杂度转移。时间复杂度从O( n 2 n^2 n2)降低到O(n)，空间复杂度从O(1)增加到O(n)。

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

**系列文章：**[【算法与数据结构 01】衡量程序运行效率——复杂度][01]

参考链接：https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185\#/detail/pc?id=3340

[aHR0cHM6Ly9zMC5sZ3N0YXRpYy5jb20vaS9pbWFnZS9NMDAvMEUvMTYvQ2dxQ0hsN0U5YkdBS1hrQUFHclA4RnRsOXFFODM0LmdpZg_pic_center]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMC5sZ3N0YXRpYy5jb20vaS9pbWFnZS9NMDAvMEUvMTYvQ2dxQ0hsN0U5YkdBS1hrQUFHclA4RnRsOXFFODM0LmdpZg#pic_center
[20200601093953140.png_pic_center]: https://img-blog.csdnimg.cn/20200601093953140.png#pic_center
[20200601094047534.png_pic_center]: https://img-blog.csdnimg.cn/20200601094047534.png#pic_center
[20200601123557192.png_pic_center]: https://img-blog.csdnimg.cn/20200601123557192.png#pic_center
[20200601171356847.png_pic_center]: https://img-blog.csdnimg.cn/20200601171356847.png#pic_center
[01]: https://blog.csdn.net/wjinjie/article/details/106452718