时间与空间的矛盾

发表于 | 分类于
字数统计: 313 字

记得以前上软件技术导论的时候,听的最多的话就是时间和空间是两个不可调和的矛盾,要么去拥有时间,要么去拥有空间,当然如果一个算法中即不节省空间,也不节约空间,那这就是个失败的算法.

这两者是不可同时兼得的,就拿Python中的数据类型来说

1
2
3
4
5
6
7
8
9
import sys
list_ = []
tupel_ = ()
dic_ = {}
set_ = set([])
print('%s,%s' % (type(list_), sys.getsizeof(list_)))
print('%s,%s' % (type(tupel_), sys.getsizeof(tupel_)))
print('%s,%s' % (type(dic_), sys.getsizeof(dic_)))
print('%s,%s' % (type(set_), sys.getsizeof(set_)))
1
2
3
4
<class 'list'>,64
<class 'tuple'>,48
<class 'tuple'>,240
<class 'set'>,224

可以看到,列表和元组所占内存较小,而字典和集合占的内存较大,所以可以这样理解,当我们去查询某一个元素是否在列表或者字典中时,列表查找的时间复杂度是O(n),而字典查找的时间复杂度是O(1),字典牺牲了空间换取了时间.

我只是很肤浅的从这里看到了一点关于时间与空间的矛盾,我相信通过不断的深入学习,应该会遇到更多的这种情况.