数据结构与算法基础（青岛大学-王卓）

• 同学们好，这一节继续介绍线性表的顺序表和实现。
• 这节课重点讲解按值查找算法。
• 查找的基本操作是从表的一端开始逐个比较。
• 算法复杂度分析包括时间效率和空间效率。

同学们好，这一节给同学们继续介绍第二张线性表的第四节线性表的顺序表是和实现。
那么从这一节开始呢要给同学们介绍几个比较重要的算法。

首先呢第一节课呢给同学们介绍这个顺序表的查找。顺序表的查找呢咱们这块是按值查找。
嗯按值查找什么叫按值查找呢？就是我们给定一个值来看一看，
我们给定的这个值在不在线性表当中，比如说咱们前面介绍的图书信息管理。

那么我们给一个数号，想看看这个数号的书在咱们的这个图书里头有没有，
或者我们给一个书名看看这个有没有。所以呢按值查找就是我们确定一下存不存在。

那么如果有的话存在这本书，那我们就返回，
我们得到的输出结果呢就是它是第几本书，也就是它的序号。

那么说如果不存在呢？如果不存在呢，这个表里头没有这本书，那我们就输出一个零。
所以我们就可以根据这个值就知道，
嗯是零说明没有，不是零说明是它的位置，它是第几个元素。

好的，那比如说我们现在是要输入的这个要查找的书号是这个，
哎那我们找到了，找到了以后呢我们就返回一个3，它是这个表里头的第3个元素，
嗯它的位置在第3个，返回一个3。

那么假如说我们输出的书号这里面没有，我们找了以后这里面没有，
那么我们就得到一个零，就返回一个零。

那么这个查找怎么做呢？我们的思路就是用这个顺序查找法。
那么这个查找呢咱们后面在这个查找这一张专门还要给同学们介绍其他的查找方法。

在这呢就给同学们介绍的是一个最简单的查找方法，就是咱们说的顺序查找法。
所谓顺序查找法呢就是从头到尾一个一个的看，
嗯是不是我们要查找的值。

好，所以呢，我们就从这个表的一端，
比如说从头从表头开始我看看，
啊第一个是不是我们要查找的值，不是，那我们再去看看第二个是不是，
第二个还不是，那我们再去看看第三个是不是，
第三个是了，那么我们就直接返回3，第三个就可以了。

那么说如果第三个还不是，那我们就继续再看下一个，
下一个，下一个。
那么什么时候把这个表中所有的元素这里面多少个元素呢？
假如说是N个，哎这N个元素我们存在什么位置呢？
下标从0到n-1。

嗯下标从0到n-1，如果我们把这些位置用i来表示，从0到n-1我们全都看了，
都不是我们要找的这个书，那就是没有。
这就是我们说按值查找是什么意思，我们是怎么做的。

所以我们来看看这个按值查找算法，咱们科普上的算法2.3。
所以按值查找呢就是在咱们的线性表L当中查找与指定的值E相等的这个元素的位置。
我们要得到这个位置。

那么怎么找呢？我们从表的一端开始，刚才呢给同学们介绍的是从表头开始，
从最第一个往后找，一个一个往后找。
那我们其实也可以从最后一个开始，一个一个往前找。
嗯一个一个往前找，咱们在第七章学的这个顺序查找呢就是从最后开始往前找，
而且呢加一个哨兵，这可以提高效率。
哎咱们后面再说这块，呢给同学们介绍的就是一个最简单的，从前往后找。

我们就是从前往后逐个的，一个一个的，
拿我们当前的这个记录当中的关键字和我们要查找的这个给定值进行比较。
如果一样那我们就说找到了，找到了我们就返回它所在的位置，它是第几个，返回这个序号。

没找到我们就返回零，这就是我们想要的操作。
那么这个操作怎么实现的呢？我们说就是这样从表的一端开始一个一个去比较。
一个一个去比较。

好那我们来看一下这个算法，很简单。
给定了线性表，给定了要查找的元素，一查找元素一。
那我们在这个线性表当中进行查找。

那么怎么查找呢？从第一个元素，也就是下标为零的元素开始，
我们进行比较看看是不是一样。
如果一样呢就返回它的位置，我们说第一个元素第一个元素存在下标为零的这个位置。
哎所以呢第下标为零的这个位置是第一个元素。

所以我们需要零加一，零加一这才是它是第几个元素。
这个元素的序号第几个刚好跟它的下标存储的位置的差异。
我们需要加异。

嗯需要加异就是咱们说的，嗯一样不一样，一样那就找到了返回它的位置。
那么不一样，不一样我们发现不一样，不一样呢，
哎那我们就再回来进行下一次循环。
哎加加，加加。

那我们就要看下一个位置上的元素和我们要查找的值是否一样，
嗯如果一样那我们从这就是一吞了，直接返回。
什么意思呢？结束当前的这个函数，就直接返回了。
嗯这个循环呢就不再执行了，不再执行了。

好那么说还是没有找到。那我们就怎么样？再继续下一次循环，
再加加，再看下一个位置的是否一样。
嗯那我们说，就这样一个一个往下找。

如果哪一个找到了我们就直接返回它的位置，就结束了。
嗯这个循环就结束了。

如果我们所有的元素都找遍了，哎这个i呢是小于什么呢？
这个里头放的什么呢？这个里头咱们说就是先行表达第二成员，这指的是表长度，
也就是这个表当中元素的个数，元素的个数n。

那么i小于这个值，l点lans小于，也就是说i最大呢可以到n-1。
我们也就是从0到n号，从这个下标为0一直到n-1，
哎一个一个去看，一个一个去看。

那么下一次我们说，如果这n个元素，从0号下标为0的到下标为n-1的我们都看了，
嗯都看了这个都不相等，那就说明没找到了。
那么这个时候i的值再加加，下一次循环，
嗯i的值再加加。再加加，那就变成n了。

嗯那就变成n。那么这个n小于这个n的条件就不成立，
不成立退出循环，不执行循环体，不执行循环体到哪去了呢？
继续这一条语句就执行完了，循环语句执行完了就到这了。

嗯到这那么这个时候说明我们把这个线性表当中所有的元素全都看遍了，
都不是，都不是那说明没找到，我们就返回一个0，返回一个0。
这就是我们进行顺序查找的算法。

顺序查找的算法好嘞，那么如果同学们对这个算法哪里不明白呢？
就请同学们在咱们的这个课程里头给我发说明或者直接找我。

那么接下来呢，咱们来分析一下这个算法的复杂度。
这个算法的复杂度我们说同学们已经学过这个算法的复杂度是怎么分析的。
我们说算法复杂度呢我们要分析时间效率和空间效率。

哎那么重点呢是要分析时间效率。
时间效率我们是用渐进时间复杂度来分析的，哎那他是怎么计算的呢？
哎我们说有三个步骤，第一步找到执行次数最多的那条语句，
然后第二步呢看看它到底执行多少次，
第三步呢把它表示成大欧的形式。

也就是说这个执行次数呢是关于一个n的函数，
然后我们求这个函数的数量级把它表示成大欧的形式。

好嘞那我们说对于这个算法呢我们也用这样的办法，
嗯我们先找到执行次数最多的那条基本语句。
那么这个执行次数最多的是哪一个呢？
哎我们说这个是这个循环体。

嗯这个循环体当我们找到的时候，
当我们找到的时候，哎这个找一遍不是再下一次他又执行一次。
再找一遍不是下一次又执行一次，哎有一次找到了，嗯找到了，
哎那你说他就是执行次数最多的一句。

执行次数最多的一句。
那么嗯我们说他就可以定义成我们要，
嗯这个算法当中的基本操作，
嗯就是将我们要查找的值，嗯这个给定的这个值与我们这个表中的记录进行比较。

也就是咱们的这一句。这一句执行多少次呢？
到底执行多少次呢我们说这个不一定。
比如说咱们看一下这个例子，我这有一个线性表，这个线性表当中存储了七个元素，
所以呢lans的值这个成员的值是七。

这个表中有七个元素，那么假如说我要查找的元素呢是A，查找元素是A，
哎那我第一次i等于零，第一次循环的时候i等于零，
然后呢我用的是这个元素下标为零的这个元素的值和我的查找值进行比较，
哎那我们说只需要比较一次找到了，嗯直接返回这个i加1；

返回i加1也就是返回的是i加1等于0加1等于1，返回这个元素呢就在我们这个表中第一个位置。
第一个就是他找到了，找到了。

那么这个时候我们比较了几次啊？就比较了一次，嗯比较了一次。
所以咱们说如果我们刚好要查找的是他，
那么假如说我们要查找的是他的话，嗯我们输入的要查找的值是b。

那么这个时候我们这个i的值呢，还是从零开始，从零开始看一下，
他是不是我们的要查找的值b，那我们说不是。
不是呢，那i加加，嗯i加加i变成1，变成1。

然后呢我们就去看这个下标为1的这个位置上的元素，
嗯是不是和我们要查找的值b相等，
哎是不是跟我们要查找的这个b相等。
哎看，哎相等了，相等了那就找到了。

那我们这个时候就可以返回他的位置了，
嗯i加1等于2，我们就可以返回2，哎就表示这个他是第二个元素。
嗯第二个元素，那我们说这个每一次到底比较几次呢？
我们找第一个元素的时候找这个a的时候比较一次就找到了。

嗯如果查找的是b的话，那我们就需要比较两次，
第一个比较了不是，第二个比较了是，哎那就比较两次。
那我们要找第三个的话那我们就需要怎么样呢？同理，
嗯第一个不是，第二个不是，嗯一次两次，然后第三个a是我们比较三次，
嗯就需要比较三次。

同理如果我们要找的是这个第七个元素，嗯找第七个元素那我们就需要比较七次，
嗯就需要比较七次。
也就是说我们这一个基本操作到底会执行多好次呢，跟我们的要查找的元素有关系。

哎看到底要查找哪一个，嗯查了哪一个。
哎那平均来说要查找几次呢？你就是说我们说第一个元素他是查找一次，
第二个元素查找两次，第三个元素查找三次，
第四个元素就需要，哎这个比较四次，下一个比较五次，比较六次，比较七次。

哎那么假设这些呢都找一遍，这七个元素都找一遍。
嗯都找一次。那我们的比较次数呢平均下来我们除个七，
一加二加三加四一直加到七，
嗯加起来除上一个七，

那么平均需要多少呢？哎那我们算一下。
嗯一加二等于三，三加三等于六，六加四等于十，
十五再加六是二十一，再加七是二十，
嗯这个二十八哎二十八除以七等于四。

哎那我们平均，嗯如果是这七个元素每一个都找一遍的话有的比较的次数少。
嗯哎只需要一次有的呢就需要：
哎比如说我找的元素我从头往后我就需要比较七次，
平均来说，嗯需要比较四次，需要比较四次。

好那我们说咱们这个顺序查找法我们要衡量，它到底执行多少次呢，
我们就用这个平均比较次数来衡量。
这个呢就是咱们说的平均查找长度。

我们给他一个数语平均查找长度称作ASL，
嗯ASL，平均查找长度。
嗯平均查找长度也就是说，
嗯这个所有的所有的表中所有的值假如说都被查找一遍的话，
那么平均要比较多少次。

那么这个值呢咱们在数学里面有一个数语就叫做期望值。
嗯就叫做期望值所谓期望值呢，它就是这个输出值的一个平均值。
嗯是不是这个嗯什么输出值呢？
咱们是一个离散的随机变量。

嗯咱们这个查找某一个元素呢，
你到底查找哪一个这是随机的，非定查找哪一个，
并不一定查到哪一个，哎那我们在这个同样的机会下，
假如说每一个都查找都会查找到，
平均的情况那么是什么情况呢？

哎它是这样来算，嗯所以同学们看到这个数学表达式的时候，
会觉得哦这个东西好像很难那样子。
其实呢它也不是很难，就是咱们刚才说的什么呢，
我用一加上二加上三一直加加加我有七个元素，
那个第一个元素比较一次就行了，第二个元素比较两次，
如果是第七个元素呢那我们就需要比较七次。

哎那么这七个元素假如说平均每个元素都找一次，
嗯那我们除以一个七。
哎那就等于四，
就我们就是算这个东西的算这个东西。
这就是咱们的平均查找长度，平均查找长度那怎么算的呢？
啊怎么算的呢？我们是这样算的，
哎为什么要除以七呢？为什么要除以七呢？

其实呢就相当于七分之一乘以一加上七分之二乘以二加上七分之一乘以二。
意思是说什么呢？这七个元素每一个都出现一次，
那么这如果七次的话，他们的出现的概率呢都是七分之一。
出现的概率都是七分之一，一直到最后一个元素它出现的概率也是七分之一。

因为要算平均嘛，乘以一个它需要比较七次，
哎我们把这个七放进去这这是咱们小学的计算方法求平均值是这么求的。
这这是咱们大学的这个求平均值的，我们用它出现的概率。
出现的概率。

所以我们叫做期望值，那我们把这个东西累加起来就是这个公式，
把这个东西累加起来就是这个公式。
那么这里面的一二三一照到七是什么呢？
就是查找第二个元素。这是查找第一个元素的，
这是查找第二个元素的，最后这个是查找第七个元素。

就是这个找到第二个元素需要的比较次数，需要的比较次数。
那么这里面这个七分之一是什么东西呢？这个七分之一呢，
就是每一个元素被查找的时候的概率。
我们这七个元素每个元素都被查找一次，
所以如果查找七次的话，那么他们每一个元素的出现的概率是七分之一。

然后我们把这个东西累加起来所有元素的累加起来，
这就是咱们说的期望值，其实就是这个平均值。
好嘞，那我们现在用大学的方法就不用中学的方法了，
我们就这样来算的，每一个出现的概率乘上每一个的比较次数。
然后做累加和，做累加和。

好嘞那我们展开的话累加和，那就要展开，用第一个元素它需要比较一次，
其实就是乘以1乘以1，第一个元素出现的概率乘以1。
加上这不累加吗，把它展开。

加上第二个元素需要比较的次数乘以第二个元素出现的概率，
一直到最后一个元素出现比较的次数乘上它的概率。
那么咱们在这都假设每个都可能要查找，它被查找的这个概率是相等的。
我们七个元素都可能被查找到，如果查找七次的话每个都会出现一次。

所以我们说每一个出现的概率都是七分之一，都是七分之一。
那我们N个元素每一个查找的概率都是N分之一，
那我们把N分之一带进去就是P，P2，P3，P4，一直到Pn。
这个全都等于N分之一。

所以呢我们就可以把这若干个N分之一都提取出来了，
这若干个N分之一那这就是什么呢？N分之一。
然后乘以1加2加3加4一直加到N，就成了这个东西了，就成这个了。
那么1加2加3加4一直加到N，这是个等差数列。

那我们按照等差数列求和就可以了，按照等差数列求和就可以了，
我们把它求出来，把它求出来。
那么这个求和的结果是多少同学们还会不会了？会，这个求和的结果是2分之N乘以N加1。
是不是2分之N乘以N加1。

好嘞那么我们在这个2分之N乘以N加1的前面再乘上一个N分之一，
再乘上一个N分之一，2分之N乘以N加1再乘上一个N分之一。
再开在前面乘上，那我们就可以把这个N约掉了。
所以最终这个平均查找长度是多少呢？是2分之N加1。

是2分之N加1，这就是咱们这个公式的由来。
这就是咱们这个公式的由来。
我们假设每个记录都会被查到一次，他们出现的概率是相等的。
那就都是N分之1，所以我们的平均查找长度就是这个。

这个我们把这一部分提出来都一样，都是N分之1提出来。
那么我们累加从1加到N，从1加到N，这就是这个，从1加到N。
那么我们进行化解N分之1乘以这个，所以最终的结果，N约掉了，
最终的结果是什么呢？就是这个。

这就是咱们计算这个查找的平均查找长度的方法。
以往的时候同学们算这个地方就是总也不明白，
不知道怎么来的，不知道怎么来的，
也不知道怎么算呢，现在同学们就理解了。

如果同学们还有问题的话请同学们提出来。
那么关于这个顺序表的查找算法查找算法的算法分析咱们就分析到这里。
那么这个查找次数我们知道了，比较次数我们知道了，
那实际上它的数量级我们也就知道了，
我们找出它的数量级就是大ON，大ON是N的一次方。

N的一次方好这一节课咱们就讲到这里。