跳转至

算法效率评估

先把输入大小和形状同时改一改

测试查找时,用长度 10、100、1000 的数组分别运行。每个长度都试目标在开头、在末尾和不存在。光测开头会觉得不论怎样都一样快,光测一次也容易受其他程序抢占处理时间等因素影响。同样的代码测出的时间会波动,这种波动常叫**测量噪声**。除耗时之外,可以数比较次数,先知道算法实际走了几步。

把这组数据直接拿去比较二分查找,缺了什么条件?

二分查找需要有序数据。若输入还要排序,应说明测的是单次查找,还是把预处理也算进整个任务。

在算法设计中,我们先后追求以下两个层面的目标。

  1. 找到问题解法:算法需要在规定的输入范围内可靠地求得问题的正确解。
  2. 寻求最优解法:同一个问题可能存在多种解法,我们希望找到尽可能高效的算法。

也就是说,在能够解决问题的前提下,算法效率已成为衡量算法优劣的主要评价指标,它包括以下两个维度。

  • 时间效率:算法运行时间的长短。
  • 空间效率:算法占用内存空间的大小。

简而言之,我们的目标是设计“既快又省”的数据结构与算法。而有效地评估算法效率至关重要,因为只有这样,我们才能将各种算法进行对比,进而指导算法设计与优化过程。

效率评估方法主要分为两种:实际测试、理论估算。

实际测试

假设我们现在有算法 A 和算法 B ,它们都能解决同一问题,现在需要对比这两个算法的效率。最直接的方法是找一台计算机,运行这两个算法,并监控记录它们的运行时间和内存占用情况。这种评估方式能够反映真实情况,但也存在较大的局限性。

一方面,难以排除测试环境的干扰因素。硬件配置会影响算法的性能表现。比如一个算法的并行度较高,那么它就更适合在多核 CPU 上运行,一个算法的内存操作密集,那么它在高性能内存上的表现就会更好。也就是说,算法在不同的机器上的测试结果可能是不一致的。这意味着我们需要在各种机器上进行测试,统计平均效率,而这是不现实的。

另一方面,展开完整测试非常耗费资源。随着输入数据量的变化,算法会表现出不同的效率。例如,在输入数据量较小时,算法 A 的运行时间比算法 B 短;而在输入数据量较大时,测试结果可能恰恰相反。因此,为了得到有说服力的结论,我们需要测试各种规模的输入数据,而这需要耗费大量的计算资源。

理论估算

要想提前判断输入大到十万、一百万项时开销怎么变,可以数代码里的操作,再看规模足够大时哪一部分增长最快。这里的「渐近」说的就是规模变得很大时的趋势。这种估算方法被称为渐近复杂度分析(asymptotic complexity analysis),简称复杂度分析。

复杂度分析能够体现算法运行所需的时间和空间资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加,算法执行所需时间和空间的增长趋势。这个定义有些拗口,我们可以将其分为三个重点来理解。

  • “时间和空间资源”分别对应时间复杂度(time complexity)和空间复杂度(space complexity)。
  • “随着输入数据大小的增加”意味着复杂度反映了算法运行效率与输入数据体量之间的关系。
  • “时间和空间的增长趋势”表示复杂度分析关注的不是运行时间或占用空间的具体值,而是时间或空间增长的“快慢”。

复杂度分析克服了实际测试方法的弊端,体现在以下几个方面。

  • 只要能数出操作,就能在实现或运行代码前比较增长趋势。
  • 分析基于同一套计数规则,可以用它比较不同机器上实现同一个算法时共有的结构。每一步实际耗时还得测量。
  • 它可以体现不同数据量下的算法效率,尤其是在大数据量下的算法性能。

Tip

如果你仍对复杂度的概念感到困惑,无须担心,我们会在后续章节中详细介绍。

复杂度分析为我们提供了一把评估算法效率的“标尺”,使我们可以衡量执行某个算法所需的时间和空间资源,对比不同算法之间的效率。

复杂度是个数学概念,对于初学者可能比较抽象,学习难度相对较高。从这个角度看,复杂度分析可能不太适合作为最先介绍的内容。然而,当我们讨论某个数据结构或算法的特点时,难以避免要分析其运行速度和空间使用情况。

综上所述,建议你在深入学习数据结构与算法之前,先对复杂度分析建立初步的了解,以便能够完成简单算法的复杂度分析。