1.5　性能分析

算法的性能分析是算法設計的重要部分。估計算法性能的方法之一是分析算法的復雜度。

復雜度理論研究算法的復雜程度。任何有用的算法應該具備以下三個關鍵特征：

• 算法應該是正確的。算法如果無法給你正確的答案，則對你毫無用處。
• 好算法應該是易懂的。如果世界上最好的算法對你來說太復雜，你無法在計算機上實現，則它對你也毫無用處。
• 好算法應該是高效的。即使算法能產生正確結果，但是如果它需要花費一千年或者10億TB的內存，那么它的用處也不大。

有兩種方法用于量化分析算法的復雜度：

• 空間復雜度分析：估計算法運行對內存的需求。
• 時間復雜度分析：估計算法的運行時間。

1.5.1　空間復雜度分析

空間復雜度分析就是估計算法在處理輸入數據時所需的內存量。在處理輸入數據的同時，算法需要在內存中存儲一些臨時的數據結構。算法的設計方式將會影響這些數據結構的數量、類型和規模。在分布式計算時代，需要處理的數據量越來越大，空間復雜度分析變得日益重要。這些數據結構的規模、類型和數量將決定對于底層硬件的內存需求。分布式計算中使用的現代內存數據結構——如彈性分布式數據集（Resilient Distributed Dataset，RDD）——需要高效的資源分配機制，使其能夠感知算法在不同執行階段的內存需求。

空間復雜度分析是高效算法設計中必須完成的工作。如果在設計特定算法時沒有展開空間復雜度分析，臨時數據結構可用的內存不足，則可能會觸發不必要的磁盤溢出，從而大大影響算法的性能和效率。

本章僅深入討論時間復雜度。空間復雜度將在第13章中進行更詳細的討論，屆時將對運行時內存需求比較復雜的大規模分布式算法進行處理。

1.5.2　時間復雜度分析

時間復雜度分析就是依據算法結構來估計算法完成其指定工作所需的時間。與空間復雜度不同，時間復雜度并不取決于運行算法的任何硬件設施，而是完全取決于算法本身的結構。時間復雜度分析的總體目標是試圖回答下列重要問題：算法是否具有良好的可擴展性？算法在處理更大規模數據集時性能如何變化？

為回答這些問題，我們需要確定數據規模的增加對算法性能的影響，并確保設計的算法不僅準確，而且具有良好的可擴展性。在當今“大數據”的世界里，算法處理更大規模數據集時的性能變得越來越重要。

在很多情況下，設計算法的方法可能不止一種。此時，時間復雜度分析的目的如下：

“給定某個問題和多種算法，從時間效率來看，使用哪種算法效率最高？”

計算算法的時間復雜度有以下兩種基本方法：

• 實現算法后的分析方法：這種方法先分別實現各種候選算法，再對其性能進行比較。
• 實現算法前的理論方法：這種方法在運行算法前用數學方法近似計算每個算法的性能。

理論方法的優點是它僅依賴于算法本身的結構，而不依賴于將用于運行該算法的實際硬件、運行算法時所選擇的相關軟件和用于實現該算法的編程語言。

1.5.3　性能評估

典型算法的性能都取決于作為輸入提供給它的數據的類型。例如，如果在待求解問題中數據已經排序，則該算法執行的速度可能會快得驚人。如果用排序后的輸入作為基準來對特定算法進行測試，則將得到不真實的、過好的性能測試結果，而這個結果在大多數情況下并不能夠反映算法的實際性能。為了處理算法對輸入數據的這種依賴性，我們在進行性能分析時需要考慮各種不同情況。

最好復雜度

在最好復雜度中，輸入數據經過組織，能夠得到算法的最佳性能。最好復雜度分析得出算法性能的上界。

最壞復雜度

評估算法性能的第二種方法是嘗試找到算法在給定條件下完成工作所需的最大可能時間。最壞復雜度分析非常有用，因為我們可以保證無論在何種條件下算法的性能總是優于所得的分析結果。在評估算法在處理更大規模數據集的復雜問題時，最壞復雜度分析特別有用。最壞復雜度給出了算法性能的下界。

平均復雜度

平均復雜度分析先將各種可能的輸入劃分為不同的組，然后從每組中選擇具有代表性的一個輸入來分析算法性能，最后計算出算法在各組輸入上的平均性能。

平均復雜度并不總是準確結果，因為它需要考慮算法輸入的所有不同組合和可能性，但這并不總是容易做到的。

1.5.4　選擇算法

你怎么知道哪種方案更好？你怎么知道哪種算法運行得更快？時間復雜度和大O記號（本章后面會討論）為回答這種問題提供了有效手段。

為了理解它的作用，我們舉一個簡單的例子：對一個數字列表進行排序。有幾種可用的算法可以完成這項工作，問題是如何選擇合適的算法。

首先，易于觀察到的事實是，如果列表中數字為數不多，則我們選擇哪種算法來排序數字列表根本無關緊要。例如，如果列表中只有10個數字（n=10），則我們選擇哪種算法均不要緊，因為即使是設計得非常糟糕的算法，所花費的時間可能也不會超過幾微秒。但是，如果列表規模高達100萬，則選擇合適的算法就會產生區別。一個寫得很差的算法甚至可能需要幾個小時才能完成列表排序任務，而一個設計較好的算法則可能僅用幾秒就完成了任務。因此，在大規模輸入數據集上，投入時間和精力展開性能分析，選擇合理設計的算法來高效地完成要求的任務是非常有意義的。

1.5.5　大O記號

大O記號用于量化表示各種算法在輸入規模增長時的性能，它是最壞復雜度分析中最常用的方法之一。下面討論不同種類的大O記號。

常數時間復雜度（O(1)）

如果算法運行時間是獨立于輸入數據規模的相同值，則稱其運行時間是常數時間，表示為O(1)。例如，考慮訪問數組的第n個元素，無論數組的規模多大，花費常數時間即可獲得結果。再如，下面的函數以復雜度O(1)返回數組的第一個元素：

其輸出結果顯示為圖1-7。

• 使用push向棧內添加新的元素，或使用pop從棧中刪除元素。無論棧的規模多大，添加和刪除元素都花費常數時間。
• 訪問哈希表中的元素（參見第2章的相關討論）。
• 桶排序（參見第2章的相關討論）。

線性時間復雜度（O(n)）

如果算法的執行時間與輸入規模成正比，則稱該算法具有線性時間復雜度，表示為O(n)。例如，考慮下面對一維數據結構中所有元素求和的算法：

注意算法的主循環。算法中主循環的迭代次數隨著n值的增加而線性增加，導致了O(n)的復雜度，圖1-8展示了算法的運行實例。

其他一些數組操作的例子如下：

• 查找元素
• 找出數組中所有元素的最小值

平方時間復雜度（O(n2)）

如果算法的執行時間與輸入規模的平方成正比，則稱該算法的運行時間為平方時間。例如，考慮下面對二維數組求和的簡單函數：

注意，在內層循環嵌套外層主循環中，這種嵌套結構使得前面代碼的時間復雜度為O(n2)（如圖1-9所示）。

另一個例子是冒泡排序算法（參見第2章的相關討論）。

對數時間復雜度（O(log n)）

如果算法的執行時間與輸入規模的對數成正比，則稱該算法的運行時間為對數時間。在時間復雜度為O(log n)的算法中，隨著算法的每一輪迭代，輸入規模都會以常數倍數遞減。例如，二分查找是對數時間復雜度，該算法用于從一維數據結構（如Python列表）中查找特定元素，它要求數據結構內的元素按降序進行排序。下面的代碼將二分查找算法實現為一個名為searchBinary的函數：

主循環利用了列表有序這一事實。算法中每輪迭代都將列表二等分，直到得到結果（如圖1-10所示）。

定義完函數后，圖1-10的第11行和第12行中通過查找特定元素對其進行了測試。二分查找算法將在第3章中進一步討論。

注意，在所介紹的四種類型的大O記號中，O(n2)表示最差性能，O(log n)表示最佳性能。事實上，O(log n)可以視為任何算法性能的黃金標準（盡管并非總是能夠達到）。另一方面，O(n2)并不像O(n3)那樣糟糕，但由于時間復雜度限制了它們實際可以處理的數據規模，因此屬于這類時間復雜度的算法仍然不能用于大數據。

降低算法復雜度的一種方法是在算法的準確度上進行折中，從而得到一種稱為近似算法的算法。

算法性能評估的整個過程本質上是迭代進行的，如圖1-11所示。