复杂度分析（下）
最好、最坏；平均；均摊时间复杂度
最好、最坏时间复杂度
代码示例1
# 代码示例1
def find(x, list_):
for item in list_:
if item == x:
pos = list_.index(x)
return pos
上述代码时间复杂度：等于len(list_)=n => O(n)
# 改写
def find2(x,list_):
for item in list_:
if item == x:
return list_.index(x)
假如list_=[1,2,3,4,5,6,7]，目标值：x=1；此时就能在O（1）的时间复杂度内找到该值；#最好
当x不存在这个列表中，需要对整个列表进行遍历，此时O（n）#最坏
以上就是最好、最坏时间复杂度的例子；
平均时间复杂度
上述代码中，list_长度为n，寻找list的值是否与目标值相等的情况：
1+2+3+……+n-1+n => n(n-1)/2; 值存在于list中的情况：n+1
T(n) = n(n-1)/(2(n+1))
通常，我们会忽略掉常数，系数；得到O（n）。
加权平均时间复杂度
上述X存在于list中的情况，是不可能会一样的，假设，X存在与不存在的概率都是1/2，
存在与0~n-1，概率=1/n，总的概率 = 1/(2n)；
平均时间复杂度变成：
1（1/(2n)）+2（1/(2n)）+3*（1/(2n)）+4*（1/(2n)）+……+n*（1/(2n)）=n(n-1)/2 * 1/(2n) = n(n-1)/(4n)
得出结论：加权平均时间复杂度：O(n)
均摊（摊还）时间复杂度
在python内部，列表是动态的，因为他能够实现动态扩容；列表创建的时候会预估你需要存的长度，当你要存的东西快要超出长度的时候，他会申请两倍于自身的空间，进行扩容。
假设我们这个列表在存放满了的时候才进行扩容；会出现以下两种情况：
第一：列表还没存满，直接往后面插值；list.append(X),时间复杂度：O(1)
第二：列表刚好满了，我还要再插值，先申请两倍大的空间，将内容复制到新的空间，再插值;
时间复杂度：O（n）
摊还分析：当我们进行一次O（n）的操作，都会有n-1次的O(1)的操作；
动态插入的的均摊时间复杂度：O（1）。