速学数据结构-大O表示法（Python）原创

哈喽，大家好，欢迎来到数据商谷，大家可以叫我二师兄啊，那么接下来的一些视频呢，我和大家去讲解一下关于数据结构的一些知识啊，那么今天呢，我们先来了解一下，到底什么叫数据结构呢？以及我们怎么去表示一个算法的好坏呢？我们一起来看一下啊，这有一份课件，那么首先呢，第一个就是数据结构是什么，那我们都知道在生活中我们盖房子的时候，是不是会有一些钢架结构啊，像是三角形更稳定，还是说啊四方形的是吧，很多的形状，那么包括我们去啊超市买买东西，去买菜啊，买水果是不是都要排队啊，那你会发现生活的各个地方都是存在着它自己的一个结构的，那么对于我们这个虚拟的数据也是一样的啊，我们这个数据之间呢，有一个前后的关系，有一个上下的关系，那么这些关系呢，所组成的内容呢，它就叫做数据结构啊，那么我们来看一下，这就是数据结构的一个表示方法，然后呢，再往下看吧，那么有了数据结构之后呢，其实它是算作是。

法的一种啊，那么关于这些算法来说，我们怎么去评判一个算法的好坏呢？那你盖房子你看啊，刮风下雨，这个房子如果不倒啊，或者说是啊，地震的时候它根本就不动摇啊，是不是证明这个结构很好啊，对吧？那么我们数据结构也是一样的，我们会有一个方法去评判我们这个数据结构的一个好坏，那么它要叫做大O表示法啊，那么下面呢，我们来看一下具体什么叫大O表示法呢？那么大O表示法啊，其实就是说我们可以把每一次在我们计算机中做运算的过程来叫做时间复杂度，那么每做一次运算呢，我们可以看作是增加了一个时间单位啊，那么来看一下，哎，具体时间单位是怎么去走的呢？那么首先我们来了解一下关于on的时间复杂度啊，我们来看一下，这里有一段伪代码，我把这里放大一下。我们可以看到这段伪代码，首先我们会定义一个数据S等于零，然后呢，对于这个for循环for I range n是吧？那么这个N是集我们就不用去了解了，那么里边呢，就是S加等于一，我们来去看一段这段，看一下这段代码吧，那么首先可以知道在这个方循环进行的过程中，是不是我们每进行一次循环，这个S的值都会进行一个加一的操作，那么它每进行一次这样的运算操作，我们就可以看作是这个时间单位啊，其实就加一了，这里是时间，时间单位是加一了。那么我们来想一下，是不是有N次循环啊，N次循环也证明我们这个在整个负循环的过程中，时间单位是加了N的，那么一到循环结束，是不是我们就走过了N个时间单位呢？那么既然是N个，那么所以说我们可以把这种循环的时间复杂度把它叫做on啊，那么这个on就是这么一个意思，它的时间复杂度就是on，那么好啦，了解了on之后呢，再来看下边有了on啊，其实还有on方，On方其实和他刚刚才。

它就是啊，差不多的啦，我们来看这两个for循环对吧？第一个方循环for I in range n，第二个方循环for接in range n，对吧？那么对于里面这个方循环我们先来执行，那么对于这个fo接于转N，是不是我们这个S加等于一的操作执行了N次呀，对吧，就是走过了N的时间单位没问题吧？那么再往上呢，看这外外层这个循环啊，外层这个循环for I in range n，那么这个for I in range n是不是证明它也要走过N的时间单位呀，对吧？那么这里我们也给一个N，那么因为这个循环啊，是嵌套的，一个嵌在一个里边一个啊在一个外边这么一个结构，那么这对于这两个结构呢，我们会发现每一个的时间单位都是N，那么它们整体的时间单位应该是做相乘的操作吧，这个大家应该都知道吧，对吧，先执行X次，然后呃，先执行N个I，然后再执行N个阶，对吧？那么总体就是N的平方呗，N乘以N，所以说对于这种形式的这个代码呀，我们可以把它看作是时间复杂度为N方啊，这是N方。

那么第三个呢，就是log个n log n呢，相对于NN和这个N方来说呀，它要小一些，对吧？那么如果它用它来表示这个时间单位的话呢，很明显它会更快一些，那么它快在哪呢？它为什么会快呢？我们就来看一下，那么首先呢，给定这么一个循环，我们现在不用负循环了，我们用while循环，哎，While I小于n ni等于I乘以二，那么这个循环呢？哎，是一个关于while的条件，那么想一下，如果我们写上这个循环，跳出循环停止，我们应该达到一个什么程度啊？是不是当I等于N的时候，这个循环就不再往下进行了呀？那么当I等于N的时候，我们要想一下，这个循环它走过了多少遍呢？它走了多少遍之后停了呢？那么走过的这个变数是不是就是我们走过了几个时间单位呀，对吧？那我们一起来算一下，它走过了多少遍呢？我们来用一个画笔来算一下啊，那么首先呢，我们可以去啊设定设定什么呀，设定它走了K变可以吧，走了K变那么可以。

想一下这里这个循环呀，I等于I乘以二，那是不是每走一遍，我们这个I就在原来值的基础上乘了一个二啊，对吧？那么每次都乘二，那么K变是不是应该成了K个二，也就是二的K次方啊，对吧？那么当它等于什么的时候呢？哎，当它等于哪个值的时候跳出循环呢？对吧？是不是应该二的K次方等于N，当这个I等于N了，我们自然也就跳出循环了呗，对吧？那么此时这个K等于几啊？是不是K1解就知道等于log n啊对吧？那么这样的话大家应该发现了吧，我们此时关于这种这个循环的一个伪代码呢，就可以看作是它的时间复杂度为log n啊，那么这是log n其实就是这么来的，那么再往下呢，我就不再去给你们做过多的介绍了啊，比如说我们会遇到这个N乘以log n，它是怎么来的呀，你把它的外边加一个for循环，是不是就可以变成是N乘以log n呢？因为我们刚才说了呀，每一个for循环它都可以看作是N的。

时间单位对吧？那么这个呢，就是关于N乘了个N，那么与此同时还有N方啊，N的立方啊等等的都是一样的一个，呃，这个思想啊，我就不去做过多的一个赘述了，那么好了，了解完了这三个简单的时间复杂度之后呢，我们可以看一下关于时间复杂度的一个对比，那么这里呢，列出了很多很多的一个情况啊，有n log个NN乘log个N，还有N方，还有二的N次方是吧？那么很明显可以看到随着我们这个N的增大，也就是循环次数的增加，我们这个时间呢啊，消耗啊是就是有一些差别的对吧？二的N次方是消耗时间最长的，然后是N方，然后N乘log n，然后N，然后是log n，对吧？那么这样的话呢，根据这个时间复杂度长短，我们可以判断出我们这个算法的一个好坏程度了，那么当我们去写算法，去解一个题的时候，是不是越把时间复杂啊，时间复杂度越就是降的越低，应该越好一些，对吧？那么降到log n是不是应该是一个最好的一个情况对吧？那么好了，那这些就是关于时间复杂度的。

一个简单的讲解啊，那么下面的一节呢，我们会来讲解一下一些基本的数据结构。