内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

算法的复杂度

2018-11-30 20:06 出处:清屏网 人气: 评论(0

对于任何一个程序来说,都可以从三个方面进行分析,分别是 输入处理输出 ,也即 IPO (Input、Process、Output),这种分析方法对硬件和软件程序都是适用的。

数据的来源(Input):可以是硬件传感器收集的,也可以是从网上爬取的…。数据的输出(Output):可以显示在网页上,安卓APP上,电子屏幕上…。而最重要的是程序处理,可以对数据进行简单的处理,也可以对数据进行挖掘…。

就拿最简单的 Hello World 程序来说,也是由这三方面组成的,输出函数(处理)帮你处理输入的 “Hello World” 字符串(输入),然后再帮你将这些字符输出显示到控制台上(输出)。大到现在热门的技术,物联网、大数据,人工智能等,做的也无非都是上面三个方面内的事情,关于这些,读者可以思考一下。

评价一个程序的复杂程度,关键也是看程序中处理数据的这部分,对数据处理就要用到算法了。什么?你说你没有用过算法,其实从你编程开始的第一句 “Hello World” 就注定编程和算法分不开了,一个输出函数背后也同样有算法呀,只是你在使用算法的时候并没有意识到你在用算法罢了(嘿嘿,就是这么神奇~)。

算法是一个程序的灵魂,就好比没有蛋的泡面是没有灵魂的一样。一个好的算法可以有很多的应用,比如在美剧《硅谷》中,主角发明了一种压缩算法,将它用在音乐、云存储、视频等方面都大获成功。虽然故事是虚构的,但是在一方面也说明了算法的重要性。

分析一个算法的复杂度,也是在分析一个算法的好坏优劣,简单高效的算法才是我们应该追求的,而复杂低效的算法则是我们需要改进的。算法的复杂度包括 时间复杂度空间复杂度 ,下面将用尽量少的概念来帮你搞懂这两个度。

1、什么是算法的时间复杂度?

讨论算法的时间复杂度,也是在讨论程序使用该算法运行的时间。经常听到身边的同学说我的电脑好慢呀,打开个软件都要一分多钟,急死人了。这从算法的角度看,只能说电脑硬件比较差,不一定说程序写的很垃圾(当然也有可能有程序的锅),同样的程序可能在别人配置高的电脑上打开就很快。所以你看单纯从程序运行需要的时间长短上,并不能反映算法的优劣,因为这和运行的设备也有很大关系(计算机计算主要用到的是 CPU 和 GPU)。

算法的时间复杂度并不能以具体的时间数值为单位(如1秒钟,1分钟等),那算法复杂度中的时间单位是什么呢?这个时间单位其实更像是程序中执行的次数或者步骤数。

举个栗子,当你忘记东西放哪里了,可能会把所有的抽屉都找一遍,假如你有 n 个抽屉,那么找完 n 个抽屉就可以找到你的东西了,每个抽屉都找了一遍,就找了 n 遍。算法的时间复杂度(运行时间)用大 O 表示(不需要关心大 O 表示法怎么来的,就是个名字),把你找东西的这个过程写成程序,算法的时间复杂度就是 O(n),是不是感觉算法其实就在我们中间。

在上面这个例子中,最好的情况是,当你找完第一个抽屉,你就找到你的东西了,这当然是最好的了,用大 O 表示法表示就是 O(1),但是这样的情况存在偶然性,并不能代表算法的复杂度;最坏的情况是,直到你找完最后一个抽屉,累的要死,你才找到你的东西,用大 O 表示法表示就是 O(n)。位于最坏和最好之间的情况是,当你找到中间一个抽屉时,你找到的你的东西了,用大 O 表示法表示就是 O(n/2)。

那么这三种情况,哪一种应该代表算法的时间复杂度呢?最好的情况毕竟是小概率事件,不具有普适性,肯定是不能代表算法真实的时间复杂度。平均的情况,确实在一定程度上可以反映出算法的时间复杂度,但是学过数学的我们知道,平均值容易受到极端值的影响(在评委打分时也经常是去掉最高分和最低分),所以平均情况也不是很合适。而最坏的情况却可以给我们一种保证,我们心里也可以有一个预期,这个算法在最差的情况下表现如何(就像我们做事也常常考虑最坏的情况一样),所以我们 用最坏情况下的时间复杂度来衡量算法的时间复杂度

对于大 O 括号内的参数(或者称为操作数)的系数,往往被我们主动忽略,如一个计算出所需次数为 n/2 的算法,用大 O 表示法表示是 O(n),而对于计算次数是个常数(如 1,5, 9)的算法,用大 O 表示法表示都是 O(1),这点是需要我们注意一下的。为什么这样做呢?因为对于计算次数是 n2/2 + n/2 + 5 这样的算法,起决定作用的是 n,而不是 n 前面的系数,当 n 为无穷大时,n 前面系数的影响就微不足道了,最终这个算法的时间复杂度用大 O 表示法为 O(n2 + n)。

2、什么是算法的空间复杂度?

程序运行时肯定是要消耗空间资源的,寄存器、内存和磁盘等。输入和输出这两部分占用空间是必需的,所以程序处理的空间指的是程序运行算法时所需的那部分空间。先来看个例子,交换两个数的值,相信大家都做过吧,一般的方法是找一个中间变量存储其中一个数的值,再让一个数等于另一个数的值,另外一个数等于中间变量的值,就像下面的伪代码这样。

// 交换 a 和 b
temp = a
a = b
b = temp

栈这种数据结构,我都应该很熟悉,特点是先进后出(FILO),交换的这两个数肯定都是要放在栈中的,但由于引入了中间变量实现,所以在程序栈中还要有中间变量的空间,一个变量占用一块栈空间(想象一下),我们用一个格子来表示,就像下面这样,中间变量也要占用一个格子(其实这个格子在其他栈中叫做 ,如 Java虚拟机的本地方法栈和虚拟机栈,帧又是一种数据结构)。

因为这个值交换算法用到了中间变量,而中间变量又要占用一个格子,所以这个算法的空间复杂度用大 O 表示法表示就是 O(1)。

相比较而言,算法的空间复杂度比较简单,所以我们在讨论一个算法时,更多的是讨论算法的时间复杂度。

3、一些常见的大 O 运行时间

  • O(1),如 y = x + 1,只需要一次计算便可得到结果。
  • O(logn),也称为对数时间,如二分查找算法。
  • O(n),也称为线性时间,如我们上面例子中的找东西,用的就是简单查找算法。
  • O(n*logn),如快速排序算法。
  • O(n2),如选择排序算法。
  • O(n!),如著名的旅行商问题。

这里提到的算法,将在后面的文章中讨论,感兴趣的小伙伴不妨先搜索了解一下。

上面几种大 O 运行时间,反应在图中如下(注意:图中曲线并不一定从原点开始画的,只需要知道算法运行时间的大概走势就可以了):

算法的速度,指的并不是时间,而是增速,反应的在图中就是曲线的斜率,可以看到,随着输入的增加,有的算法所需要的时间越来长,也就是使用这种算法的程序会越来越慢。

4、小结

算法的复杂度和需要的时间、空间都有关系,我们更多谈论的是算法的时间复杂度, 算法的时间复杂度不是以秒为单位算法运行的速度是从其增速的角度度量的 ,也即是输入越多,算法运行的时间改变的快慢。一个好的算法应该是时间复杂度和空间复杂度都比较低,通俗的说就是花最少的时间和精力达到最好的效果,但是这两样往往是很难同时做到的,这就需要我们牺牲一样来做到尽可能的更好。

分享给小伙伴们:
本文标签: 算法

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号