写点什么

快速理解大 O 复杂度

用户头像
ES_her0
关注
发布于: 16 小时前

有人说你也是算法的门外汉怎么就胆敢写文章来教别人了呢?谁说写文章是为了教别人呢?我又不是老师,写文章算是对自己的一个总结,从自己学到自己写出来,假装会有读者来看,我的责任是让对方能看懂,这就足够了。

算法入门的时候几乎所有书籍和博客都会说,用大 O 来表示算法复杂度。确实,衡量一个东西的好坏需要一个标准或者规范,大写的 O 就是这个规范。算法的复杂度有两种定义:时间复杂度和空间复杂度。这两者都是用大 O 来表示。在大多数时候,我们更关注的是时间复杂度,空间上正常是较为宽裕的,一个算法很难产生堆栈的溢出。

初学者一眼看到 O(logn)之类的符号时,曾经被高等数学支配的恐惧就油然而生,心理上首先就破防了。大可不必,心理的畏惧会让我们一事无成。其实一共用来表示的符号只有这几种:O(1),O(n),O(n^2),O(logn),O(nlogn)。剩下的就是分析什么情况下是哪一种复杂度,复杂度的表示有什么用呢?在写算法的时候几乎没用,但在和别人交流算法的时候有用,可以理解为算法交流的通用语言。

现在来解释一下分别是什么场景:

O(1)

无论什么输入下,这个算法只需要执行固定的行数。这一般出现在值交换这样的简单算法上,因为一旦涉及到数组、列表之类的处理,长度未定所需执行的行数肯定也未定。

O(n)

这就很好理解了,比如遍历一个列表,列表有多长就要循环多少次,这个 n 就代表长度。

O(n^2)

正常情况下,这是比较糟糕的情况。因为有了指数,所需要的执行的行数会指数级上升,长度 n 越长,所需承担的时间成本最终会高的难以想象。循环嵌套循环就会产生 n^2,再嵌套一层就是 n^3,因为 n 个元素每个都要在下层循环 n 次,所以是 n * n。

O(logn)

可能很多人不是被前面的几个吓到,而是这个。log 在数学里是对数,应该是高中数学,可能现在已经是初中了。有指数,相对应的就肯定有对数,这里默认是 log2^n,底数为 2 的对数,简写为 logn。假如 log2^n = x,那 x^2 = n,这是一个相互转换的简单例子。什么场景下会是 logn 的复杂度呢,就是每一步执行都会减少一半的元素,比如二分查找,每次从中间取值之后都会定位到某一个半区,从而另一半的元素就不是我们的目标区域,直接范围变成原来的 1/2,这便是对数时间。

O(nlogn)

有了上面的基础,这个就很好理解了。还是说二分查找,查询一个数组需要 O(logn),那查询 n 个数组就是 O(nlogn)了。

对大 O 的恐惧是不是有所减少呢?

用户头像

ES_her0

关注

还未添加个人签名 2018.03.21 加入

还未添加个人简介

评论

发布
暂无评论
快速理解大O复杂度