[python] insert()性能分析

我们在list中插入数据时，经常使用这两个函数：

append()：在列表的末尾增加一个数据

insert()：在某个特定位置前加一个数据

Python内的list实现是通过数组实现的，而不是链表的形式，所以每当执行insert()操作时，都要将插入位置的元素向后移动才能在相应的位置插入元素，执行append()操作时，如果分配的空间还足够大的话那么就可以直接插到最后，如果空间不够的话就需要将已有的数据复制到一片更大的空间后再插入新元素，insert()空间不够的话也是同样

所以，在使用insert()时，要特别注意性能问题，如：

例1：

a = []
for i in range(n):
    a.insert(0,'s')

例2：

a = []
for i in range(n):
    a.insert(i,'s')

一字之差，例1的时间复杂度为O(n^2)，例2为O(n)