算法效率对比：顺序查找vs折半查找

2025-09-30 理论教育版权反馈

【摘要】：运行算法时所消耗的资源的多少称为算法的效率。在6.4.1节讨论了无序表的顺序查找算法，在6.4.2节讨论了有序表的折半查找算法，现在我们来分析对比一下这两个不同的查找算法的时间效率。对于有序表的折半查找算法来说，当给出一个要查找的书号时，由于知道记录是按书号有序存放的查找线索，所以折半查找算法可以从表的中间处开始查找。因此，在学习掌握各种算法时，不仅要掌握算法的实现过程，还要掌握算法的时间效率。

对于任意一个问题，通常存在许多个方法不同的算法。虽然这些算法都是正确的，都能得到期望的结果，但是，不同的算法在得到这些结果时消耗的资源却是不同的。运行算法时所消耗的资源的多少称为算法的效率。消耗资源少的算法称为高效率的算法，消耗资源多的算法称为低效率的算法。

运行算法时所消耗的资源主要是时间资源和空间资源。时间资源指的是运行算法所花费的时间，空间资源指的是运行算法所占用的内存空间。其中，时间资源是算法设计时要考虑的主要资源。运行算法时所消耗的时间资源的多少称为算法的时间效率。

我们通过实际例子的分析，来看看算法的时间效率对实际应用问题的影响。假设某个图书馆共有100万册图书，该图书馆的图书借阅通过计算机来实现管理。和人工进行图书管理的方法类同，计算机管理图书时，也要记录并保存每本书的书号、书名、作者名、是否已经借出等信息，不同之处只是计算机管理时这样的信息是存储在计算机中。我们把一本图书的描述信息称为一条记录，这样，全部100万册图书就有100万条记录。当一本书被借阅时，需要把相应的记录修改为已经借出状态，当一本书被归还时，需要把相应的记录修改为可以借阅状态。要对某条记录作这样的修改，必须在100万条图书记录中查找到相应的记录，这就需要使用查找算法。

在6.4.1节讨论了无序表的顺序查找算法，在6.4.2节讨论了有序表的折半查找算法，现在我们来分析对比一下这两个不同的查找算法的时间效率。

对于无序表的顺序查找算法来说，当给出一个要查找的书号（因一本书有一个书号，所以书号是惟一编码的）时，由于没有任何查找线索，所以顺序查找算法只能从表的起始处用一个循环过程进行查找。每次循环中，用要查找的书号和表中当前记录的书号比较，当比较相同时，查找过程结束，当比较不相同时，再和表中下一个记录的书号比较，直到某次比较相同或所有的记录全部比较完没有查找到所要的记录为止。对于一个随机给出的表中存在的书号，我们很难说算法会在第几次比较时找到该书号，但最好的情况是在第⋯次循环时就比较相同，最坏的情况是在最后一次循环时才比较相同，平均情况是在记录的一半处比较相同。假设计算机运行该算法时，每次比较和其他一些附属的查找工作需要耗时10﹣4秒（万分之一秒），则在最坏情况下查找到记录需要耗时100秒，在平均情况下查找到记录需要耗时50秒，这对读者和图书管理人员来说是一个比较长的等待时间。(https://www.chuimin.cn)

对于有序表的折半查找算法来说，当给出一个要查找的书号时，由于知道记录是按书号有序存放的查找线索，所以折半查找算法可以从表的中间处开始查找。每次查找时，当书号比较相同时，查找过程结束，当书号比较不相同时，根据比较时的大于或小于情况，用原有序表的前半部分或后半部分继续进行查找。直到某次查找时比较相同或有序表为空为止。对于一个随机给出的表中存在的书号，我们很难说算法会在第几次比较时找到该书号，但最好的情况是在第一次比较时就相同，最坏的情况是在最后一次比较时才相同。由于折半算法每次新的有序表都是原有序表长度的一半，所以对100万条记录来说，最坏的情况下比较14次（13＜lb 1000000＜14）即可。假设计算机运行该算法时，每次比较和其他一些附属的查找工作需要耗时10﹣4秒，则在最坏情况下查找到记录需要耗时0.014秒，这是用户感觉不到的非常快的时间。

从上述的分析结果可以得出如下结论：特定的应用问题对算法的时间效率有特定的要求。因此，在学习掌握各种算法时，不仅要掌握算法的实现过程，还要掌握算法的时间效率。同样，在以后的软件设计工作中，不仅要根据要求设计出算法，而且要设计出满足用户时间效率要求的算法。

对于处理同样数据的不同算法来说，比较不同算法的时间效率优劣时，并不需要计算具体的数值，只需用抽象的数值进行比较就可以。例如，对于查找问题，可以把要处理的数据个数抽象为n，则顺序查找算法的平均查找时间为某个常数数值的n/2倍，而折半查找算法的最坏查找时间为某个常数数值的lb n倍。这样，算法效率的比较就主要比较的是算法的数量级差别。例如，顺序查找算法的时间效率是数据个数n的一次方，而折半查找算法的时间效率是数据个数n的lb n。我们用函数O（f（n））来表示数据个数n的数量级为函数f（n）。这样，顺序查找算法的时间效率就可以表示为O（n），折半查找算法的时间效率就可以表示为O（lb n）。时间效率函数还有O（n2），O（n3），O（nlb n）等等。显然，这几个函数的优劣排列次序是：O（lb n），O（n），O（nlb n），O（n2），O（n3）。

对算法效率的分析称作算法分析，也称作算法的复杂性分析。算法分析是计算机科学和计算机工程领域的一个非常重要的研究方向。算法分析主要分析的是算法的时间效率。前面说过，运行算法时除时间资源外，还需要存储空间资源，但不同的算法存储空间的差别不是很大，所以除特殊应用要求外，一般情况下，算法的空间效率不会对应用问题有太大的影响。

算法效率对比：顺序查找vs折半查找

相关推荐