00:00
下面呢,我们来看下一个内容哈,叫算法的时间复杂度里面的时间频度这个概念。那么首先呢,我们对时间频度做一个基本的介绍,何为时间频度呢?说一个算法。他花费的这个时间就是一个算法,它会耗时多少,与这个算法中语句的执行次数为正比例。什么意思呢?比如说我们有一个有一段代码要去排序。而排序的过程中呢,这个比如说这个这个排序呢,他一共用了十条语句,而另外一个算法呢,用了20条语句,它才完成,那么从这一个呃,程序的角度来看呢,你执行的语句越多。那当然我的这一个呃,时间肯定花费就越长,所以说我们说花费的时间与它执行的次数成正比,那么哪个算法中语句执行的次数多,它花费的时间就越多,是吧,成正比的。
01:05
那么在这里有个概念呢,就抛出来了,一个算法中语句执行的次数称之为语句频度,或者叫时间频度,它用一个专门的符号来计较T。N。TN。明白我的意思吧,TN。好,那么这个这个TN呢,就是就叫时间频度,就叫时间频度,好,那么我们来看看关于时间频度有哪些例子,给大家举一下,因为光这样基本介绍,大家没有什么形象的认识,就不知道这什么意思,我们来看几个。同学们看这里。同学们看这里。首先我们看关于时间频度的一个基本案例,比如说现在呢,我们要去计算一到100。就一到100,就一到100,所有数字之和呢,我们有两种算法,第一种大家看这段代码,这段代码其实挺简单啊,就是我用一个for循环。
02:07
从一加到N。最后呢,得到一个to。那么对于这一个同学们看,对于这一个这一段代码,它的时间频度。四等于多少呢?就等于N加一。理解我的意思吧,等于N加一,为什么是N加一呢?大家想一想,假如我们现在这个要统计这个N等于100,我们要统计一加100,这个N就代表它的一个规模,就是这个我们这这一个程序的规模,那么如果N等于100,是不是按这个算法的设计,它要计算。N加一次,那那有些同学呢,你不是计算100次吗。你从这看是I等于一小于等于100嘛,这个N的就相当于是NN了,那么按理说是100。按理说应该是N嘛,但为什么要加一个一呢?同学们知道吗?因为你最后是不是要进行一个判断呢,你还要判断一次才能退出。
03:08
是不是,所以说我们后面是N加一,它的时间频度就是N加一,我们再来看另外一种算法。这个算法呢,也可以得到一加,假设这个N等于100,它也可以得到这个一加到100的值,那怎么算呢?是直接计算的。它是一加N乘以N的除以二。这个是一个简化的写法。啊,那么那么这个时候如果我们也写一个TN来表示它的一个时间频度的话,那么这个N不管有多大,我不管你这个N是100还是1000。还是2000无所谓。只要你是从一加到这个值,那么它的这个时时间频度就应该是一,为什么呢?一句搞定。大家大致明白什么意思了吧?好,那关于这个时间频度有哪些需要同学们注意的呢?我们来看一下。
04:06
大家看。嗯,这里呢,我们在举了几,呃,举了有这么四个案例,比如说这一个时间品种应该这样写,有有点小问题啊,应该这样写就对了啊,这样写。哦,这样是简写,大家大家能看懂啊,就是我这样把它改一下就是TN。TN。等于2N22N,其实二二乘以N的意思,好吧,后面这个以此类推,我就不去改了,好吧,但大致也能看明白什么意思呢,就是说。假如我这里有有这么四个。时间频度。时间频度,那么再看当这个N等于一的时候。当N等于一的时候,其实我要执行22次,22 22次22条语句,那么同样这边等于二,这边等于13,这这边等于三,那随着这个N值的变大,或者说叫这个程序的规模变大,大家有发现什么问题没有?
05:08
你们有没有发现?这两个是无限接近。就是这TN2N加20和TN,这个N也是二乘以N的意思啊,同学们,这个大家我就不再多说了,那么这个二乘以N呢,它的N越来越大,它会变成600,大家有没有发现,随着这个N值的变大,它们两个执行的次数其实是无限接近的。所以说从这里来看呢,这有一个曲线图。这个全图你们发现有没有发现,就是六这个2N加20和二乘以2N他们其实是重合了,逐渐。同样道理,如果我们时间频度是3N加十和3N,你们有没有发现?你们有没有发现他这个地方也是逐渐的重合?那么结论是什么呢?结论是在一个比时间复杂度时间复杂度的这么一个算式里边,我们可以忽略常数项,结论就这样子的,大家看。
06:10
结论是2N加20和2N这两个时间频度的算式随着N的变大,直行曲线无限接近,因此这个20这个常数项20实际上是个常数项,就可以忽略了。下面也是一样道理,三加十和三随着N的变大,执行曲线无限接近,十这个常数项也可以忽略。因此我们在统计一个时间时间频度的时候。那么时,这个长数像其实是可以忽略的,就是对于时间频度而言,长数像是可以忽略的,你明白我意思吧?好的,那么再看下一个案例,忽略第一次项,我们仍然举这个例子,大家看啊。这里有一个时间频度的一一个表达式,那大家看啊,就是二乘以N的平方加上3N加十,注意这个这个算式这样写呢,是有问题的,标准的写法应该这样写啊。
07:10
N啊,这个地方有点大了。折回去啊,就是应该是把这个去掉,这个小框去掉。标准的写法应该是这样写的,同学们。就是N。等于。N等于后面这个算式好吧,呃,大大家应该应该能看懂哈,应该能看懂,这个有点有点短了,我这边挪一下。稍微稍微的移一下啊,稍微的移一下,这样好看一点。好,嗯,后面我就不一个个改了,大家应该能看懂,说现在呢,我们这有四个。时间频度的表达式第一个是2N,二应该是二乘以N的平方,二乘以N的平方加三加加十,这个是二乘以N的平方,这个是N的平方加5N加20,这个是N的平方。
08:07
那么大家有没有发现?当。当我们这个N值逐渐变大的时候,大家有没有发现前两个也是无限的接近,它们的曲线接近重合?看到没有,那么我们再看后面这两个时间频度的表达式,就是N的平方加5N加20和N的平方,你们有没有发现它们随着N值变大,他们的这一个执行的曲线就是执行指数的曲线也见也逐渐的重合。那说明什么问题呢?说明在这个呃,时间频度的表达式里面是可以忽略。第吃相的。那最后结论大家可以看到看到什么呀。二就是第一个二乘以N的平方加三三加十,然后二乘以N的平方随着N值变大,执行曲线无限距可以忽略什么呢?3N3,当然常数项前面已经可以忽略了,所以说统计出来就是3N加十可以忽略,下面也是一样的道理,可以忽略5N。
09:14
加20。这说明我们可以忽略。第一次项。理解啊理解,因为后面这些特点,这个时间频度,它的这个特点会直接影响到我们时间复杂度的一个计算和统计,那么接着我们再看一个案例,可以忽略系数,我们还以这个为例。大家有看到现在呢,我这有一个时间频度的表达式是三乘以N的平方加2N,这个我就不念了,好吧,后面这个不念了,大家有没有发现,我们先看第一个特点,大家有没有发现这两条线。就是呃,随着这个N值的变化,你们有没有发现这这两条线在逐渐的重合,就是什么呢?就说5N的五乘以N的平方加7N和这个三乘以N的平方加2N,它们曲线逐渐重合。
10:07
就是后面这这个我们叫做这个平方项的啊,因为平方项呢,它跟这个立方项就是按照立方来说,那肯定不是一个级别的了。对不对,他们说这个N值变大,你们发现曲线重合,那说明什么呢?说明在这种情况下,我们我们这一个系数。就在这种情况下,这个五和三呢,其实可以忽略。其实可以忽略,因为在在这种数量级很大的情况下,这个五和三呢就可以忽略了。好,这是得到一个结论,我们再来看这个立方项的N的三次方加5N和六乘以N的三次方加4N,大家有没有发现,随着这个N值的变大,这两条线直行曲线开始分离了,一条是紫色的线,紫色的这条线呢,其实就是。他。
11:00
啊,说错了啊,紫色的这条线,对对对,是这个紫色的,呃,不是这个啊,紫色的这条线是这个。六乘以N的立方,而绿色的这条线是什么呢?是N的。三次方加5N,大家有没有发现它是逐渐的分离?而且大家有没有发现逐渐分离过后呢,他们的这个当N无限接近大的数,他们的这个比例就是5N,就是就是这个表达式和N的。立方。加5N的它们随着N值的这个表达,他们这这个这个他们的这个比是无限接近于六。也是他们无限接近于一个一个六这个一个常数项了。所以说在这里呢,我们发现什么呀,就是这两者直线分离,而分离了说明什么呢?这个最重要是跟多少次有关系,在一个数量级的情况下,这个次方表示很重要,因此在这种情况下。
12:02
执行曲线就分离了,好了,那我们发现对于一个呃,算法,算法的时间复杂度里面的这个叫做时间时间频度而言呢,我们发现随着这个N的变大,也就是说这个程序的规模的变大呢,它有三个特点。哪三个特点呢?第一个特点就是常数项可以忽略。第二个特点呢,就是第一次项可以忽略,第三个特点就是什么呢?系数可以忽略,就是高次项的系数也可以忽略,但是你这个这个立方是不能忽略的啊,就次方是不能忽略的。好,那么有了这样一个基础过后呢?呃,我们就把时间频度给同学们。说完了,下面当我们有时间平度这个概念过后,我们再来谈时间复杂度就比较好理解了。那时间复杂度呢?我们放在下一个视频为大家讲解。
我来说两句