1.5　在一个随机列表中查找两个最大值

设计一种算法，在一个随机列表中查找两个最大值。也许我们只需要对largest()算法进行少量修改。读者可以尝试自己解决这个修改后的问题，并把自己的解决方案与程序清单1-4进行比较。程序清单1-4展示了我的解决方案。

程序清单1-4　对largest()进行修改，查找两个最大值

def largest_two(A):
  my_max,second = A[:2]                 ❶
  if my_max < second:
    my_max,second = second,my_max
  for idx in range(2,len(A)):
    if my_max < A[idx]:                 ❷
      my_max,second = A[idx],my_max
    elif second < A[idx]:               ❸
      second = A[idx]
  return (my_max, second)

❶ 保证my_max和second是A中降序排列的前两个值。

❷ 如果A[idx]是新找到的最大值，就把my_max设置为A[idx]，second就设置为旧的my_max。

❸ 如果A[idx]大于second，但小于my_max，只更新second。

largest_two()看上去与largest()相似：使my_max和second为A中的前两个值，并具有正确的顺序；然后，检查A中的每个剩下的值（剩下几个值？对！就是N − 2个）；如果发现A[idx]大于my_max，就同时更新my_max和second，否则就检查是否只有second需要更新。

对小于操作的调用次数进行统计要更加复杂，因为它还依赖于问题实例中的值。

当for循环内部的if语句的条件为真时，largest_two()调用小于操作的次数最少。当A包含以升序排列的值时，这个小于条件总是为True，因此调用次数为N − 2。不要忘了加上1，因为函数一开始就调用了1个小于操作。因此在最佳情况下，我们只需要N– 1次的小于操作调用来确定最大的两个值。elif条件中的小于条件在最佳情况下始终不会被用到。

对于largest_two()，我们能不能构建一个最坏情况的问题实例？读者可以自己尝试一下，如当for循环中的if条件中的小于条件总是False时。我相信读者肯定已经知道当A中的值以降序排列时，largest_two()调用的小于操作的次数最多。具体地说，在最坏情况下，for循环的每次迭代需要调用2次小于操作，总共就是1 + 2 × (N − 2) = 2N − 3次。这个结果看上去很符合预期，如果我们需要N − 1次的小于操作来查找A中的最大值，可能还需要另外的N − 2次小于操作（当然可以排除那个最大值）来查找第二大的值。

下面对largest_two()的操作进行总结。

● 在最佳情况下，它在N − 1次调用小于操作之后找到这两个值。

● 在最坏情况下，它在2N − 3次调用小于操作之后找到这两个值。

现在是不是完成任务了？它是解决在一个任意的列表中查找两个最大值问题的“最佳”算法吗？我们可以根据以下因素在几个算法中选择最合适的一种。

1．需要的额外的存储空间

算法是否需要创建原问题实例的一份拷贝？

2．编程复杂性

程序员至少需要编写多少行的代码？

3．可修改的输入

算法是在适当的位置对问题实例所提供的输入进行修改，还是让它保持不变？

4．速度

与问题实例所提供的输入无关的情况下，算法是否能够在速度竞争中胜出？

下面我们研究解决同一个问题的3种不同的算法，如程序清单1-5所示。①sorting_two()创建了一个新列表，包含A中以降序排列的值，然后抓取前两个值并把它们以元组的形式返回。②double_two()使用max()查找A中的最大值，将它从A的一份拷贝（copy）中删除，然后对修改后的列表再次使用max()找到第二大的值。③mutable_two()查找A中最大值的索引位置并把它从A中删除，然后把second设置为A中剩下的那个最大值，再把my_max值重新插入到原先的位置。前两种算法需要额外的存储空间，第3种算法则修改了它的输入。这3种算法都只适用于值的数量超过1个的问题实例。

程序清单1-5　使用Python工具库的3种不同算法

def sorting_two(A):
  return tuple(sorted(A,reverse=True)[:2])       ❶
def double_two(A):
  my_max = max(A)                                ❷
  copy = list(A)
  copy.remove(my_max)                            ❸
  return (my_max, max(copy))                     ❹
def mutable_two(A):
  idx = max(range(len(A)), key=A.__getitem__)    ❺
  my_max = A[idx]                                ❻
  del A[idx]
  second = max(A)                                ❼
  A.insert(idx, my_max)                          ❽
  return (my_max, second)

❶ 按降序对A进行排序，并以它的前两个值创建一个新列表。

❷ 使用内置的max()函数查找最大值。

❸ 创建原先的A的一份拷贝，并删除my_max。

❹ 返回一个元组，其中包含my_max和copy中的最大值。

❺ 这个Python技巧是查找A中最大值的索引位置，而不是查找最大值本身。

❻ 记录my_max值并把它从A中删除。

❼ 现在，在剩余的值中用max()查找最大值。

❽ 把my_max插入到原先的位置，恢复列表A。

这3种不同的算法并没有直接使用小于操作，因为它们依赖于现有的Python库函数。sorting_two()和double_two()都创建了列表A的一份拷贝，这看上去是不必要的，因为largest_two()并没有这样做。另外，为了查找两个最大值而对整个列表进行排序似乎“用力过猛”。与分析运行时间性能时对关键操作调用次数进行统计的方法相似，我将对算法所使用的额外的存储空间进行评估。对于前两种算法，额外存储空间的大小直接与N成正比。第3种算法mutable_two()通过删除A的最大值并在以后将其插入，对A进行简单的更新。这个函数的调用者可能会对原始列表被修改而感到惊讶。

如果熟悉Python技巧，就可以使用一个特殊的类RecordedItem[1]对小于操作的调用次数进行准确的统计。表1-4说明了在列表中的值以升序排列时double_two()调用小于操作的次数最多，而在值以降序排列时largest_two()调用小于操作的次数最多。在“交替排列值小于操作调用次数”列中，524,288个值的排列方式是偶数以升序排列，而奇数以降序排列，比如当N = 8时，输入是[0,7,2,5,4,3,6,1]。

表1-4　不同算法在处理524,288个升序值、降序值和交替排列值时的小于操作调用次数

1.6节所描述的tournament_two()算法不管输入如何都具有最少数量的小于操作调用。篮球爱好者应该会非常熟悉它的逻辑。

如果确定了解决一个特定问题的算法的最坏情况问题实例，也许换种算法来解决同一个问题所受到的负面影响不会这么大。不同的算法可能具有不同的弱点，我们可以通过详尽的分析阐明这一点。