时间复杂度理解不了?看看这个吧!

小白:庆哥啊,这个复杂度到底是个啥啊,我在上大学的时候学这块的时候就很懵:joy:,不知道是个啥,理解起来很费劲,所以当时也没有好好学习,自己的数据结构与算法这块一直比较薄弱,准备好好再学学数据结构与算法嘞,这一个复杂度都难住我了

庆哥:的确啊,虽然就三个字,但是理解起来也确实有点费劲,我当时学习的时候也是有点理解不了,感觉看了很多解释,总觉得迷迷糊糊的,还是不知道到底是个啥?:joy:

小白:嗯嗯,是的,我也上网搜了很多的关于复杂度的分析的文章,有些文章觉得越看越迷糊,看着看着就看不下去了,然后我就去看看评论,想着会有人跟我一样觉得看不懂,结果评论都是“写的很好”:joy:,顿时觉得自己是不是太笨了 。

庆哥:哈哈:grin:,太真实了,那今天咱俩就来好好学习下这个复杂度吧,绝对让你对复杂度有个全新的认识:sunglasses:

一起攻克复杂度吧

小白:嗯嗯,那我得好好学习了,复杂度一直困扰着我,还真的是复杂啊:sweat_smile:,对了,有啥不明白的可是随时提问你的哦,还请庆哥赐教:grin:

庆哥:小事小事,那咱开始吧,首先我们要知道我们学习啥,那必须是复杂度啊,咋一看,三个字“复杂度”,应该是个名词吧,所以嘞,首先我们得知道,它一定有他本身的概念,那好,我们看看复杂度是怎么定义的,怎么看?必须是百科的解释啊,来,一起看看:

在计算机科学中,算法的时间复杂度(Time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

看看,明白不?

小白:说实话,看到这个真的有点懵啊:smile:,时间复杂度?跟复杂度一样吧,什么函数,大O,低阶项,渐进时间,这都是啥跟啥啊:joy:,是不是涉及数学啊,我数学可一直都不好啊

庆哥:别说你,我刚开始看这个的时候也是一脸茫然啊 ,也许真的是因为咱俩太笨了:smile:,怪尴尬:joy:,不过我觉得这个解释虽然很正确,但是有点官方,对已经只是到啥是时间复杂度的来说很不错,但是对于新手和那些对复杂度概念有疑惑的人来说,真的不算友好,本身就理解的云里雾里,看这个更迷茫了:smiley:

小白:对对对,也许它说的很对,但是这样解释就是觉得好迷茫,不知道到底是个啥:tired_face:,庆哥快给我解释解释吧:laughing:

复杂度小探

庆哥:嗯嗯,那接下来,我就把我的理解用大白话给你解释一下吧:wink:,首先嘞,针对你上面的一些疑问咱先来说说,你要知道,咱们这里要探讨的复杂度是数据结构与算法里面的概念,为啥要这样说,中华文字,博大精深,一样的字放在不同的场景里,那含义就不同了,所以咱必须先明确,我们这里讲的 ==复杂度是数据结构与算法中的概念==

好了,知道这个之后,我们还要知道,我们这里说复杂度,更为准确的来说是==时间复杂度==(还有空间复杂度嘞),所以后面咱们不说复杂度了(避免有歧义),就说时间复杂度(因为时间复杂度相对来说比较重要),先跟你说一声,这个时间复杂度是针对于算法的,所以再全面点,我们实际应用中会说成==某个算法的时间复杂度==

小白:是啊,复杂度,哎不对,是时间复杂度:grin:,就是跟算法有关的,数据结构与算法是块超级难啃的骨头啊:joy:

庆哥:的确,==数据结构与算法真的很重要==,按时不可否认,真的不容易,很多程序员这块的技能也都不是很强,数据结构与算法这块牛了,那都是大神级别的啊:grin:,很多小渣渣早就放弃了,根本学不会啊:joy:

小白:这太扎心了:grin:,我好难啊

庆哥:虽说数据结构与算法有一定难度,但是还没有到了那种难得学不会的地步,需要你==多花时间,多思考多练习==,很多人第一步都不敢迈出去,当然难了

小白:嗯嗯,确实,很多人听到数据结构与算法,心里不自然的就觉得好难,然后就没有学下去的欲望了,首先就被自己吓到了,我要迈出第一步,跟着庆哥:joy:

庆哥:哈哈,可以可以,我的这块也是比较薄弱,咱们共同共同学习,那咱接着上面的说,经过上面说的,我们现在知道了,我们要搞定的就是时间复杂度,至于什么大O,低阶项的,咱们一步步来。

理解时间复杂度的前提

那时间复杂度到底是个啥呢?我个人觉得啊,要想理解什么是时间复杂度,我们先要知道什么是算法,为啥,因为时间复杂度就是针对算法才有的一个概念,注意啦,我开始慢慢分析什么是时间复杂度了哦:grin:

小白:嗯嗯,我在注意听着嘞:grinning:

庆哥:好的,千万别走神:sunglasses:,为啥说理解时间复杂度的前提先要搞明白算法是啥呢?举个例子,比如有人要给你介绍对象,你这人嘞比较在意身高,所以你就问“那货多高啊:joy:”,别人说差不多一米6左右吧,这个时候你就知道她多高了,这个身高就是衡量一个人的,这个好理解吧,而这个时间复杂度就是用来衡量一个算法的。

你想想,为啥你要问身高,因为你比较在意身高,比如说身高达到一米六就是你的标准,那达到这个标准就是好啊,达不到就是不好,如果人家才一米五,你肯定说,不好,身高不行:joy:,所以身高也作为你衡量一个人好不好的指标,那对于算法嘞,一个算法也有好不好的说法,那用啥来衡量一个算法的好坏呢?

小白:我知道,时间复杂度:grin:

庆哥:嗯嗯,说的非常对,我们就可以用时间复杂度来衡量一个算法的好坏,当然,你衡量一个人的好坏,可以有很多指标,身高只是其中之一而已,同理,对于算法的好坏,也有好多指标,时间复杂度也只不过是其中之一罢了,像空间复杂度也可以来衡量一个算法的好坏,不过嘞我们这里主要探讨的是时间复杂度对算法的影响。

小白:庆哥啊,不是要说什么是算法吗,这里好像把什么是时间复杂度给讲讲了吧:grinning:

算法是啥

庆哥:哈哈,别着急,到了这里,你应该知道了,==时间复杂度是用来衡量算法的一个指标==,那啥是算法嘞?

小白:说实在的,我对算法也有点迷迷糊糊的,觉得算法就是一种方法吧:grin:

庆哥:其实吧,概念性的东西没有个定性答案,所以,按照你的理解没啥问题,所谓算法,当然咱这里也是针对数据结构与算法这块说的,它就是你解决问题采用的一种方式方法而已,我们这学编程的,终究是要落实到代码中的,在代码里来说,不同的算法,也就是你实现的代码不一样,但是达到的目的是相同的,用我们生活中的例子来说,那就是条条大路通罗马啊

就像这个图一样,我们从起点到终点,可以选择的路线有很多,但是我们直观来看,图中红色的路线是最近的,其实这里拿到编码中来说,每一条路线都可以说成是一个算法,那这里的好坏就是哪个近哪个算法好啊,这应该没啥难理解的吧。

这里的路线的远近就可以看成是时间复杂度,路线近,我们可以说时间复杂度小,算法就好,路线远,时间复杂度就高,算法相对来说就不好。

那为啥又说衡量一个算法的好坏,时间复杂度只是其中一个指标呢?难道这里的红线路线就是最好的吗?比如我们考虑道路问题,看下面的图,红线虽然近,但是路不好走,黑线虽然远点,但是路好走,综合下来,黑线是最佳路线。

所以说,时间复杂度并不能作为一个衡量算法的唯一标准,因为还有其他影响算法的因素,只不过,时间复杂度的影响比较大,我们常规讨论算法的好坏的时候经常使用时间复杂度来苹果。

那么,说到这里,你知道了啥是算法和时间复杂度了吧?

小白:嗯嗯,对他们的概念比较清晰了,其实算法这个玩意就是一个怎么做比较好的问题吧:grin:

庆哥:是啊,所以算法也涉及到思想层面,上升到这个高度就有难度,值得研究了,因为怎么找一个最佳选择,也就是最好的办法是需要费脑筋的,有的人能想到,有的人就是想不到:joy:

小白:哈哈,是这样啊 ,这里也知道了时间复杂度是用来衡量算法的一个指标了,也就是清楚概念了,不过不是有什么大O啥的吗?就是它咋用啊:joy:

怎么表示时间复杂度嘞

庆哥:不着急,咱继续,经过上面的讲解,我们大致清楚时间复杂度的概念了,以及它有啥用,那么应该怎样来表示时间复杂度了,我们上面举过身高的例子,那表示身高可以用多少多少cm啊,也就是160cm,那么时间复杂度该怎么表示嘞?

小白:这个我知道,叫什么大O表示法,经常见表示哪个算法的时间复杂度是O(1)啊,或者O(n)之类的。

庆哥:对的,就是用这种方式来表示时间复杂度,那你知道啥是大O表示法吗?

小白:这个就有点迷惑了,只知道这样表示,但是要说啥是大O表示法,就有点懵:joy:

庆哥:那咱来看关于大O表示法的一个概念解释:

若存在函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n) 的同数量级函数。记作T(n)=O(f(n)),称为O(f(n)),O为算法的渐进时间复杂度,简称为时间复杂度。 因为渐进时间复杂度用大写O来表示,所以也被称为大O表示法。

怎么样,看得懂不:grin:

小白:说实话,懵

庆哥:别说你懵,我也懵:joy:,没办法,咱们数学差啊,当初学数学的时候,有些概念就是理解不了,感觉说的好绕,那啥是大O标识法嘞,我觉得吧,没必要去纠结它的概念性问题,你只需知道大O标识法的形式就是==O(n)==,啥事大O啊,就是大写字母O啊,然后一个括号,括号里面一个数,这个数可以事已知的,比如说1,其实也就只有1,也可以事未知的,比如n,也可以是2n,3n或者是n的平方(n^2)等等,反正未知的就是跟n相关的函数。

大O表示法为啥是n

小白:有个疑问啊,这里为啥是n呢?:sweat_smile:

庆哥:当然,这个n只是表示个未知数,我们之前表示未知数通常是x和y之类的,这里使用n只是个约定俗称的事,也就是习惯成自然:joy:,大家之前都这样表示,于是干脆就这样吧,使用n来表示,其实吧,这个也跟我们写代码有关,比如我们写一些循环代码,经常出现n,像这样:

public static int test2(int n) {
		if(n<=1) return n;
		
		int first = 0;
		int second = 1;
		for (int i = 1; i < n; i++) {
			second += first;
			first = second - first;
		}
		return second;
	}
复制代码

看到没,这段代码中使用的n,对了,你知道怎么计算时间复杂度的嘛?

小白:就是如何计算一个算法的时间复杂度嘛?我就不会这个:joy:,看了不少文章,好多都是在介绍啥是时间复杂度,可是就是不告诉我时间复杂度该怎么计算

如何计算时间复杂度

庆哥::joy:,那咱来说说,因为跟你说了这个怎么计算时间复杂度的之后,你就会更明白为啥是n了,首先,你有没有觉得时间复杂度跟时间有关:grin:

小白:必须啊,人家就叫时间复杂度,我之前还以为时间复杂度就是多少多少秒之类的:joy:,结果是O(n)什么的 ,这是咋算出来的啊

庆哥:你这样理解也正常,那是因为我们对时间这个概念固化了,想着时间那就是时分秒来计算的,这些都是时间单位,是我们熟知的时间单位,但是还有可能时间不是一时分秒来计算,时分秒是确切的,也有可能是抽象的,没什么意思呢?我们弄个代码来看下:

public static int test(int n) {
		
		return n++;
		
	}
复制代码

咋样,这段代码简单吧,就是给定一个值,然后加一返回,我们了解过什么是算法了,这段代码其实就是一个算法,只不过超级简单,它是用来计算一个值加一之后的结果的,那么我们来看怎么算它的时间复杂度,该怎么计算呢?

我们先约定好,在方法体内,每执行一次操作,我们记作1,也就是花费了一个时间单位,你看这里并没有说是1秒还是1分,就说是一个时间单位,我们下面来看这段代码。

在这段代码中,就有一行代码,也就是:

return n++;

它就算做一次操作,所以这里花费的是1个时间单位,也就是1,那它的时间复杂度就是O(1)

小白:为啥啊?:joy:

庆哥:不着急,我们继续看下面的代码:

public static int test(int n) {
		
		n=+5;
		return n++;
		
	}
复制代码

与上面代码不同的地方是这里多了一行代码,把给定的值加上5,我们来看它的时间复杂度,首先是n=+5这行代码被执行一次,花费了1个时间单位,下面那行代码也是执行一次,也是花费了1个时间单位,那么总的就是花费两个时间单位,所以它的时间复杂度就是O(1),怎么样,有没有发现点什么啊:joy:

小白:无论是1个时间单位,还是2个时间单位,他们的时间复杂度始终是O(1),这是不是意味着,==只要是这些常数个时间单位,时间复杂度始终都是O(1)== 啊:grin:

庆哥:对,很对,也就是说,只要代码的总执行次数是个常数,那么时间复杂度就是O(1),我们紧接着来看O(n)的是咋回事,看下面这段代码:

public static int test(int n) {
		int sum = 0;
		
		for (int i=0;i<n;i++) {
			sum=+i;
		}
		
		return sum;
		
	}
复制代码

这里有个for循环,我们看看它的时间复杂度怎么计算,首先第一行代码int sum = 0执行一次,花费1个时间单位,重点在下面的for循环这块,因为这里的n是个不确定的值,经过分析,发现for (int i=0;i<n;i++)这行代码会执行n+1次,也就是会花费n+1个时间单位,循环体内的sum=+1这行代码则会执行n次,也就是会花费n个时间单位,然后最后一行代码会执行一次,就是花费1个时间单位,总的来说就是: 1+n+1+n+1 = 3+2n,也就是总共花费3+2n个时间单位,那么它的时间复杂度就是O(n)。

你看看,觉得这个是规律是啥:sunglasses:

小白:这里得出的总时间单位就像函数一样,比如f(n)=3+2n,不过我们之前喜欢用x,也就是f(x)=3+2x,只不过这里是n,看这里应该是把常数项去除,然后系数也去除,只保留个n,那么如果是f(n)=3+2n^2的话,时间复杂度是不是就是....

是不是就是O(n^2)啊:grinning:

庆哥:很聪明啊,确实是这样,这里有个比较官方的解释,也就是按照下面的规则去计算时间复杂度

  1. 如果运行时间是常数量级,则用常数1表示
  2. 只保留时间函数中的最高阶项
  3. 如果最高阶项存在,则省去最高阶项前面的系数

这个明白吧,举个例子,比如f(n)=3+2n^2+5n,那么3就是常数项,5n就是一阶项。 2n^2就是二阶项,在这里也是最高阶项,那么按照规则时间复杂度是哈?:sunglasses:

小白:这还是O(n^2)吧:grin:

庆哥:咋样,现在知道怎么计算时间复杂度了吧,你有没有总结什么规律呢?

总结

小白:经过上面那几个例子,我觉得这计算时间复杂度,主要就是看代码中的每一行代码一共执行了多少次,不确定的就是n,然后按照那三条规则来确定最终的时间复杂度,所以重点就是计算每行代码执行了多少次,是不是这样:sweat_smile:

庆哥:是的,就可以这样理解,就像你说的重点就是看每行代码一共执行了多少次,不过有些复杂的代码是不容易算出一共执行多少次的,容易算着算着就迷糊了

小白:哈哈,我也正在思考这个问题呢?咱这里举的例子比较简单,容易计算每行代码执行多少次,但是代码一旦比较绕,比较复杂那就不容易了吧:joy:

庆哥:确实啊,不过随着我们后续的学习,我们会学习一些经常使用的算法,那么这些算法的时间复杂度会直接给出,我们记着就行了,比如我们看看这个图:

这个就是不同时间复杂度的一个函数图,可以简单理解,越陡的花费时间单位越大,那算法性能也就越差,这个我们只要学过数学,一般都能理解吧:grin:

小白:嗯嗯,是的,这个还是能够明白的,你说有些常用算法的时间复杂度是给出的,有哪些呢?

庆哥:这个啊,我觉得还是随着我们后续的学习去逐步的了解,比如学到哪个算法,需要分析时间复杂度的时候我们再去说,那样我们记忆的才牢固,不然,这里即使和你说了,也会很快忘掉:joy:

小白:嗯嗯,有道理:grin:

庆哥:对了,知道大O表示为啥是n了吧:sweat_smile:

小白:嗯嗯 知道了:grinning:

感谢阅读

大家好,我是ithuangqing,一路走来积累了不少的学习经验和方法,而且收集了大量的精品学习资源,现在维护了一个公众号【 编码之外 】,寓意就是在编码之外也要不停的学习,主要分享java技术相关的原创文章,现在主要在写 数据结构与算法,计算机基础,线程和并发以及虚拟机 这块的原创,另外针对小白还在连载一套《 小白的java自学课 》,力求通俗易懂,由浅入深。同时我也是个工具控,经常分享一些 高效率的黑科技工具及网站

对了,公众号还分享了很多我的学习心得,可以一起探讨探讨!

关注公众号,后台回复“庆哥”,2019最新java自学资源立马送上!更多原创精彩尽在【编码之外】

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章