00:00
下面我们来看一下时间复杂度,时间复杂度首先呢,关于时间复杂度,我们先有三点要给他说清楚,第一点呢,就说一般情况下。算法中的基本操作语句重复执行的次数是问题规模N的一个,呃,某个函数用TN表示,这个是不是就是刚才我们讲的?呃,时间频度对吧,那么如果有一个辅助函数。那么使得当N趋近于无穷大的时候,这个TN它的这个表达式和FN的这个表达式,他们当这个N无穷大的时候,它们的极限值为一个不等于零的常数。什么意思啊,就说我这个T不是一个表达式吗?FN呢,是不是也是一个这个FN假设是一个函数啊,这个N呢,它也无穷的无呃无穷大,那么这个时候呢,TN这个表达式和FN这个表达式呢,它们是趋近于一个不等于零的常数。
01:05
在这种情况下,我们就称为FN是TN的一个同数量级的函数。大家明白这什么,就说这两个,呃,这两个呢,是同一个同数量级的。那么这个时候,我们就可以把TN记作O。FN,当然这个FN到底是个什么样的一个表达式,要要根据实际情况来看,也就是说。TN它可以简写成,就好像刚才大家还记不记得我们曾经有一个叫TN等于N加一的。N加一的这这是它的一个表示,假设我们有一个FN。FN,它等于什么呢?它就等于N。你明白我是什么什么意思吧,那么这个时候TN。TTN去除以,除上这个FN,就相当于是FN去除以N,这个时候他们是不是就无限的接近于一个值什么呢?接近于一。
02:05
那这个时候我们就说FN是TN的一个同数量级的函数,那这个时候呢,我们就可以把这个TN减记成什么呢?就可以直接写成哦。这个FNFN是不是就是N呢,就这样子的一个意思。明明白了吧,大致就这样子啊,然后呢,Ofn为算法的渐进时间,就是说是相当于是把这个时间频度的表达式。找找到它对应的这个同数量级的函数简写,那么这个就变成的是这个AO里面的这个东西,就说大家看到这个玩意儿就叫什么呢?就叫算法的渐进时间复杂度,简称时间复杂度。明白啊,那现在我们举几个例子吧,比如说TN不同,但是时间复杂度是可能相同的。你比如说。
03:00
你比如说,你比如说我们现在举个例子,这有一个,这有一个TN等于N平方加上七乘以N加六,这个是不是一个时间频度的表达式?那么这也有个TN,它是3N的3N的平方加2N再加一二。同学们可以看到这这两者他们的TN是不一样的,表达式是不一样的,但是他们复杂度都为N的平方。为什么呢?因为刚才我们讲过,常数项是可以忽略的。第一次项是可以忽略的,系数是不是也可以忽略,最后是不是他们都如果如果这样比比较下来是不是?假设我有一个叫做FN的,注意听这句话啊,假设有个FN的辅助函数,它的。表达式就是N的平方是不是?TN和FN相处,最终他们是趋随着N值的变大是不是?呃,他们是趋近于一个常数项。
04:02
是不西式好,这个时候呢,我们就用这个FN表示它的时间复杂度,就简写成on的平方,就相当于在这在这个地方加了一个大O,就是这个就相当于是O的平方。明白,所以说TN对应的它的这个实间,否则就它这个也是一样的道理,只是不一样的是我们把这个高次项的这个系数也怎么样忽略掉了,是不是前面我们讲过这个东西啊,所以前面为什么我说时间频度要认真去理解,那么现在呢,我们来看一下怎么去计算,怎么去计算一个时间复杂度的方法呢?我举个例子,比如说。我们就以这个为例。我们就以这个为例,它先用常数一来替代运算时间频度中的所有加法的,呃,这个常数,比如说这个呢,我们先把它改成了这样一个东西。
05:00
这这样一个东西,然后拿到这样一个东西过后呢,第二步修改运行次数函数中的这个修改这个函数保留最高阶的相处,也就是说。呃,这这个东西又改成什么呢?改成了TN,注意听这句话啊,TN只保留高次项,就是N的平方。因为7N和这个一,一次常数应该又被忽略,第一次项也被忽略了,最后去除高阶高最高阶的系数,那也就是说这当然这个系数它本身前面是个一,那那去不去都是一样的道理。是不是这意思?啊,那那这样子,他把他把他这个去去除最高最高阶的像素,不就这个就还是变成TN。TN等于这个N的平方嘛,啊,这个N的平方啊,这这写的不对,N的平方。变成N的平方,这边呢也是一样的。
06:01
因为他前面这个系数,唯一你去了还是他。那这个时候我们就把这个记成什么了吗?好,就把这个TN这个就继承了,就说这个T,这这个上面这个TN,它对应的时间复杂度就是大写的O。N平方就来了,就这就这样推推算出来的啊,就这样推算出来的,那同样你你可以用这个方法来推这个三的平方,你看如果是三的平方在这是不是这这方应该是三,把这个三去掉。是是不是这个三去掉过变成N的平方,这这就能看到比较明明显明白吧,为什么可以去掉这个三呢?因为大家想嘛,随着这个N值的变大,是不是它也趋趋近于一个。那不等于零的一个常数,所以说这这个呃,这个N的平方呢,是可以去,呃,跟它是一个同数量级的函数,就这么来的啊。大家理解一下怎么做出来的?好吧,我一步一步的给大家演演示了一下,那现在呢,我们来看一下这个常见常见的时间到底有哪些,这个是同学们一定要去掌握的啊。
07:07
就说我们算法里面常用的时间符当中有八个,八个当然不止这些,就是常见的有八个,第一个呢叫常数阶。常数阶其实就是刚才我们举的例子,就是说他一句话就搞定,后面我们还会举例说明对数阶,比如说这个对数阶叫什么呢?Log,以二为底的N的对数。这个大家还在上初中的时候,应该是学过这个东西的,这个怎么念啊,叫log,以二为底的N的对数,那么二是底数,这个二是底数,N是什么呀?N是真数。那么整个这个值叫什么呢?叫对数。这个二是底数是不是底。是底,底数N是N叫什么?N叫增数,还还有印象吗?同学们学学过数学啊,增数,那么整个这个结果叫对数。所以这个就叫对数键,那么至于这个底数是多少,是二还是三,还是五还是十,这个要根据具体的算法而言,待会我们举例说明一会就明白了。还有一个叫还有一个叫做线性阶,线性阶呢就是on,就说你这个N是多少次,N是多大,随着N的变大呢,它的这个执行的语句的次数做相应的变化,就线性的。
08:23
就这这条线看到没有啊,这条线那么还有一个呢,就是线性对数阶,线性对数间就是前面有一个,它是线性和这个对数相结合的一种算法,后面我们举例说明,还有一个平方阶。还有一个立方街,还有N次街。那么呃,我举个例子,什么叫平方间呢?比如说咱们双层就是嵌套循环,就是双层或循环,它就是一个立方啊平方间立方阶是什么呢?三层做循环就是立方阶。那K次方是多什么?K次负循环。啊,嵌套了K次的负循环,就叫K次方,那么指数阶这个很猛的啊,指数阶它是二的N次方,这个就很厉害了。
09:06
这个要尽量避免在我们算法中出现指数阶的这种时间复杂度。大家看一下,待会我做做个说明看,常见的算法时间复杂度呢,是从小到大这样子的。这个我写的顺序就是它的时间复杂度就是逐渐变大,比如说常数阶,它的时间复杂度最小的,最大的是谁呢?就是这个指数节最大。其他意思类推啊,比如这个是对数阶,线性阶就是对数阶其实还是一个比较不错的算法。线性阶也还可以,这个是线性对数阶,这个是平方阶,立方阶,K次方阶,这个是。呃,指数节其实还有一个,还有一个我没有写出来,呃,但是大家用的很少这个玩意。不知道有没有同学见过这个叫N的。
10:01
N次界,这个是这个是最最麻烦的,就是这个它的增长是最最快的,要尽量避免,那我这没有写,我就不写它了,好吧。那么大家看我这随着问题规模N的不断增大呢,上述时间复杂度不断增大,算法呢,执行效率就会降低,大家看这有一张图。大家有没有发现这张图很有意思,你们有没有发现这个,这我说了一句话,就是从图上中我们要尽量的避免指数阶的算法,大家看指数阶是这条线。大家有没有发现指数家有个特点,他在刚开始的时候啊,就当这个N的规模不大的时候,其实他还很OK的,对吧,他还很OK,但是大家有没有发现,当这个规模这个N到这个十一十二的时候,他已经猛的一下就上去了。看到没有,人家还在这呢,人家还在他上去了,那这大家可以想象,当我们这个值,当这个N到15的时候,这个指数该到哪去了。
11:01
到这个遥远的地方去了,看到没有,这个远远的超出了其他的时间复杂度,所以说对,只要在你的算法中出现了指数间,这个这个算法一定是比较慢的。一定是比较慢的,因为这个东西增长太快,假设到20人家还在这,他可能已经到哪去了,都已经超出我这个屏幕了,到这来了。而最稳定的是哪一个呢?显然常数也是最好的。比如说刚才我们那个求一加到N的这么一个算法,你用for循环,显然就没有用一条语句搞定这个常数间其实是最好的。所以说我们在写代码的时候,如果能用常数阶,这种时间复杂度是最OK的,那么次之就是对数阶。那么现在我们把这个长间时间辅要说完了,过后我们分别举几个例子吧,加深认识好不好?我们来看一下,因为空说这个。实验复杂大家没有印象,我举几个例子,大家认真听啊,有些同学呢,是听过实验复杂度,但是没有见过具体的,我们每个举个例子,大家看常数节OE,它是什么意思呢?就是说无论代码执行了多少行。
12:11
只要没有循环等复杂的结构,那么这个代码的复杂度就是一个常数键。大概。嗯,举个例子看这int I等于一,J等于二加加IJ加加,然后拼接,大家可能乍看一眼说哦,老师,不对哦不对哦,你,你是不叫仓数间,你不执行了五条语句吗?你要这么理解,我就没什么话可说的了啊,因为你要这么去想,就说随着这个I和J大家看,你I揭是I等于一,你执行五句话,你I要你要你I要等于20万。个十百千万,十万二十万,你I等于20万,是不是他还是五条,还是执行五句话就完事了。大家要这样去看啊,所以说上述代码之中,它消耗的时间这写错了啊,时间并不随某个变量的增长而增长,因那么无论这段代码有多长,即使有几万几十万行,都可以用OE来表示它的分量度,因为它并不属于你的变,它并不属于你的变化的这个变量的增长,而让这个代码的这个执行的这个次数变大。
13:20
你你有几万行,几十万行,那你有几行肯定必须执行了嘛,这不可能说你写了几万行代码就执行一次,他这说的词时间,时间复杂度,主要是跟你这个变量的这个规模有没有关系,明白我意思就好像刚才这个I等于一,你执五句话,你要I等于20万,那个200万,2000万,它也执行五句话,所以这个就叫常数街,理解吗?这个是最好的算法。好,这个讲完了,我们再来看下一个叫做对数阶,对数阶呢,我这举了一个,我举了一个例子,是log以二为底的N的对数,大家注意这个二不一定是,呃,每次都是二啊,也可能是三,也可能是四,也可能是十。
14:03
那我这为什么写个二呢?因为我下面这个算法刚好是成了一个二。注意听讲啊,那同学们看。我们我们首先呢,先把这个给大家做一个简单回顾,Log以二为底的N的对数,这个含义是什么?简单回顾一下,我这有一有个简单的一个案例,大家看一看啊,呃,同学们看这里。这有一个N等于A的X次方。A大于零,A不等于一,这个是初中我们学过的,这个叫什么呢?叫,即A的X次方等于N。这个是这个大家很好理解吧,就是A的X方等于N,那么反过来就叫什么呢?那么X叫做以A为底的N的对数,就这个X啊。它是以A为底的N的对数,那么记住什么呢?记住这个就说上面这个式子,如果以对数的方式来写,就是log以A为底的N的对数X,那么其中A呢叫底数,N叫增数,而X呢,叫做以A为底的N的对数。好,这个我就回回顾到这里,那么大家看这段代码。
15:11
看这段代码,这段代码你们有没有发现它有个while循环,但是它这个I呢,在它循环体里面是成了一个二。那大家想,在Y2循环体内,每次将I乘以二,乘完以后,I距离N就越来越近了,它可不是I加加呀,它是I乘以二。那么大家想一想,假设我们循环X之后,I就大于二了,这时就退出循环,也就是说二的X方等于N,那么N等于log以二为底的对数。那我举个最简单的例子吧,比如说我问大家,如果N等于幺零,二,四。大家理解我在说什么?假设我们这个N的规模是1024,请问这这个while循环一共执行多少次?按这个代码一共执行多少次?是不是执行log以二为底的1024次对应的对数,那等于十了吗?等于12的十次方不等于1024,所以说你虽然这个规模是1024,但实际上我这个执行代码其实是二的。
16:19
以你这个N规模的一个对数,所以这个就叫对数键。理解我的意思吧。好,这个我就讲到这了啊,如果还不理解的同学,把这个代码去看看,再不理解把初中数学拿出来看一下。好,下面呢,我们再看线细节,线细节也很好理解,就是这种负循环,单纯的负循环就是线细节,你比如说大家看这段代码。呃,我这个N假设是十,是不是你的这个时间复杂度。啊,时间时间复杂度这个O就。你N等你你看啊,它这个相当于这这个意思了,比如说你十,你N等于十,那就就是你要N等于20呢,就是20。
17:03
他直接跟你这个N的这个规模相关。没有其他的东西说,这段代码for循环里面代码会执行N变,因此它消耗的时间是随N的变化而变化,这这一类型的代码呢,就用O小O大写的一个O,一个小括号N来表示它的时间复杂度。那它的时间频度是不是这样写的,时间频度是实际上是N加一。这个N加一,最后推出来这个是对应的是O的N次,是不是以前讲过这个东西啊。我就不再多说了,这线性间那线性节减完的功能,我们再来看一个线性对数间,这个很好理解,线性对数间呢,它是这样子的啊,我后我这个地方没有写它的底数啊,没有写底数,大家看线性对数阶其实非常容易理解,它是将时间复杂度。呃,为这个线性,呃是时间复杂度,为这个对数阶的代码,循环N遍,这个就是所谓的线性对数阶,也就大家看这段代码。
18:04
这个代码是不是,如果只看里边。它的时间复杂度是不是一个对数键。是对数键吗?那肯定是对数键,刚刚刚刚讲过,但是他用负循环又套了一下说的这个N的变化。这个N呢?N,这个N的规模变化,其实前面会在这个对数间前面再加一个N。因为你里面是一个线性对数阶,外面是个线性阶,性相对线性阶去乘以一个对数阶,所以说就变成了所谓的线性对数阶。这种呢,复杂度肯定要比刚才线性阶要高了,因为它有个负循环了,好,这个就说到这儿啊,下面呢,我们再来看平方阶,平方阶其实特别好理解,就说你看我这有一个双层负循环。假如我们这个N等于十。你从这儿来看,它是双层负循环,里面是个I小于零,你再里面再再来一个I小于零,实际上它一共执行多少次,实际上是十乘以四一百次。
19:05
那假设我们这个N变成了二,变成了100。变成100,那么整个这个负循环是不是要执行100乘以100等于1万次?所以说这个呢,就是我们所说的平方键。OK,那同学们看啊,呃,我这就不再多说了,如果把N和把N改成M,那么它的实验辅导数就是M乘以N,就说假设这个里面啊,呃,有一个假设,我把里面改成M,那整个时间幅度就是。呃,M乘以N或者N乘以M一样的。能理解我的意思,那另外几个我就不一个讲了吧。同学们,什么叫做立方阶,K次方阶我就不讲了。因为你参考刚才讲的平方阶一下就理解了,比如说像这个O的N的三次,呃,立方阶其实相当于三乘N循环,其他类似,好同学们,那到此我相信经过这个讲解,同学们再回头再看我们这里面的这个时间符是不是相对来说好理解了,那同学们看,像这个常见复杂度呢?这里我们就先给大家介绍,这以后同学们再看这些所谓的时间复杂度应该就比较形象了,因为我每个都举了一个案例,对不对?好同学们,关于常见的时间复杂度就给同学们聊到这。
20:24
聊到这儿。
我来说两句