概述

算法是計算機程序的一個基本的構建模塊。評價算法質量的最基本的標準是正確性，另一個重要的標準是運行時間性能。當在一臺真實、資源有限的計算機上運行一個算法的時候，經濟性的考慮就有了用武之地，這樣一個過程會消耗兩種資源：處理時間和空間或內存。

統計指令

用于估算算法性能的另一種技術是統計對不同的問題規模所要執行的指令的數目。不管算法在什么平臺上運行，這個統計數字對于算法所要執行的抽象的工作量給出了一個很好的預計。然而要記住，當統計指令的時候， 所統計的是用于編寫算法的較高級代碼中的指令數目，而不是執行機器語言的程序中的指令數目 。

當以這種方式分析算法的時候，你需要區分兩種指令：

（1）不管問題規模多大，都執行相同次數的指令

（2）根據問題的規模，執行不同次數的指令

現在，我們先忽略第一類指令，因為它們的影響并不顯著，第二類指令通常在循環或遞歸函數中可以找到。

復雜度分析

復雜度的階

大O表示法

一個算法幾乎不太可能只是嚴格執行等于n、n^2或k^n的那么多次的操作，算法通常在循環體內、循環體之前或之后還要執行其他的工作。例如，我們說算法執行2n+3或2n^2操作，可能會更加精確。

一個算法的總工作量，通常是多項式中的數項之和，當用多項式來表示工作量的時候，有一個項是 主項 ，隨著n變得越來越大，主項也變得很大，以至于你可以忽略其他的項所表示的工作量。例如，在多項式(1/2)n^2-(1/2)n中，我們主要關注平方項(1/2)n^2，實際上忽略掉線性項(1/2)n，還可以刪除掉系數1/2，因為(1/2)n^2和n^2之間的差別不會隨著n的增加而改變。這種類型的分析有時候叫做 漸進分析 （asymptotic analysis）。

搜索算法

搜索最小值

Python的min函數返回列表中的最小的項。為了研究這個算法的復雜度，我們開發了一個替代的版本，它返回了最小項的索引。這個算法假設列表不為空，并且其中的項的順序是任意的，該算法首先將列表中的第1個位置當作最小項，然后，向右搜索以找到一個更小的項，如果找到了，將最小項的位置重新設置為當前位置，當這個算法到達列表末尾的時候，它就返回最小項的位置。

            
              class indexOfMin():
    def indexOfMin(self,lyst):
        """Return the index of the minmum item."""
        minIndex = 0
        currentIndex = 1
        while currentIndex < len(lyst):
            if lyst[currentIndex] < lyst[minIndex]:
                minIndex = currentIndex
            currentIndex += 1
        return minIndex

if __name__ == "__main__":
    a = indexOfMin()
    lyst = [3,5,7,1,9,10]
    print(a.indexOfMin(lyst))
            
          

對于大小為n的列表，該算法必須進行n-1次比較，因此，算法的復雜度為O(n)。

順序搜索一個列表

Python的in運算符作為list類中名為__contains__的一個方法而實現。該方法在列表（任意排列的項）中搜索一個特定的項（叫做目標項）。在這樣的一個列表中搜索一個目標項的唯一的方法是，從第1個位置的項開始，將其與目標項進行比較，如果這兩個項相等，該方法返回一個True。否則，該方法移動到下一個位置并且將其項與目標項進行比較。如果該方法到達了最后一個位置，卻仍然沒有找到目標項，它就返回False。這種搜索叫做 順序搜索 （sequential search）或 線性搜索 （linear search）。一個更為有用的順序搜索函數，應該返回它所找到的目標項的索引，或者如果沒有找到目標項的話，返回-1。

            
              class Search():
    def sequentialSearch(self,target,lyst):
        """Returns the position of the target item if found, or -1 otherwise."""        
        position = 0
        while position < len(lyst):
            if target == lyst[position]:
                return position
            position += 1
        return -1

if __name__ == '__main__':
    a = Search()
    target = 3
    lyst = [2,4,5,1,3,7]
    print(a.sequentialSearch(target,lyst))
            
          

最好情況、最壞情況和平均情況的性能

有些算法的性能取決于所處數據的放置方式。順序搜索算法在查找一個目標項的時候，在列表的開頭處所做的工作比在列表的末尾所做的工作要少。對于這樣的算法，我們可以確定其最好情況的性能、最壞情況的性能和平均情況的性能。 通常一般考慮的是最壞情況的性能和平均情況的性能 。

順序搜索的分析要考慮如下3種情況：

（1）在最壞情況下，目標項位于列表的末尾，或者根本就不在列表之中。那么，算法必須訪問每一個項，并且對大小為n的列表要執行n次迭代。因此，順序搜索的最壞情況的復雜度為O(n)。

（2）在最好的情況下，算法只進行了1次迭代就在第1個位置找到目標項，復雜度為O(1)。

（3）要確定平均情況，把在每一個可能的位置找到目標項所需的迭代次數相加，并且 總和除以n 。因此，算法執行了(n+1)/2次迭代，對于很大的n，常數因子2的作用并不大，因此，平均情況下的復雜度仍然為O(n)。

顯然，順序搜索的最好情況的性能是很少見的，而平均情況和最壞情況的性能則基本相同。

有序列表的二叉搜索

對于那些沒有按照特定的順序排列的數據，順序搜索是必要的。 當搜索經過排序的數據的時候，可以使用二叉搜索（又稱為二分搜索）。

現在來考慮Python實現二叉搜索的一個示例。首先，假設列表中的項都是按照升序排列的，搜索算法直接找到列表的中間位置，并且將該位置的項和目標項進行比較。如果它們是一致的，算法返回該位置。否則，如果目標項小于當前項，算法搜索列表中間位置以前的部分。反之，搜索中間以后的部分。

            
              def binarySearch(target, lyst, profiler):
    """Returns the position of the target item if found,
    or -1 otherwise."""
    left = 0
    right = len(lyst) - 1
    while left <= right:
        profiler.comparison()
        midpoint = (left + right) // 2
        if target == lyst[midpoint]:
            return midpoint
        elif target < lyst[midpoint]:
            right = midpoint - 1
        else:
            left = midpoint + 1
    return -1
            
          

在最壞的情況下，循環要運行列表的大小除以2直到得到的商為1的次數，對于大小為n的列表，實際上執行了n/2/2.../2的連續除法，直到結果為1。假設k是用n除以2的次數，要求解k，讓n/(2^k)=1就行了，那么n=2^k，k=log2n，因此，二叉搜索的最壞情況的復雜度為O(log2n)。

比較數據項

二叉搜索和搜索最小項，都是假設列表中的項是可以相互比較的。在Python中，這意味著這些項具有相同的類型，并且它們都識別比較運算符==、<和>。幾個內建的Python類型的對象，例如數字、字符串和列表，都可以使用這些運算符來比較。

為了允許算法對一個 新對象的類 使用比較運算符==、<和>，程序員應該在該類中定義__eq__、__lt__和__gt__方法。__lt__方法的方法頭如下所示：

            
              def __lt__(self,other):
            
          

如果self小于other，該方法返回True，否則，它返回False。 比較對象的標準，取決于它們內部的結構，以及應該以何種方式對其排 序。

例如，SavingAccount對象可能包含3個數據字段，一個用于名稱，一個用于PIN，還有一個用余額。假設賬戶應該按照名稱的字母順序來排序，那么，需要對__lt__方法按照如下的方式來實現：

            
              class SavingAccount(object):
    """This class represents a saving account with the owner's name, PIN, and balance."""
    def __init__(self,name,pin,balance = 0.0):
        self._name = name
        self._pin = pin
        self._balance = balance

    def __lt__(self,other):
        return self._name < other._name
            
          

注意：__lt__方法對兩個賬戶對象的_name字段調用了<運算符（名稱是字符串），并且字符串類型已經包含了一個__lt__方法。當對字符串應用<運算符的時候，Python自動運行__lt__方法。就像是在調用str函數時運行str方法一樣。

基本排序算法

這里介紹的幾個算法很容易編寫，但是效率不高，下一節介紹的算法都很難編寫，但是更為高效（這是一種常見的取舍）。每個Python排序函數都是在整數的一個列表上進行操作的，并且都會使用一個swap函數來交換列表中的兩項的位置。

swap函數的代碼如下：

            
              def swap(lyst,i,j):
    """Exchanges the items at position i and j."""
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp
            
          

選擇排序

最簡單的策略就是搜索整個列表，找到最小項的位置。 如果該位置不是列表的第1個位置，算法就會交換在這兩個位置的項，然后，算法回到第2個位置并且重復這個過程，如果必要的話，將最小項和第2個位置的項進行交換。當算法到達整個過程的最后一個位置，列表就是排序好的了。這個算法叫做選擇排序（selection sort）。

            
              def selectionSort(lyst):
    i = 0
    while i < len(lyst) - 1:
        minIndex = 1
        j = i + 1
        while j < len(lyst):
            if lyst[j] < lyst[minIndex]:
                minIndex = j
            j += 1
        if minIndex != i:
            swap(lyst,minIndex,i)
        i += 1
            
          

這個函數包含了一個嵌套的循環。總的比較次數為(1/2)(n^2)-(1/2)n，對于較大的n，我們可以選擇影響很大的項，而忽略常數項。因此，選擇排序在各種情況下的復雜度為 O(n^2) 。

冒泡排序

另一種排序方法相對容易理解和編碼，它叫做冒泡排序（bubble sort）。其策略是從列表的開頭處開始，并且比較一對數據項，直到移動到列表的末尾，每當成對的兩項之間的順序不正確的時候，算法就交換其位置。 這個過程的效果就是將最大的項以冒泡的方法排到列表的末尾。 然后，算法從列表開頭到倒數第2個列表項重復這一個過程。依次類推，直到該算法從列表的最后一項開始執行。此時，列表是已經排序好的。

            
              def bubbleSort(lyst):
    n = len(lyst)
    while n > 1:
        i = 1
        while i < n:
            if lyst[i] < lyst[i-1]:
                swap(lyst,i,i-1)
            i += 1
        n -= 1
            
          

和選擇排序一樣，冒泡排序也有一個嵌套的循環，對于大小為n的列表，內部的循環執行(1/2)(n^2)-(1/2)n次，因此，冒泡排序的復雜度是O(n^2)。

插入排序

（1）在第i輪通過列表的時候（其中i的范圍從1到n-1），第i個項應該插入到列表的前i個項之中的正確位置。

（2）在第i輪之后，前i個項應該是排好序的。

（3）這個過程類似于人們排列手中的撲克牌的順序，也就是說，如果你按照順序放好了前i-1張牌，抓取了第i張牌，并且將其與手中的這些牌進行比較，直到找到其合適的位置。

（4）插入排序包括兩個循環。外圍的循環遍歷從1到n-1的位置。對于這個循環中的每一個位置i，我們都保存該項并且從位置i-1開始內部循環。

            
              def insertSort(lyst):
    i = 1
    while i < len(lyst):
        itemInsert = lyst[i]
        j = i - 1
        while j >= 1:
            if itemToInsert < lyst[j]:
                lyst[j + 1] = lyst[j]
                j -= 1
            else:
                break
        lyst[j + 1] = itemToInsert
        i += 1

            
          

插入排序的最壞情況下的復雜度是O(n^2)。列表中排好序的項越多，插入排序的效果越好。在最好情況下，列表本身是有序的，那么插入排序的復雜度是線性的。然而，在平均情況下，插入排序的復雜度仍然是二次方階的。

更快的排序

到目前為止，我們介紹的3種排序算法都擁有O(n^2)的運行時間。然而，我們可以利用一些復雜度為O(nlogn)的更好的算法。這些更好的算法都采用了 分而治之（divide-and-conquer） 的策略，也就是說，每個算法都找到了一種方法，將列表分解為更小的子列表，隨后，這些子列表再遞歸的排序。理想情況下，如果這些子列表的復雜度為log(n)，而重新排列每一個子列表中的數據所需的工作量為n，那么，這樣的排序算法總的復雜度就是O(nlogn)。

快速排序

快速排序所使用的策略可以概括如下：

（1）首先，從列表的中點位置選取一項。這一項叫作 基準點 。

（2）將列表中的項分區，以便小于基準點的所有項都移動到基準點的左邊，而剩下的項都移動到基準點的右邊。根據相關的實際項，基準點自身的最終位置也是變化的。但是，不管基準點最終位于何處，這個位置都是它在完全排序的列表中的最終位置。

（3） 分而治之。對于在基準點分割列表而形成的子列表，遞歸地重復應用該過程。一個子列表包含了基準點左邊的所有的項（現在是較小的項），另一個子列表包含了基準點右邊的所有的項（現在是較大的項）。

（4）每次遇到小于2個項的一個子列表，就結束這個過程。

1.分割

從程序員的角度來看，該算法最復雜的部分就是對子列表中的項進行分割的操作。步驟如下：

（1）將基準點和子列表中的最后一項交換。

（2）在已知小于基準點的項和剩余的項之間建立一個邊界。一開始，這個邊界就放在第一項之前。

（3）從子列表的第一項開始掃描整個子列表，每次遇到小于基準點的項，就將其與邊界之后的第一項進行交換，并且邊界向后移動。

（4）將基準點和邊界之后的第一項進行交換，從而完成這個過程。

例子：

2.快速排序的復雜度分析

在第1次分割操作中，從列表頭部到其尾部掃描了所有的項。因此， 這個操作過程的工作量和列表的長度n成正比 。

在這次分割之后的工作量，和左邊的子列表的長度加上右邊的子列表的長度（加在一起是n-1）成正比。當再次分割這些子列表的時候，有了4個子列表，它們組合在一起的長度近似為n， 因此，組合的工作量還是和n成正比的 。隨著將列表分割為更多的子列表，總的工作量還是和n成正比。

然后我們需要確定 對列表分割多少次 。 如果每一次新的子列表之間的分割線都盡可能地靠近當前子列表的中央，大概經過log2n步之后會得到一個單個的元素 。因此，這個算法在最好的情況下的性能為 O(nlog2n) 。

對于最壞的情況，考慮一個列表已經排好序的情況。如果所選擇的基準點元素是第1個元素，那么在第1次分割的時候，基準點的右邊有n-1個元素，在第2次分割的時候，基準點的右邊有n-2個元素，依次類推，因此，在最壞的情況下，快速排序算法的性能是O(n^2)。

如果將快速排序實現為一個遞歸算法，你的分析還必須考慮到調用棧所使用的內存。 每一次遞歸調用都需要一個固定大小的內存用于棧 ，并且每一次分割之后有兩次遞歸調用。因此， 在最好的情況下，內存使用是O(log2n)，在最壞的情況下，內存使用是O(n) 。

3.快速排序的實現

快速排序使用遞歸算法更容易編碼。

            
              def quicksort(lyst):
    quicksortHelper(lyst, 0, len(lyst) - 1)

def quicksortHelper(lyst, left, right):
    if left < right:
        pivotLocation = partition(lyst, left, right)
        quicksortHelper(lyst, left, pivotLocation - 1)
        quicksortHelper(lyst, pivotLocation + 1, right)

def partition(lyst, left, right):
    # Find the pivot and exchange it with the last item
    middle = (left + right) // 2
    pivot = lyst[middle]
    lyst[middle] = lyst[right]
    lyst[right] = pivot
    # Set boundary point to first position
    boundary = left
    # Move items less than pivot to the left
    for index in range(left, right):
        if lyst[index] < pivot:
            swap(lyst, index, boundary)
            boundary += 1
    # Exchange the pivot item and the boundary item
    swap (lyst, right, boundary)
    return boundary

def swap(lyst, i, j):
    """Exchanges the items at positions i and j."""
    # You could say lyst[i], lyst[j] = lyst[j], lyst[i]
    # but the following code shows what is really going on
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp


import random


def main(size = 20, sort = quicksort):
    lyst = []
    for count in range(size):
        lyst.append(random.randint(1, size + 1))
    print(lyst)
    sort(lyst)
    print(lyst)

if __name__ == "__main__":
    main() 
            
          

合并排序

另一種名為合并排序（merge sort，又稱為歸并排序）的算法利用了 遞歸、分而治之 的策略來突破O(n^2)的障礙。如下是該算法的一個非正式的概述：

（1）計算一個列表的中間位置，并且遞歸地排序其左邊和右邊的子列表（分而治之）。

（2）將兩個排好序的子列表重新合并為單個的排好序的列表。

（3）當子列表不再能夠劃分的時候，停止這個過程。

有3個Python函數在這個頂層的設計策略中協作：

（1）mergeSort——用戶調用的函數。

（2）mergeSortHelper——一個輔助函數，它隱藏了遞歸調用所需要的額外參數。

（3）Merge——實現合并過程的一個函數。

1.實現合并過程

合并的過程使用了和列表相同大小的一個數組，這個數組名為copyBuffer，為了避免每次調用merge的時候為copyBuffer分配和釋放內存的開銷，只在mergeSort中分配一次該緩沖區，并且在后續將其作為一個參數傳遞給mergeSortHelper和merge，每次調用mergeSortHelper的時候，都需要知道它所操作的子列表的邊界。這些邊界通過另外的參數low和high來提供，如下是mergeSort的代碼：

            
              from arrays import Array

def mergeSort(lyst):
    # lyst: list being sorted
    # copyBuffer: temporary space needed during merge
    copyBuffer = Array(len(lyst))
    mergeSortHelper(lyst,copyBuffer,0,len(lyst)-1)
            
          

在檢查到至少有兩項的一個子列表已經傳遞給它之后，mergeSortHelper函數計算了這個子列表的中點， 遞歸地對中點以上和中點以下的部分進行排序，并且調用merge來合并結果 。如下是mergeSortHelper的代碼：

            
              def mergeSortHelper(lyst,copyBuffer,low,high):
    # lyst: list being sorted
    # copyBuffer: temp space needed during merge
    # low,high : bounds of sublist
    # middle: midpoint of sublist
    if low < high:
        middle = (low+high)//2
        mergeSortHelper(lyst,copyBuffer,low,middle)
        mergeSortHelper(lyst,copyBuffer,middle+1,high)
        merge(lyst,copyBuffer,low,middle,high)
            
          

下圖展示了在對擁有8項的一個列表開始遞歸調用mergeSortHelper的過程中所生成的子列表。注意，在這個例子中，子列表在每一個層級都是平均劃分的，在第k層，有2^k個子列表需要合并。 如果最初列表的長度不是2的冪，那么，無法在每一個層級都做到完全平均的劃分，并且最后的層級將不會擁有足夠的子列表 。

最后，下面是merge函數的代碼：

            
              def merge(lyst,copyBuffer,low,middle,high):
    # Initialize i1 and i2 to the first items in each sublist
    i1 = low
    i2 = middle + 1

    # Interleave items from the sublists into the copyBuffer in such a way that order is maintained.
    for i in range(low,high+1):
        if i1 > middle:
            copyBuffer[i] = lyst[i2] # 列表1已經用完
            i2 += 1
        elif i2 > high:
            copyBuffer[i] = lyst[i1] # 列表2已經用完
            i1 += 1
        elif lyst[i1] < lyst[i2]:
            copyBuffer[i] = lyst[i1] # 將小的數放上去
            i1 += 1
        else:
            copyBuffer[i] = lyst[i2] # 將小的數放上去
            i2 += 1

    for i in range(low,high+1):
        lyst[i] = copyBuffer[i] # 排序完的copyBuffer返回給lyst
            
          

merge函數將兩個排好序的子列表合并到一個大的排好序的子列表中。第1個子列表在low和middle之間，第2個子列表在middle+1和high之間，這個過程包含步驟：

（1）將索引指針設置為每個子列表的第1項，這分別是low和middle+1的位置。

（2）從每個子列表的第1項開始，重復地比較各項。將較小的項從其子列表中復制到緩存中去，并且繼續處理子列表中的下一項。重復這個過程，直到兩個子列表中的所有項都已經復制過了。 如果先到達了其中一個子列表的末尾，通過從另一個子列表復制剩余的項，從而結束這個過程 。

（3）將copyBuffer中low到high之間的部分，復制回lyst對應的位置。

2.合并排序的復雜度分析

合并排序的運行時間由兩條for語句主導，其中每一條都循環(high-low+1)次，結果，該函數的運行時間是O(high-low)，在一個層的所有合并花費的時間是O(n)。由于mergeSortHelper在每一層都是盡可能平均地分割子列表，層級數是O(logn)，并且在所有情況下，該函數的最大運行時間是O(nlogn)。

根據列表的大小，合并排序有兩個空間需求，首先，在支持遞歸調用的調用棧上，需要O(logn)的空間，其次，復制緩存需要使用O(n)的空間。

指數算法：遞歸式的Fibonacci

遞歸實現

如果我們采用遞歸的Fibonacci函數來實現，調用的次數似乎比問題規模的平方增長的還要快，具體代碼如下：

            
              from counter import Counter

def fib(n, counter):
    """Count the number of calls of the Fibonacci
    function."""
    counter.increment()
    if n < 3:
        return 1
    else:
        return fib(n - 1, counter) + fib(n - 2, counter)

problemSize = 2
print("%12s%15s" % ("Problem Size", "Calls"))
for count in range(5):
    counter = Counter()

    # The start of the algorithm
    fib(problemSize, counter)
    # The end of the algorithm
    
    print("%12d%15s" % (problemSize, counter))
    problemSize *= 2
            
          

counter函數如下：

            
              class Counter(object):
    """Models a counter."""
    
    # Class variable
    instances = 0
    
   #Constructor
    def __init__(self):
        """Sets up the counter."""
        Counter.instances += 1
        self.reset()
        
    # Mutator methods
    def reset(self):
        """Sets the counter to 0."""
        self._value = 0
        
    def increment(self, amount = 1):
        """Adds amount to the counter."""
        self._value += amount
        

    def decrement(self, amount = 1):
       """Subtracts amount from the counter."""
       self._value -= amount
        

    # Accessor methods
    def getValue(self):
        """Returns the counter's value."""
        return self._value
    

    def __str__(self):
        """Returns the string representation of the counter."""
        return str(self._value)
    
    def __eq__(self, other):
        """Returns True if self equals other

        or False otherwise."""
        if self is other: return True
        if type(self) != type(other): return False
        return self._value == other._value
            
          

結果如下：

            
              Problem Size          Calls
           2              1
           4              5
           8             41
          16           1973
          32        4356617
            
          

說明工作量的快速增長的另一種方式是顯示該函數針對給定的問題規模的一個調用樹，下圖展示了當使用遞歸函數來計算第6個斐波那契數的時候所用到的調用。

注意：每個填滿的層級上的調用綜述，都是其上一個層級的調用總數的兩倍。因此，完全平衡樹的遞歸調用次數通常是2^(n+1)-2，其中n是調用樹的頂部或者根部的參數，這顯然是一個指數級的O(k^n)的算法。

指數算法通常只對較小的問題規模才切合實際。盡管遞歸的Fibonacci在設計上很優雅，但是和使用循環按照線性時間運行的較快版本相比，它還是差很多。

此外，使用相同參數重復調用的遞歸函數，例如Fibonacci函數，可以通過一種叫作記憶（memoization）的技術，來使得其更有效率，根據這個技術，程序維護一張記錄了函數中所使用的每一個參數的值的表。在函數遞歸地計算一個給定參數的值之前，它會檢查這張表，看看該參數是否已經有了一個值了。如果是的，就直接返回這個值。如果沒有，繼續計算過程，并且隨后會將參數和值添加到這個表中。

Fibonacci函數轉換為一個線性算法

這種算法可以將復雜度降低到線性時間階。

            
              class Counter(object):
    """Tracks a count."""

    def __init__(self):
        self._number = 0

    def increment(self):
        self._number += 1

    def __str__(self):
        return str(self._number)

def fib(n, counter):
    """Count the number of iterations in the Fibonacci
    function."""
    sum = 1
    first = 1
    second = 1
    count = 3
    while count <= n:
        counter.increment()
        sum = first + second
        first = second
        second = sum
        count += 1
    return sum

problemSize = 2
print("%12s%15s" % ("Problem Size", "Iterations"))
for count in range(5):
    counter = Counter()

    # The start of the algorithm
    fib(problemSize, counter)
    # The end of the algorithm
    
    print("%12d%15s" % (problemSize, counter))
    problemSize *= 2
            
          

結果如下：

            
              Problem Size     Iterations
           2              0
           4              2
           8              6
          16             14
          32             30
            
          

這里可以看出，該函數的新版本的性能已經提升到了線性階。

本文是數據結構（用Python實現）這本書的讀書筆記！