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

举报
AI 菌 发表于 2021/08/04 23:38:12 2021/08/04
【摘要】 文章目录 1. 时间昂贵、空间廉价2. 程序优化核心思路3. 举例说明:代码优化 1. 时间昂贵、空间廉价 不管是在面试中手撕代码,还是在实际应用中去优化代码效率。其核心就是要:尽量降低时间复杂度和空间复杂度。 一段代码会消耗计算时间、资源空间,从而产生时间复杂度和空间复杂度。代码效率的瓶颈一般也发生在时间或者空间这两个方面。如果是缺少计算空间...


1. 时间昂贵、空间廉价

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

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

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

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

在这里插入图片描述
注:图片来源: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; 
} 

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

运行结果:
在这里插入图片描述
分析:这段代码用了三层嵌套的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; 
} 

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

运行结果:
在这里插入图片描述
分析:对代码结构进行了优化,通过两个嵌套的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;
} 

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

运行结果:
在这里插入图片描述
分析:在这里,我们用了两个嵌套的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;
} 

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

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


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

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

文章来源: ai-wx.blog.csdn.net,作者:AI 菌,版权归原作者所有,如需转载,请联系作者。

原文链接:ai-wx.blog.csdn.net/article/details/106462116

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。