Python算法分析

本文是我自学Python过程的学习笔记和心得体会，不求全面，参考书籍《Python数据结构与算法分析》。

算法分析

程序的好坏取决与你的标准，我们应该朝着更高可读性代码的目标努力。对于算法而言，算法分析关注的是所使用的计算资源，即空间（内存）与时间，是一种独立于实现的算法度量方法。

解决方案所需要的空间总量通常由问题实例本身决定，也会有特定的空间需求。执行时间或运行时间是另一个需要思考的指标，在Python里可以用time模块的time函数来记录开始和结束的时刻，从而获得运行时间。

执行算法的实际时间并不是一个有用的指标，它跟计算机、编译器、编程语言等都有关系，我们需要一个独立于程序或计算机的指标——大O记法。

大O记法是指将算法所需基本计算单位函数在问题规模n足够大时，舍去增长较慢的部分，留下最大的数量级，比如O(n)，表示属于线性阶算法。

Python数据结构的性能

列表生成

Python的设计师考虑了列表最常见的用法来优化列表的实现。比如为了保证索引操作为常数阶，在调用pop(0)时，其余元素都要向列表头前移一位。我们可以用timeit模块做实验，验证各个方法的大O效率。用法如下：

def test():
	pass
t1 = Timer("test()","from __main__ import test")
print(t1.timeit(1000))

生成列表的四种方式：

#连接
def f1():
    l = []
    for i in range(1000):
    	l = l + [i]
#追加        
def f2():
    l = []
    for i in range(1000):
        l.append(i)
#列表解析式        
def f3():
    l = [i for i in range(1000)]
#列表构造器    
def f4():
    l = list(range(1000))

经测试，连接操作远远慢于其他方式，后两种较快。

列表操作的大O效率

操作	大O效率
索引	O(1)
索引赋值	O(1)
追加	O(1)
pop()	O(1)
pop(i)	O(n)
insert(i,item)	O(n)
删除	O(n)
遍历	O(n)
包含	O(n)
切片	O(k)
删除切片	O(n)
设置切片	O(n+k)
反转	O(n)
连接	O(k)
排序	O(nlogn)
乘法	O(nk)

字典操作的大O效率

操作	大O效率
复制	O(n)
取值	O(1)
赋值	O(1)
删除	O(1)
遍历	O(n)
包含	O(1)

小结

算法分析是一种独立于实现的算法度量方法。
大O记法可以使得算法可以根据随问题规模增长而起主导作用的部分进行分类。

Yinyaohui