一、时间复杂度规则
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)的渐进函数
三、列表和字典的时间复杂度
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/123560.html
