前言
你好,我是彤哥,一个每天爬二十六层楼还不忘读源码的硬核男人。 上一节,我们一起学习了表示复杂度的几个符号,我们说,通常使用大O来表示算法的复杂度,不仅合理,而且书写方便。 那么,使用大O表示法评估算法的复杂度有没有什么套路呢?以及常见的复杂度有哪些呢? 本节,我们就来解决这两个问题。 前情回顾在正式讲解套路之前,我们先回忆一下前面几节讲到的内容。 在第2节,我们学习了渐近分析法,将算法的复杂度与输入规模挂钩,随着输入规模的增大,算法执行的时间将呈现一种什么样的趋势,将这个趋势用函数表示,再去除低阶项和常数项,就得到了算法的时间复杂度。 在第3节,我们分别从最坏、平均、最好三种情况来分析了算法的复杂度,得出结论,一般使用最坏情况来评估算法的复杂度。 在第4节,我们通过动态数组的插入元素及经典快速排序的时间复杂度,解释了有的时候不能使用最坏情况来评估算法的复杂度。 在第5节,我们从读音、数学、通俗理解三个方面分析了各种表示算法复杂度的符号,得出结论还是使用大O比较香,大O代表了算法的上界,它与前面讲到的最坏情况往往是对应的。 所以,这里所说的套路也是针对大部分情况,也就是最坏情况,对于一些个例,比如经典快排,我们虽然也是使用大O表示他们的复杂度,但是,其实是一种均摊的复杂度。 好了,让我们看看计算算法复杂度的套路到底是什么吧。 套路我将计算算法复杂度的套路归纳为以下五步:
比如,对于在数组中查找指定元素的操作:
所以,在数组中查找指定元素的时间复杂度为O(n)。 OK,使用这种方式可以很快的计算出算法的复杂度,也不需要进行额外的计算,非常快捷高效。 常见的复杂度上面我们说了,复杂度的计算就是计算与输入规模n的关系,所以,我们想想数学中关于n的函数就能得出常见的复杂度了,我绘制了一张表格:
在这张表中,复杂度是依次增加的,可以看到常数复杂度O(1)无疑是最好的,让我们用一张图来直观感受下: 后记本节,我们一起学习了复杂度分析的套路以及常见的复杂度,到目前为止,我们不管是举例还是讲解基本上都在说时间复杂度。 那么,空间复杂度又是什么呢?空间与时间之间如何权衡呢? 下一节,我们接着聊。
|
|