前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python|时间复杂度测试

Python|时间复杂度测试

作者头像
算法与编程之美
发布2020-02-13 17:39:30
1.3K0
发布2020-02-13 17:39:30
举报
文章被收录于专栏:算法与编程之美

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

问题描述

由我们所知每一个python程序的运行都是很多次的算法变成的,而计算机进行计算一定会花费时间,而我们在学习python基础时已经知道python相对其他语言来说是相对比较慢的。这样的差异我们称为时间复杂度。可能在一般情况下我们看不出时间的差异,那么我们接下来就将对时间进行测试。

解决方案

我们进行测试的题目很简单:如果a+b+c=1000,并且a**2+b**2=c**2,求abc的组合。

我们先用最简单的方法进行计算,就是将a,b,c分别放入(0,1000)内,分别一个一个的尝试,最后确定a,b,c的确定值。但是这里我们为了测试时间,我们要引用第三方库来记录程序的运行时间。

代码示例:

代码语言:javascript
复制
import time
start_time = time.time()
for a in range(1001):
    for b in range(1001):
        for c in range(1001):
            if a + b + c == 1000 and a**2 + b**2 == c**2:
                print("a,b,c:%d,%d,%d"%(a,b,c))
end_time = time.time()
used_time= end_time - start_time
print(used_time)

这里我们可以推算计算机就进行的运算次数为1000*1000*1000*2(将if语句看作为一步)

图1 运行结果

可以看出,进行这次运算大约使用了146秒,其实便可以看出python运行速度慢的问题了。

然后我们将代码简化为 c = 1000-a-b的形式,这样问题便被简化了,我们可以推算运算次数为1000*1000*3。

代码示例:

代码语言:javascript
复制
import time

start_time = time.time()

for a in range(1001):

     for b in range(1001):

         # for c in range(1001):

            c = 1000 - a - b

            if a**2 + b**2 == c**2:

                print("a,b,c:%d,%d,%d"%(a,b,c))

 

end_time = time.time()

used_time= end_time - start_time

print(used_time)

图2 运行结果2

可以看到在这个程序下,我们运行时间不足1秒,而我们仅仅只是优化了一步。两者相比,第一个比第二个快了许多。这种差异就叫做时间复杂度的差异。在算法中我们经常需要将一个程序简化,以达到最佳运算的目的。

结语

在算法中,我们经常会想要限制自己程序的运行时间,然后对其进行优化,达到最佳的运行时间。我们便也可以通过这种简单的方式来进行测量。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-01-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档