1.4 可以預測算法性能的模型
如果有人向我們展示同一問題的不同算法怎么辦？我們如何確定應該使用哪一種算法呢？觀察程序清單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倍。
對算法處理規模為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
