数据结构与算法（Python版）：时间复杂度和大O表示法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法（Python版）：时间复杂度和大O表示法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2013字，纯文字阅读大概需要3分钟。
内容图文
一.时间复杂度
首先我们来看一个问题·：
题目：如果a+b+c=1000，且a^2+b^2=c^2(a,b,c为自然数),如何求出a,b,c所有可能的组合？ 看到这个题目我们的第一反应则是直接套用三个循环使用枚举法直接得到答案，程序如下：import time
start_time = time.time()
for a in range(0,1001):
for b in range(0,1001):
for c in range(0,1001):
if a+b+c == 1000 and a**2+b**2==c**2:
print("The possible a is {}, b is {}, c is {}".format(a,b,c))
end_time = time.time()
print("time:{}".format(end_time-start_time))
print("finished")
这样我们就可以得到结果：
The possible a is 0, b is 500, c is 500 The possible a is 200, b is 375, c is 425 The possible a is 375, b is 200, c is 425 The possible a is 500, b is 0, c is 500 time:190.9680194854736328 finished
我们可以通过这个程序来分析它的运算规模大小，假如说程序每执行一次，则计为1，那么一个循环里则执行了1000次，三个循环就执行了1000*1000*1000次，在最后一个变量C的循环当中，还有if语句和print语句，这两个都算是执行的步骤，因此我们将总体执行的步骤表示为：
T=1000^3*（1+1）
但是1000这个数字是可以更换的，可以变成2000,3000，可以随着题目要求的变化而变化，这样我们可以得到一个更为普遍的函数来表示这个时间复杂度（程序执行所需要的全部步骤就叫做时间复杂度，且我们一般将最坏时间复杂度称为时间复杂度，最坏时间复杂度表示的是程序一旦完成这些步骤一定能够完成所有的工作，因为有的时候程序完成一些步骤就会得到最后答案，但是我们不能够使用最优时间复杂度，这太过特殊了）。你可以将1000变为n，这样就能得到以下函数的形式：
T(n)=n^3*2
二.大O表示法
之前我们已经发得到了上面这个程序的时间复杂度，现在我们来使用更为通识的大O表示法来表示它，这个表示法说白了就是忽略掉低次方的项，当然对于只有常数项的时间复杂度无法进行忽略，对于刚才我们得到的函数：T(n)=n^3*2。其中后面乘上的2相对平方而言来说是非常小的，因此可以忽略不计，用大O表示法可以表示为：
T(n)=O(n^3)
这样就得到了我们这个程序时间复杂度的大O表示法的结果了。
下面是常见大O表示法的表示方法以及术语：
下面是练习：
第一个的答案是：O（1）
第二个的答案是：O（n）
第三个的答案是：O（n^2）
第四个的答案是：O（n^2）
今天有关时间复杂度和大O表示法的知识就到此结束了！希望你能够有所收获！
结果
内容总结
以上是互联网集市为您收集整理的数据结构与算法（Python版）：时间复杂度和大O表示法全部内容，希望文章能够帮你解决数据结构与算法（Python版）：时间复杂度和大O表示法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。