Python 数据结构和算法 02 | 如何瞄一眼,就知道这段代码的效率?

到后面,我们要追求的是自己写的代码效率尽量高,在此之前,当我们一行行的代码敲下来之后,如何去评估自己写出的代码效率如何呢?

这时候我们要学会评估代码的质量,也就是它快么?它省空间么?

我们先来假设一下这样的弱智题目,在下面这些有序的数据中,如果要让你找 “68” 这个数字所在的位置,你会怎么去找?

1 、2、 3 、4 、5 、6 、7 、8、 9 、10 、11 、12 、13 、14、 15、 16、 17 、18、19 、20、 21、22、23、 24 、25 、26 、27、 28、 29 、30、 31 、32 、33 、34 、35 、36 、37 、38、 39 、40、 41 、42 、43、 44 、45 、46、 47 、48、 49、 50 、51 、52、 53、 54 、55 、56 、57、 58、 59、 60 、61、 62 、63 、64 、65 、66、 67 、68 、69 、70、 71 、72 、73、74 75、 76 、77 、78、 79 、80、81 、82、83、 84 、85、 86 、87、 88 、89、 90、 91 、92 、93 、94 、95 、96、 97、 98、 99、 100

可能你会从第一个数字开始,一个一个查找,直到找到它为止:

可能你还想到了另一种快一些的方法,就是折半查找,也就是说先从中间开始查找,如果发现这个数小了,说明这个数的左边所有的数都可以排除掉,然后再从剩下的数中折半查找,知道查找到那个数字位置:

那么,这两段代码,哪一种效率高呢?如何评估它们的时间复杂度呢?

如果现在的你对代码复杂度的分析全无概念,完全没有关系,我们用笨办法来 debug 分析一下这两段代码的运行时间效率。

首先我们来看第一段代码:

可以看到,我们在这里执行了 68 次(每次都执行 i+1 的操作)才找到我们要找的数,假设执行一次所需要的时间为 t ,那么这段代码的运行时间可以这样表示:

T1 = 68t

ok, 我们以同样的方式,来 debug 分析一下第二段代码:

可以看到这段代码很快, 4 次就找到了,不过这段代码每次都进行折半查询,所以它的时间复杂度应该是这么表示的:

T2 = log(100)t

因为 T1 > T2 , 所以说第二段代码的运行效率比较高。

接着我们再假设一下,如果我们不止在 100 个数里面找呢?有超级多个,多到 n 个,那么这时候它们的复杂度应该这么表示对吧:

本文隐藏内容 登陆 后才可以浏览
ok,你先把这些时间复杂度的表示方法熟悉一下,下一篇再用一些简单的 Python 代码让你熟悉一下大O,以及在代码相对来说多一些的情况下,应该怎么去分析。

发表回复