00:00
下面我们来看一下。算法的这个平均时间复杂度和最坏时间复杂度的这么一个概念。那么首先我们看平均时间复杂度,它是指什么意思呢?指的是所有可能的输入实例均以等概率的出现情况,该算法的一个运行时间,也就也就是说,呃,考虑到一个平均的问题。考虑到一个平均的问题,那么最坏情况下的时间复杂度呢?我们称之为最坏时间复杂度。一般来讲呢,我们在讨论一个算法的时间复杂度的时候,我们一般讨论是最坏时间复杂度,为什么呢?因为这样做的原因是,最坏情况下的时间复杂度是算法在任何输入实例上运行的时间的一个界限。那这样就保证了算法在运行时间是不会比最坏情况更长,比如说我已经把最坏的情况下考最坏的这么一个时期事情给给你考虑到了。
01:05
那呃,你你你这就是一个,呃,这这就是能够做一个参考的标准了,你不能考虑最好啊,对不对,所以说我们看第三点,平均时间复杂度和最坏时间复杂度是否一样呢?这个跟算法是有关系的,就不同的算法,平均时间复杂度可能和最坏时间复杂度是相同的,也有可能不相同,就是不同的算法呢,有区别,大家看我这里列,列举出来了这么。一些排序算法,比如说1234567899个,那么我们来看看冒泡这个排序算法,它的平均和最差是一样的。第二个呢,交换也是一样的,选择也是一样的,插入排序也是一样的,OK,那么基数排序就是我们所说的统排序的升级版,它也是一样的,是一个对数间,前面这些大家有没有发现冒泡交换选择插入它都是一个平方间,那说明冒泡选择。
02:08
还有这个,呃,交换选择插入,他们都至少是一个双层波循环才能搞得定,是这意思吧。好,而基数排序呢,大家可以看到它的时间复杂度是一个对数线,因此可以看到基数排序它的速度在同等的情况下肯定要比冒泡交换选择插入要快,所以说通过这个时间复杂度,你一下就看出来了。那么我们再看这个希尔排序,希尔排序大家有没有发现它的平均时间复杂度是一个线性对数键。线性对数阶,那么它的平均和这个最差呢不一样。你看这个如果是最差的情况下,有没有发现线排序,它最差的情况下它是一个什么阶啊,看它是一个呃是一个呃,相当于是N的N的S次方,就是有点像这个S是在一到二之间,那说明什么?它是介于这一个,在最大的情况下,它是介于一个线性阶和一个平方阶的这么一个情况。
03:13
平均时间是一个取,取终止的话是一个线性对数键。对吧,我们再看快速排序,快速排序如果在最差的情况下,它是一个平方键,就是跟如果在最快速排序在最差的情况下,其实它和这个冒泡交换是一致的。是不是,但是呢,如果在平均的情况下来看呢,快速排序它是一个线性堆数键,所以说时间还是要快一些,那么我们再看规定和堆,规定规定和堆来说,它们都是它们平均时间复杂度和最差啊,最差时间复杂度其实都是一个线性。对数结,所以说我们通过这个案例,你们可以看的出来。你们可以看出来就是冒泡交换选择插入他们的这个速度。
04:02
他们的速度其实大致相同。当然也会有些微小差别啊,有些微小差别,而我们的这一个C2排序,还有快速排序规定堆,他们都是一个线性,呃,平均时间范围都是个线性的,所以说他们还是呃肯定要从从这个。排序的时间来看呢,还是要比前面这几种排序方法要快是吧,而且大家看到后面写了一个备注,就是N。这个大呢,N大的时候比较好,就是N越大呢,我们这一个。呃,这个性能就越越优越,就越能够体现出这种算法的优越性,对吧?好,这是我们说的平均时间复杂度和最坏时间复杂度,后面呢,我们会把每一个算法都给大家做一个讲解,就是呃,八大算法嘛,八大算法好,下面呢,我们再来探讨一下算法的空间复杂度。空间复杂度呢?这里我们就做一个基本的介绍,为什么这么说呢?大家看这里。
05:03
类似于时间复杂度的讨论。一个算法的空间复杂度叫SPA。Complete,那么定义为该算法所耗费的存储空间。它也是一个问题规模N的一个函数,那么空间复杂度呢?对一个算法在运行时间占用的存储空间的一个大小的度量,就是我可以通过空间复杂度来计算一个算法占用多大存储空间。那么有的算法需要占用的临时工作单元和解决问题的规模有关,它属于N的增大而增大,当N较大时占用的。空间较大,例如快速排序和规避这种算法呢,它会占用额外的这种空间,所以说你的N越大,它占用的空间就越大,但是我们这有一句话,我做了一个整理啊。在做算法分析的时候呢,我们一般来讲是讨论时间复杂度,为什么这么说?因为从用户的体验来看,我们更看重的是时间,是这个程序执行的时间,对不对?
06:06
就是说从用户来看,他并不关心你这个程序占用了多少的空间,他更关心的是你什么时候把这个事情做完。是这意思吧。而有些缓存产品,像red memory case和一些算法,比如像基数排序,它的本质就是用空间换时间,而且大家也知道,随着计算机的发展呢,硬件这一块其实它的成本在降低。对吧,我说诶我用一个空间来换时间,一般来讲在在这个公司里面都是允许的,而且实际上在我们做优化的时候,在做这个算法优化的时候呢,本身就能够去用空间换实验,你比如说你为什么要做一个二级缓存,三级缓存。你为什么不让他直接插数据库呢?其本质就是让这些数据先加载到缓存,我直接从缓存取,当然你会占用一些额外的空间呢,但是时间呢,却变得很快。
07:03
对不对,所以说你看后面我们再讲这个最经典的两个算法,一个是快速排序,还有归并,归并排序的时候你你都会看到,这里面会有一个空间换时间的概念在里边。啊,空间换时间概概念在里边好了,那所以说这个空间复杂度呢,我们就做一个简单介绍就行,好同学们,那现在呢,我们就把刚才讲的这一系列的内内容呢,给大家做一个简单的板书,我们刚才讲的是哪些来捋一捋。来捋一捋。好,我们。我们刚才是讲到这个地方的。是吧,讲到这个位置。时间频度讲到时间频度,我们从这里开始来做一个板书,再讲时间复杂,时间复杂度的时候呢,我们给大家说了一下这个时间频度的一个概念。时间频度感首先我们对时间频度做了一个基本的介绍,就是什么叫时间频度?说白了,呃,所以时间频度就是一个算法中,一个算法中语句执行的次数,称之为时间频度。
08:13
然后在这个计算,为了加深大家对时间频度的理解呢,我举了好些个案例,第一个呢,先给同学们举了一个关于时间频度的基本案例。这个案例很简单,一下就说明了时间频度它的这个概念,具体来说呢,举个例子,就这个例子。对吧,我们用两种算法。两种算法,第一种算法呢是用for循环,第二种是直接计算,可以体现出时间频度对应的表达式是不一样的,你看这个是N加一,这个是一个一,呃,一次搞定。好,这是我们举的第一个案例,把第一个案例举完了过后呢,我们又给同学们说明了时间频度的三个特点,第一个呢,时间频度它可以忽略随着这个N规模的变大,它可以忽略什么样常数项。
09:04
也就是同学们看到的这个图。我把这个呢给同学们拿过来好,拿过来好,这是我们所说的时间频度随着N值变大呢,可以忽略常数项,这里面有个结论,我把这个结论给同学们板述过来。对吧,这是一个结论。两点嘛,针对上面呢,我们做了一个结论。OK,紧接着呢,我们又举了时间频度的。另一个特性就是可以忽略它的第一次项,也也也是在随着我们这个规模的变大,N规模变大的时候可以忽略,好我把这个呢也给大家拿过来。第一次项是可以忽略的。没问题吧,好回顾哈,那这个地方我们又把这个说完了,我们又做了一个小结论。是吧?关于第一次项,它是怎么来做到忽略的?
10:00
这个说完了过后,我们是不是说了时间频度,它还有第三个特点,就是可以忽略它的系数。啊,因为忽略这个系数呢,呃也是,呃,可以计算出它的空间的一个复杂度的,你看这里。在这里呢,我们。把这个挪过来哈,大家看这里。是吧,结论在这儿。结论是在这个位置。也给大家整理到这儿。OK,诶,这个地方重新来整一下。随着N值的变大呢,它会逐渐要么重合,要么执行曲线分离,但是分离的时候呢,它们的系数就是它们这个系数会逐渐形成一个常量。你比如说刚才这个N的三次方加5N和六乘以N的三次方,到最后它的比例就应该是什么呢?就应该是六和一的一个关系。诶,这样子就就就能拿到一个等啊等数量级的一个表示方法。
11:02
那这个说完了以后呢,我们又讲了什么呢?我们又给他讲了时间复杂度的这个概念,就说时间复杂度和刚才讲的这一个时间频度的一个关系是什么关系,那么我把这个也拉过来。我们这讲的是时间复杂度。对,时间复杂度。好,第一点我们说了时间复杂度是和这个TN就是时间频度的一个关系,那后面呢,我们说了一下时间复杂度它的一个计算的方法。有这么三点。是不是举了一个例子来讲解的,对吧?哎,举了一个例子来讲解的。好,上面呢,每个案例我们都有,我就这里就不再111个一个说了啊,这里面再体体验一下什么情况?算法中的基本操作语句是,呃,执行数是问题规模N为N的一个函数,那么当什么呢?当N趋近于无穷大时,这。
12:01
TN和FN的极限值为一个不等于零的常数,那么我们就称FN是它一个等量级的同数量级的一个函数,那最后呢,这个公式大家要记下,就是我们这个TN可以用你这个等量级的函数来表示,这个N是什么就什么。这个O。对应的O,大写的O里面对应的这个表达式,我们整个这个称之为什么呢?渐进时间复杂度也称为时间复杂度这么来的,你比如说后面举了例子,这两个是时间频度的,那么最后根据我们这个计算方法呢,这两个时间时间频度对应的。空、时间、复杂度都为它。是不是下面举例子说明的,然后把这个讲完过后呢,为了加深印象,我们说了一下在我们整个这个算法里面常见的。时间复杂度有这么一些。哦,有这么八种。这八种的关系呢,我们捋了一下,我们说了这八种时间复杂度呢,是有两点说明,一个是谁是由上往下时间复杂度在逐渐的增大,那么我们要尽量的避免指数阶这种时间复杂度,因为它。
13:18
会非常的耗费我们时间,对吧,我把这个呢也列到这里。这边有一个图啊,说明有两点,应该是第一个。这个还是要记下的啊,因为你在做这个算法分析的时候呢。一般来讲你会把这个。时间复杂度。分析出来,然后你就可以有针对性的进行优化。那么对应的这个图上面常见啊,我这写个常见的。这个时间复杂度对应的。对应对应的一个图。图的一个描述,我把它呢,也给各位同学放在笔里面了,这个图在哪里呢?就是刚才在我们笔记里啊,在幻灯片里面看到这个图很形象很形象,好,然后这个说完了以后呢,我们就针对每一个,呃,不同的。
14:15
这个时间辅当中呢,举了一些案例,举了案例,第一个呢,我们举的是常数街的案例。好,常数解的案例这个地方应该写成什么样?就时间复杂度,常数解的案例我就写到这。好,常书杰。常熟界的案例。好,常数节的案例呢,我们就这样子给大家拿过来就行哈,因为时间关系,我就这样子截个。截个图就放这,大家一目了然,这是第一个,然后把这个常数阶说完了,过后我们又给他讲了对数阶对不对对数阶的一个案例。对数是这样一个情况,那么对数阶呢,它的一个经典的案例就是下面这个代码,我把这个呢也给同学们拿过来,非常的简单。
15:03
好,放在我们的笔记中,大家一看就知道是怎么回事。对数阶讲完了过后,我们又说,又举了一个例子,是什么呀,线性阶。对吧,线性节就是说他这个执行时间复杂度呢,跟这个N有关系,你的N变随着N的变大而增长。比如说最经典就是单纯的循环。是不是把这个放这这个讲完了过后呢,我们又讲了一个什么呀,线性对数解。对线性对线性对数节呢,它一个经典的案例就是在for循环里边,我们嵌套了。一个VR循,呃,一个这个对数阶的一段代码,这个是个负循环里面这是个什么呢?这是一个对数阶的一段代码,对吧,所以说这个合起来就叫线性对数阶。线性对数键。下去对数阶讲完了过后呢,我们又给同学们举了一个例子,什么呀,平方阶,平方阶呢,是我们开发中建的比较多的,就是双层或者呃,就是嵌套负循环。
16:09
嵌到负循环,比如说刚才我们这这个案例,看你这有个负循环,里面还有一个负循环,而且里面两个都是N,这就N的平方,如果你一个是一个是M,那就是时间复杂度,就是M乘以N。OK,好,这个呢,我们叫做什么呀?叫做平方阶,还有一个呢,就是后面我们所说的立方阶和K次方阶,那么立方阶和K次方阶呢,我们可以参照。参照平方阶来理解就可以了,那也就是说如果是立方阶,就是三乘负循环,如果是K次方阶,那就什么呢?就是K次嵌套循环,这个K是多少就是多少,比如说你K45,那就是五层负循环是吧,五层的这个嵌套,那这个说完了以后呢,我们就给同学们说了一下平均。
17:01
我们又给同学们介介介绍了一下平均时间五度和最坏时间维度,关于这个字点呢,我们这有三点要说明。我们这有三点要说明对不对,哪三点我们给他截一个,给他排列一下,尤其是要注意一点,就是我们我们在讨论啊,就是一般讨论时间复杂度呢,我们讨论的是什么呢?是最坏情况下的时间幅度,这样呢就能保证即使在最坏的最坏的情况下,我们这个分析呢,也是正确的。OK,那么有1.1定要说明,平均时间复杂度和最坏时间复杂度是否一致跟算法有关系,你比如说刚才我们这罗列出来的这个图。你看这个图里面,这个就看得很清晰,冒泡排序法,在冒泡排序平均和最差都一样的,但是呢,12排序。他这个平均。时间幅度和最差情况的时间幅度就不一样了,由对线性对数阶变成了一个什么,变成了一个可能是个平,呃,就是像一个K4方阶这么一个复杂度,那当然最坏的情况下时间就会受一些影响,对不对?好,这个说完了以后呢,我们又给大家简单的说了一下算法的空间复杂度,这是第二个标题,那么我们讲了空间复杂度呢,我这里做了一个基本介绍,并没有深入的去探讨为什么。
18:30
这里我做了一个解释。做了解释,就说我们在实际的这个开发中呢,我们。我们的用户从用户体验来看,它主要是看程序执行的速度。对吧,而且我们目前呢,有很多算法本质就是空间换时间,因此呢,空间复杂度呢,一般来讲,我们在做算法这个分析的时候呢,一般不会去过多的去讨论。啊过有去讨论,因为你你用这个空间换时间,它本身也是一种优化的一种思路,对不对,所以说你看你们用用的这种缓存产品,像red member catch,他做一级缓存,二级缓存,其实就是事先把数据先加载到缓存里面去,然后呢,尽量尽量从内存里面就把它拿出来。
19:18
啊,当然了,这个呃概念呢,大家还是要有的,就说我们这个算法呢,还是会不同的算法对这个空间呃占用的情况也是不一样的,比如说同学们后面选择规定排序啊,你会发现呢,它占用的空间就很大,再比如说后面学到的这一个叫做基数排序。啊,基数排序,基数排序呢,它也会占用较多的这个存储空间,后面呢我们再做。具体的一个分析,好好,同学们,那关于我们这一块,关于算法的空间和时间复杂度呢,就给同学们先介绍到这里,OK。
我来说两句