程序运行效率程序的运行效率分为两种：第一种是时间效率，第二种是空间效率。时间效率称为时间复杂度，而空间效率称为空间复杂度。时间复杂度主要衡量程序的运行速度，而空间复杂度主要衡量程序所需的额外存储空间。从理论上讲，无法计算执行程序所需的时间。只有在一台机器上运行程序，才能知道不同的机器在不同的时间得到的结果可能是不一样的。但是我们需要在电脑上测试每个程序吗？显然不现实，于是就有了时间复杂度的分析方法。在实践中，我们在计算时间复杂度时，不需要计算准确的执行次数，只需计算大概的执行次数即可。通常，使用大O渐近符号。我们可以说执行次数通常为1次时的时间复杂度。是O(1)，如果需要n次，可以说时间复杂度是O(n)。空间复杂度是衡量一个算法在运行过程中临时占用的存储空间大小的指标。空间复杂度不是程序占用了多少字节的空间，因为实际运行时很难计算，所以空间复杂度计算为变量个数。空间复杂度计算规则与时间复杂度基本相似，同样采用大O渐近记法。Python中常用的组合数据类型主要有元组、列表、集合和字典。每种数据类型不同操作的时间复杂度可以参考Python官方链接。网页上有详细的说明，https://wiki.python。org/moin/TimeComplexity元组和列表都是序列类型，它们的存储机制基本相同；集合和字典也基本相同，唯一的区别是集合的每个元素没有对应的值。下面我们以集合和列表为例，看看它们的搜索效率和存储开销。数据查找效率集合和列表数据查找效率差距有多大？先来看一组例子：importtimeimportrandomnums=[random.randint(0,2000000)foriinrange(1000)]list_test=list(range(1000000))set_test=set(list_test)count_list,count_set=0,0t1=time.time()#测试在列表中查找fornuminnums:ifnuminlist_test:count_list+=1t2=time.time()fornuminnums:#测试在集合中查找ifnuminset_test:count_set+=1t3=time.time()#测试在集合中搜索print('Numberfound,list:{},collection:{}'.format(count_list,count_set))print('usetime,list:{:.4f}s'.format(t2-t1))print('Usingtime,set:{:.4f}s'.format(t3-t2))输出结果为：foundnumber,list:515,set:515usetime,list:7.7953susetime,collection:0.0010s从上面的例子可以很明显的看出集合的查找效率远高于列表，所以在不同的应用场景下，一定要选择合适的数据类型，sm下看不出性能差异所有的数据量，但是一旦变成大量的数据，就会变得很不一样。数据存储开销集合的查找效率要比列表快很多，主要是因为它们的存储原理不同。集合需要消耗更多的空间来存储额外的信息，用空间开销来换取时间效率。接下来，我们通过getsizeof()函数来查看它们的存储开销的差异。getiszeof()函数是python的sys模块中用来获取对象内存大小的函数，返回的大小以字节为单位。importsysimportrandomlist_test=list(range(1000000))set_test=set(range(1000000))print('listsize:',sys.getsizeof(list_test))print('setsize:',sys.getsizeof(set_test))输出结果为：listoccupancysize:9000112collectionoccupancysize:33554656从结果可以看出，对于同样的数据内容，collection存储的开销是list的几倍。
