降低程序空间复杂度的一些技巧

当电脑运行过热时，可以通过关闭一些不需要的应用程序来降低电脑温度。 #生活常识# #电子设备#

对于程序，衡量其好坏的重要标准是时间复杂度和空间复杂度。在可以完成目标任务的前提下，使程序具有较低的时间复杂度和较低的空间复杂度是我们一直追求的目标。

然而有时候两者不可兼得。在减少时间复杂度的状况下，空间复杂度往往会提高，而在减少空间复杂度的状况下，时间复杂度往往会提高。想要在二者之间得到平衡，显然，这不太容易，可谓是鱼和熊掌不可兼得！

好吧，开始我们的正题！

假设我们想象这样一个场景，在我们的电脑上有一份文件，上面保存了水果名称，比如类似这样的一些数据，苹果，梨，桃子，西瓜，葡萄，苹果，西瓜......。我们的目的是统计这些名称中谁出现的次数最多。

程序实现思路很简单，也就是初始化一个字典，如果该名称不存在，则将该名称加入字典，其值设为一，如果该名称已存在，则其值加一。

程序：

fruitData={}with open('data.txt') as f: content=f.read().splitlines() #读取整个文件for fruit in content: if fruit in fruitData: fruitData[fruit]=fruitData[fruit]+1 else: fruitData[fruit]=1print(fruitData)

好吧，就是这么简单，但仔细想想却一个问题，那就是这是把文件信息全部读入到内存。当文件规模小时，占用不了多少内存，一旦规模大，比如1000GB(假设超过所用电脑的内存)，那就出现了问题。

前面是一次读入所有数据，事实上，我们完全可以读入一个数据，处理一个数据，处理下一个数据时，前面一个数据所占用的内存也会及时释放掉，这样就把内存占用过多的问题就被解决了。

对原程序的改进：

​​​​​​​

fruitData={}with open('data.txt') as f: for fruit in f: #一次读一行 fruit=fruit.strip() #删除结尾的换行符 if fruit in fruitData: fruitData[fruit]=fruitData[fruit]+1 else: fruitData[fruit]=1print(fruitData)

此时，空间复杂度也由原来的O(n)降为了O(1)。

网址：降低程序空间复杂度的一些技巧 https://www.yuejiaxmz.com/news/view/566647

相关内容

动态规划的空间压缩技巧（降低空间复杂度）
算法优化的艺术：降低时间复杂度与提升算法效率的实战技巧
时间复杂度和空间复杂度详解
【时间复杂度】时间复杂度优化法则简讲
实验一 算法优化技巧与时间复杂度
深入解析算法效率核心：时间与空间复杂度概览及优化策略
下面程序段的时间复杂度是( )。for(i=0;i
数据结构之算法的时间与空间复杂度
求下列程序段时间复杂度 i=1; while(i
时间复杂度

随便看看