算法学习指南
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

如果有人向我们展示同一问题的不同算法怎么办？我们如何确定应该使用哪一种算法呢？观察程序清单1-3的alternate()算法，它反复地检查A中的每个值是否大于或等于同一个列表中的其他所有值。这个算法是否返回了正确的结果？对于规模为N的问题实例，它调用了多少次小于操作？

程序清单1-3　在A中查找最大值的另一种算法

def alternate(A):
  for v in A:
    v_is_largest = True         ❶
    for x in A:
      if v < x:
        v_is_largest = False    ❷
        break
    if v_is_largest:
      return v                  ❸
  return None                   ❹

❶ 对A进行迭代时，假设A中每个值v都可能是最大的。

❷ 如果v小于另一个值x，就停下来并记录v不是最大值。

❸ 如果v_is_largest为True，就返回v，因为它是A中的最大值。

❹ 如果A是一个空列表，就返回None。

alternate()试图在A中找到一个值v，使A中的其他值x都不会比它更大。这个算法使用了两个嵌套的for循环。现在对小于操作的调用进行计数不是很简单，因为对x进行迭代的内层for循环在发现x大于v时就会停止。另外，对v进行迭代的外层for循环一旦找到最大值也会停止。图1-4描述了alternate()在我们的列表实例上的执行过程。

图1-4　alternate()的执行过程

在这个问题实例中，小于操作被调用了14次。但是，我们可以看到这一总数取决于列表A中的特定值。如果这些值处于不同的顺序会怎么样呢？我们能不能找出小于操作的调用次数最少的值排列方式？这样的问题实例被认为是alternate()的最佳情况。如果A的第1个值是所有N个值中最大的，则调用小于操作的次数总是N。总结如下。

1．最佳情况

算法对于规模为N的问题实例需要的工作量最少。

2．最坏情况

算法对于规模为N的问题实例需要的工作量最大。

下面我们来看alternate()需要调用最多次数的小于操作的最坏情况问题实例。alternate()的最坏情况问题实例不仅要保证最大值是A的最后一个值，而且A中的值必须以升序排列。

图1-5（a）描述了最佳情况，此时A = [9,5,2,1,3,4]；图1-5（b）描述了最坏情况，此时A = [1,2,3,4,5,9]。

图1-5　alternate()在最佳情况和最坏情况下的执行示意

在最佳情况下，共调用了6次小于操作。如果在最佳情况下共有N个值，则调用小于操作的次数就是N。最坏情况则有点儿复杂。在图1-5中，我们可以看到当列表中的N个值以升序排列时，总共需要调用26次小于操作。稍微运用一些数学知识，就可以理解对于有N个值的列表，这个计数总是(N2 + 3N − 2)/2。

表1-2显示了largest()和alternate()在规模为N的最坏情况问题实例上的实验数据。

表1-2　最坏情况问题实例下比较largest()和alternate(``)

对于规模较小的问题实例，alternate()的数据看上去并不是很糟糕。但是，当问题的规模倍增时，alternate()调用小于操作的次数几乎是原先的4倍，远远超过largest()中的增长幅度。表1-2的最后两列显示了这两种实现在问题规模为N时100次随机实验的运行时间。alternate()的运行时间随着输入规模的倍增而扩大约4倍。

图标2对算法处理规模为N的随机问题实例所需要的时间进行测量时，从这组运行结果中，我选择了最快的（即最短的完成时间）。这种方法优于简单地对所有的运行时间求平均值，因为后者可能会受到各种因素的影响。

在本书中，我会提供一些像表1-2这样的表格，展示关键操作（如这个例子的小于操作）的调用次数和运行时间性能。每一行表示一个不同的问题实例的规模N的数据。从上到下阅读表格可以看到每一列的值随着问题实例的规模的倍增是如何变化的。

对小于操作的调用次数进行统计可解释largest()和alternate()的行为。当N倍增时，在largest()中小于操作的调用次数也几乎倍增，但是在alternate()中却呈几乎4倍的增长。无论N增大到多少这个规律都成立，因此这个行为具有一致性，我们可以使用这些数据预测这两个算法处理规模巨大的问题时的运行时间性能。图1-6描绘了alternate()调用小于操作的次数与它的运行时间性能的比较，显示了彼此之间的直接关联。

图1-6　小于操作调用次数和运行时间性能之间的关系

恭喜！我们已经完成了算法分析中的一个关键步骤：通过对一项关键操作的调用次数进行统计来预测两个算法的相对性能。我们当然可以接着实现这两种算法的变型（我就是这么做的），并预测这两个算法在规模倍增后的问题实例上各自的运行时间性能。但实际上这是不必要的，因为图1-6的模型已经预测了这个行为，证实了largest()是两个算法中效率更高的那个。

largest()和max()是用相同的算法实现的，但是如表1-3所示，largest()明显比max()要更慢，一般要慢3/4。原因是Python是一种解释型语言，意味着它会被编译为中间字节码再由Python解释器执行。像max()这样的内置函数的性能总是优于实现了相同功能的Python代码，因为内置函数是在解释器内部实现的。我们应该关注的是，当问题实例的规模倍增时，largest()和max()的对应运行时间性能不管在最佳情况还是在最坏情况下都会倍增。

表1-3说明了当问题实例的规模扩大之后对解决问题所需要的时间进行预测是可能的。一旦我们知道了largest()或max()在规模为N的问题实例上的最佳情况或最坏情况下的运行时间性能，就可以预测当N倍增之后的运行时间性能。现在，我们对问题稍加修改，使之更加有趣。

表1-3　largest( )和max()在最佳情况和最坏情况下的运行时间性能　　单位：ms

上一章目录下一章