1.1　什么是算法？

解釋算法的實現邏輯就像講故事一樣。算法會在普通的解決方案中引入新穎的思路或進行某種創新。在本章中，我們將討論一個簡單問題的幾個解決方案，解釋影響算法性能的一些因素。在這個過程中，我將介紹一些用于分析算法性能的技巧。這些技巧與算法的實現無關，盡管我在討論中總是會提供實際實現的實驗證據。

算法是一種逐步解決問題的方法，可實現為計算機程序的形式，能夠在可預測的時間內返回正確的結果。算法的研究既要關注正確性（它對于所有的輸入是否都能發揮作用？），也要關注性能（它是解決這個問題的最有效方法嗎？）。

下面我們詳細觀察一個算法的例子，看看它實際上是怎么處理問題的。如果我們想在一個無序列表中查找最大值，應該怎么辦？圖1-1中的每個Python列表都是一個問題實例（problem instance），也就是算法（用圓柱體顯示）所處理的輸入。正確答案出現在算法的右邊。這個算法是如何實現的？它在不同的問題實例上是如何執行的？我們能不能預測在一個包含1,000,000個值的列表中查找最大值所需要的時間？

圖1-1　一個算法所處理的3個不同的問題實例

算法不僅僅是一種問題解決方法。實現算法的程序還需要在可預測的時間內完成任務。Python的內置函數max()已經解決了上面這個問題。現在，對于包含隨機數據的問題實例，預測算法的性能可能比較困難，因此找到精心構建的問題實例是極有價值的。

表1-1顯示了在兩種類型的規模為N的問題實例上執行max()需要的時間。一種是以升序排列的整數列表，另一種是以降序排列的整數列表。由于讀者所使用的計算機系統的配置不同，得到的執行結果可能與表中的不同，但仍然符合下面這兩個結論：

● 當N足夠大時，在遞增的值上執行max()需要的時間總是要多于遞減的值需要的時間；

● 當后面每一行的N值都為前一行的10倍時，max()的對應時間盡管稍有偏差，但大致也是原來的10倍，這也與我們的生活經驗相符。

上述問題實例中，max()返回最大值，輸入并沒有被修改。在有些情況下，算法會直接更新問題實例而不是計算一個新值，我們將在第5章學習的對一個值列表進行排序的算法就是這樣的。在本書中，N表示問題實例的規模。

表1-1　在兩種類型的規模為N的問題實例上執行max()需要的時間　　單位：ms

關于執行算法所需要的時間：

● 我們無法事先預測T(100000)的值（即算法處理一個規模為100,000的問題實例所需要的時間）是多少，因為計算平臺可能并不相同，實現算法所使用的編程語言也可能不同；

● 但是，一旦通過實驗確定了T(10000)所需要的時間，就可以對T(100000)，也就是解決一個10倍規模的問題實例所需要的時間進行預測，盡管這種預測不可避免地和準確時間有所出入。

在設計算法時，基本的挑戰是保證它的正確性，使之適用于所有的輸入。我將在第2章使用更多的篇幅解釋如何對解決同一個問題的不同算法的行為進行分析和比較。算法分析這個領域與現實生活中發生的有趣的、重要的問題的研究息息相關。由于算法所蘊含的數學知識理解起來具有一定的難度，我將提供一些特定的例子，實現抽象的概念與現實世界的問題的關聯。

計算算法效率的標準方法是對它所需要的計算操作進行計數，但這是極難做到的！計算機中執行機器指令的中央處理器（CPU），負責執行數學計算（例如加法和乘法）、CPU寄存器的賦值、兩個值的比較等任務。有些現代的編程語言（例如C或C++）被編譯為機器指令，還有一些編程語言（例如Python或Java）被編譯為中間字節碼表示形式。Python解釋器（本身是C語言程序）執行字節碼，而像min()和max()這樣的內置函數是用C語言實現的，最終會被編譯為機器指令而執行。

強大的數組

數組是指在一塊連續的內存中存儲N個值的集合。它是程序員存儲多個值時所使用的最“古老”也最可靠的數據結構之一。圖1-2表示一個包含8個整數的數組。

圖1-2　包含8個整數的數組

數組A有8個值，可根據位置進行索引。例如，A[0]=31、A[7]=5。A中的值可以是任何類型，例如字符串或者更為復雜的對象。

下面是與數組有關的一些重要知識：

● 第1個值A[0]的索引位置是0，最后一個值的索引位置是A[N–1]，其中N表示數組的長度；

● 每個數組都具有固定的長度，Python和Java允許程序員在運行時確定數組的長度，但C語言不允許；

● 可以通過索引位置i讀取或更新數組中的一個單獨值A[i]，i是一個0～N ? 1范圍內的整數；

● 數組無法直接被擴展（或收縮），但是我們可以分配一個目標大小的新數組，并把舊數組中應該保留的值復制到這個新數組。

數組非常簡單，它在組織數據時具有極廣的用途和極高的效率。在Python中，list（列表）對象可以看成數組，它的功能更加強大，因為它能夠隨時擴展和收縮。

要對一個算法所執行的機器指令的總數進行統計幾乎是不可能的，何況現代的CPU每秒可以執行數十億條指令！我將改而對每個算法所調用的關鍵操作的數量進行統計，這可能是“數組中兩個值的比較次數”或“一個函數的調用次數”。在max()函數的討論中，關鍵操作是“小于操作（<）被調用了多少次”。我將在第2章中解釋這個計數原則。

現在，是時候揭開max()算法的面紗了。