一、时间复杂度规则

1、计算时，往往只关注时间频度中最高次项，其他次要项和常数项忽略
例如： T=3*n^3+2*n^2+10000时间的复杂度： O(n^3)
2、顺序结构，时间复杂度按加法来计算
让用户输入2个列表，一个列表的长度为m另一个为n，对这2个列表分别求和
比较他们的和的大小
循环遍历，分别求和，比较大小
m步、n步 时间复杂度为O(m+n)
3、循环结构，时间复杂度按乘法来运算
T=n*n*3
4、分支结构：时间复杂度取最大值
5、没有特殊说明时，算法的时间复杂度都是指最坏的时间复杂度

最优时间复杂度：算法完成工作最少需要多久
最坏时间复杂度：算法完成工作最多需要多久
平均时间复杂度：算法完成工作平均需要多久
均摊时间复杂度：平均时间复杂度的补充，应用场景极少

例题：用户输入长度为6的数组,数组由1-6六个数字组成,顺序随机，请返回数字6出现的位置

for i in range(6):
     if lst[i]==6:
         print(i)
         break

lst=[1,2,3,4,5,6] 最坏情况O(n)
lst=[6,2,3,4,5,1] 最好情况O(1)
平均时间复杂度
6出现在每个位置的几率时一样的，所以时间复杂度为（1+2+3+4+5+6）/6(O(n))

二、常见时间复杂度

下图为算法的时间频度的增长趋势

时间频度：一个算法中的语句执行次数称为语句频度或者时间频度，记为T(n)
时间复杂度：随着问题的数据规模的增长，算法的时间频度的增长趋势，记作O(F(n))，F(n)是T(n)的渐进函数

三、列表和字典的时间复杂度