算法系列---衡量的标准之时间复杂度
前言:
说到算法,就要聊一聊算法的复杂度了。什么是复杂度?为什么要知道复杂度?如何衡量复杂度?了解这些,是我们写好算法的基础。下面我们就来聊一聊算法世界的标准,算法的复杂度。
什么是算法复杂度,听到这个名字,就是问号三连???
1.是什么?
算法有好坏之分,衡量算法好坏的就是算法的复杂度。算法的复杂度分为时间复杂度,和空间复杂度。分别从不同的维度来说明衡量算法的好坏。
2.为什么要知道?
很多人觉得算法很难,而且在工作中基本不会用到,就对算法望而却步。但是学习算法可以让我们更有逻辑,而且在数据量大的时候(比如双十一购物的时候),算法就显得尤为重要了。学会算法,日常写效率高的代码,还可以对算法娓娓道来,让小姐姐对自己刮目相看,它不香吗,代码厉害的程序员真的是超级帅!
3.如何衡量?
说到衡量算法的标准,就要说到时间复杂度和空间复杂度了。今天呢,就先说一说时间复杂度
。
故事是这样的,话说从前聪明的孩子,特别调皮的熊孩子,经常在课上捣乱,有一天老师终于忍无可忍,于是给熊孩子出了道题,算出1+2+3+4+5+…一直加到10000,算不完不许回家吃饭!老师以熊孩子会,从1+2=3,3+3=6…一直加下去,可能算到天亮都算法不完,老师心里正窃喜,结果几分钟后。熊孩子说,老师我算完了结果是50 005 000。老师心想,我读书多,你算这么快,骗不了我,结果一看到熊孩子的算法,把数字分成两组,首位相加1+10000,再看看一共有多少之后各样的和呢,10000/2,于是就有了(1+10000)*10000/2=50 005 000。
这个熊孩子就是著名的犹太数学家约翰 卡尔 弗里德里希 高斯,而他采用的就是等差数列求和的方法,被称为高斯算法。(故事参照《小灰算法》且与史实有出入)。
向开始的1+2=3…然后一直加下去的算法,肯定比分组算法的时间花费的多得多,这就是算法的时间上的差异,可以简单理解为算法时间复杂度。
那么真正算法的时间复杂度是怎么定义的呢?官方一点的说,有如下几个原则:
-
如果运行时间是常数量级,则用常数字1表示。
举个例子:T(n)=2,则时间复杂度为T(n)=O(1) -
只保留时间函数中的最高阶项。
举个例子:T(n)=2n²+2n,则时间复杂度为T(n)=O(n²) -
如果最高阶项存在,则省去高阶项前面的系数。
举个例子:T(n)=2logn,则时间复杂度为T(n)=O(logn)
T(n)=2n,则时间复杂度为T(n)=O(n)
所以呢,算法都是没有系数的。
那么上面的例子中算法的时间复杂度,谁执行时间长,谁更节省时间呢?当n最够大时,可以看到:
O(1) < O(logn) < O(n) <O(n²)
当然编程的世界中,有各种各样的算法,除了上面的例子,还有很多形式,比如O(n³)等等,后面还会有更多的时间复杂度,等着我们去探索和发现。
小结
今天的算法分享就到这里了,下一篇算法系列会分享空间复杂度,欢迎大家评论、分享,多多关注。