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

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

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

好吧，开始我们的正题！

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

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

程序：

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)。