概述

算法是計(jì)算機(jī)程序的一個(gè)基本的構(gòu)建模塊。評(píng)價(jià)算法質(zhì)量的最基本的標(biāo)準(zhǔn)是正確性，另一個(gè)重要的標(biāo)準(zhǔn)是運(yùn)行時(shí)間性能。當(dāng)在一臺(tái)真實(shí)、資源有限的計(jì)算機(jī)上運(yùn)行一個(gè)算法的時(shí)候，經(jīng)濟(jì)性的考慮就有了用武之地，這樣一個(gè)過(guò)程會(huì)消耗兩種資源：處理時(shí)間和空間或內(nèi)存。

統(tǒng)計(jì)指令

用于估算算法性能的另一種技術(shù)是統(tǒng)計(jì)對(duì)不同的問(wèn)題規(guī)模所要執(zhí)行的指令的數(shù)目。不管算法在什么平臺(tái)上運(yùn)行，這個(gè)統(tǒng)計(jì)數(shù)字對(duì)于算法所要執(zhí)行的抽象的工作量給出了一個(gè)很好的預(yù)計(jì)。然而要記住，當(dāng)統(tǒng)計(jì)指令的時(shí)候， 所統(tǒng)計(jì)的是用于編寫算法的較高級(jí)代碼中的指令數(shù)目，而不是執(zhí)行機(jī)器語(yǔ)言的程序中的指令數(shù)目 。

當(dāng)以這種方式分析算法的時(shí)候，你需要區(qū)分兩種指令：

（1）不管問(wèn)題規(guī)模多大，都執(zhí)行相同次數(shù)的指令

（2）根據(jù)問(wèn)題的規(guī)模，執(zhí)行不同次數(shù)的指令

現(xiàn)在，我們先忽略第一類指令，因?yàn)樗鼈兊挠绊懖⒉伙@著，第二類指令通常在循環(huán)或遞歸函數(shù)中可以找到。

復(fù)雜度分析

復(fù)雜度的階

大O表示法

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

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

搜索算法

搜索最小值

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

            
              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))
            
          

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

順序搜索一個(gè)列表

Python的in運(yùn)算符作為list類中名為_(kāi)_contains__的一個(gè)方法而實(shí)現(xiàn)。該方法在列表（任意排列的項(xiàng)）中搜索一個(gè)特定的項(xiàng)（叫做目標(biāo)項(xiàng)）。在這樣的一個(gè)列表中搜索一個(gè)目標(biāo)項(xiàng)的唯一的方法是，從第1個(gè)位置的項(xiàng)開(kāi)始，將其與目標(biāo)項(xiàng)進(jìn)行比較，如果這兩個(gè)項(xiàng)相等，該方法返回一個(gè)True。否則，該方法移動(dòng)到下一個(gè)位置并且將其項(xiàng)與目標(biāo)項(xiàng)進(jìn)行比較。如果該方法到達(dá)了最后一個(gè)位置，卻仍然沒(méi)有找到目標(biāo)項(xiàng)，它就返回False。這種搜索叫做 順序搜索 （sequential search）或 線性搜索 （linear search）。一個(gè)更為有用的順序搜索函數(shù)，應(yīng)該返回它所找到的目標(biāo)項(xiàng)的索引，或者如果沒(méi)有找到目標(biāo)項(xiàng)的話，返回-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))
            
          

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

有些算法的性能取決于所處數(shù)據(jù)的放置方式。順序搜索算法在查找一個(gè)目標(biāo)項(xiàng)的時(shí)候，在列表的開(kāi)頭處所做的工作比在列表的末尾所做的工作要少。對(duì)于這樣的算法，我們可以確定其最好情況的性能、最壞情況的性能和平均情況的性能。 通常一般考慮的是最壞情況的性能和平均情況的性能 。

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

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

（2）在最好的情況下，算法只進(jìn)行了1次迭代就在第1個(gè)位置找到目標(biāo)項(xiàng)，復(fù)雜度為O(1)。

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

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

有序列表的二叉搜索

對(duì)于那些沒(méi)有按照特定的順序排列的數(shù)據(jù)，順序搜索是必要的。 當(dāng)搜索經(jīng)過(guò)排序的數(shù)據(jù)的時(shí)候，可以使用二叉搜索（又稱為二分搜索）。

現(xiàn)在來(lái)考慮Python實(shí)現(xiàn)二叉搜索的一個(gè)示例。首先，假設(shè)列表中的項(xiàng)都是按照升序排列的，搜索算法直接找到列表的中間位置，并且將該位置的項(xiàng)和目標(biāo)項(xiàng)進(jìn)行比較。如果它們是一致的，算法返回該位置。否則，如果目標(biāo)項(xiàng)小于當(dāng)前項(xiàng)，算法搜索列表中間位置以前的部分。反之，搜索中間以后的部分。

            
              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
            
          

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

比較數(shù)據(jù)項(xiàng)

二叉搜索和搜索最小項(xiàng)，都是假設(shè)列表中的項(xiàng)是可以相互比較的。在Python中，這意味著這些項(xiàng)具有相同的類型，并且它們都識(shí)別比較運(yùn)算符==、<和>。幾個(gè)內(nèi)建的Python類型的對(duì)象，例如數(shù)字、字符串和列表，都可以使用這些運(yùn)算符來(lái)比較。

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

            
              def __lt__(self,other):
            
          

如果self小于other，該方法返回True，否則，它返回False。 比較對(duì)象的標(biāo)準(zhǔn)，取決于它們內(nèi)部的結(jié)構(gòu)，以及應(yīng)該以何種方式對(duì)其排 序。

例如，SavingAccount對(duì)象可能包含3個(gè)數(shù)據(jù)字段，一個(gè)用于名稱，一個(gè)用于PIN，還有一個(gè)用余額。假設(shè)賬戶應(yīng)該按照名稱的字母順序來(lái)排序，那么，需要對(duì)__lt__方法按照如下的方式來(lái)實(shí)現(xiàn)：

            
              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__方法對(duì)兩個(gè)賬戶對(duì)象的_name字段調(diào)用了<運(yùn)算符（名稱是字符串），并且字符串類型已經(jīng)包含了一個(gè)__lt__方法。當(dāng)對(duì)字符串應(yīng)用<運(yùn)算符的時(shí)候，Python自動(dòng)運(yùn)行__lt__方法。就像是在調(diào)用str函數(shù)時(shí)運(yùn)行str方法一樣。

基本排序算法

這里介紹的幾個(gè)算法很容易編寫，但是效率不高，下一節(jié)介紹的算法都很難編寫，但是更為高效（這是一種常見(jiàn)的取舍）。每個(gè)Python排序函數(shù)都是在整數(shù)的一個(gè)列表上進(jìn)行操作的，并且都會(huì)使用一個(gè)swap函數(shù)來(lái)交換列表中的兩項(xiàng)的位置。

swap函數(shù)的代碼如下：

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

選擇排序

最簡(jiǎn)單的策略就是搜索整個(gè)列表，找到最小項(xiàng)的位置。 如果該位置不是列表的第1個(gè)位置，算法就會(huì)交換在這兩個(gè)位置的項(xiàng)，然后，算法回到第2個(gè)位置并且重復(fù)這個(gè)過(guò)程，如果必要的話，將最小項(xiàng)和第2個(gè)位置的項(xiàng)進(jìn)行交換。當(dāng)算法到達(dá)整個(gè)過(guò)程的最后一個(gè)位置，列表就是排序好的了。這個(gè)算法叫做選擇排序（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
            
          

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

冒泡排序

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

            
              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
            
          

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

插入排序

（1）在第i輪通過(guò)列表的時(shí)候（其中i的范圍從1到n-1），第i個(gè)項(xiàng)應(yīng)該插入到列表的前i個(gè)項(xiàng)之中的正確位置。

（2）在第i輪之后，前i個(gè)項(xiàng)應(yīng)該是排好序的。

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

（4）插入排序包括兩個(gè)循環(huán)。外圍的循環(huán)遍歷從1到n-1的位置。對(duì)于這個(gè)循環(huán)中的每一個(gè)位置i，我們都保存該項(xiàng)并且從位置i-1開(kāi)始內(nèi)部循環(huán)。

            
              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

            
          

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

更快的排序

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

快速排序

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

（1）首先，從列表的中點(diǎn)位置選取一項(xiàng)。這一項(xiàng)叫作 基準(zhǔn)點(diǎn) 。

（2）將列表中的項(xiàng)分區(qū)，以便小于基準(zhǔn)點(diǎn)的所有項(xiàng)都移動(dòng)到基準(zhǔn)點(diǎn)的左邊，而剩下的項(xiàng)都移動(dòng)到基準(zhǔn)點(diǎn)的右邊。根據(jù)相關(guān)的實(shí)際項(xiàng)，基準(zhǔn)點(diǎn)自身的最終位置也是變化的。但是，不管基準(zhǔn)點(diǎn)最終位于何處，這個(gè)位置都是它在完全排序的列表中的最終位置。

（3） 分而治之。對(duì)于在基準(zhǔn)點(diǎn)分割列表而形成的子列表，遞歸地重復(fù)應(yīng)用該過(guò)程。一個(gè)子列表包含了基準(zhǔn)點(diǎn)左邊的所有的項(xiàng)（現(xiàn)在是較小的項(xiàng)），另一個(gè)子列表包含了基準(zhǔn)點(diǎn)右邊的所有的項(xiàng)（現(xiàn)在是較大的項(xiàng)）。

（4）每次遇到小于2個(gè)項(xiàng)的一個(gè)子列表，就結(jié)束這個(gè)過(guò)程。

1.分割

從程序員的角度來(lái)看，該算法最復(fù)雜的部分就是對(duì)子列表中的項(xiàng)進(jìn)行分割的操作。步驟如下：

（1）將基準(zhǔn)點(diǎn)和子列表中的最后一項(xiàng)交換。

（2）在已知小于基準(zhǔn)點(diǎn)的項(xiàng)和剩余的項(xiàng)之間建立一個(gè)邊界。一開(kāi)始，這個(gè)邊界就放在第一項(xiàng)之前。

（3）從子列表的第一項(xiàng)開(kāi)始掃描整個(gè)子列表，每次遇到小于基準(zhǔn)點(diǎn)的項(xiàng)，就將其與邊界之后的第一項(xiàng)進(jìn)行交換，并且邊界向后移動(dòng)。

（4）將基準(zhǔn)點(diǎn)和邊界之后的第一項(xiàng)進(jìn)行交換，從而完成這個(gè)過(guò)程。

例子：

2.快速排序的復(fù)雜度分析

在第1次分割操作中，從列表頭部到其尾部掃描了所有的項(xiàng)。因此， 這個(gè)操作過(guò)程的工作量和列表的長(zhǎng)度n成正比 。

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

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

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

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

3.快速排序的實(shí)現(xiàn)

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

            
              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，又稱為歸并排序）的算法利用了 遞歸、分而治之 的策略來(lái)突破O(n^2)的障礙。如下是該算法的一個(gè)非正式的概述：

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

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

（3）當(dāng)子列表不再能夠劃分的時(shí)候，停止這個(gè)過(guò)程。

有3個(gè)Python函數(shù)在這個(gè)頂層的設(shè)計(jì)策略中協(xié)作：

（1）mergeSort——用戶調(diào)用的函數(shù)。

（2）mergeSortHelper——一個(gè)輔助函數(shù)，它隱藏了遞歸調(diào)用所需要的額外參數(shù)。

（3）Merge——實(shí)現(xiàn)合并過(guò)程的一個(gè)函數(shù)。

1.實(shí)現(xiàn)合并過(guò)程

合并的過(guò)程使用了和列表相同大小的一個(gè)數(shù)組，這個(gè)數(shù)組名為copyBuffer，為了避免每次調(diào)用merge的時(shí)候?yàn)閏opyBuffer分配和釋放內(nèi)存的開(kāi)銷，只在mergeSort中分配一次該緩沖區(qū)，并且在后續(xù)將其作為一個(gè)參數(shù)傳遞給mergeSortHelper和merge，每次調(diào)用mergeSortHelper的時(shí)候，都需要知道它所操作的子列表的邊界。這些邊界通過(guò)另外的參數(shù)low和high來(lái)提供，如下是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)
            
          

在檢查到至少有兩項(xiàng)的一個(gè)子列表已經(jīng)傳遞給它之后，mergeSortHelper函數(shù)計(jì)算了這個(gè)子列表的中點(diǎn)， 遞歸地對(duì)中點(diǎn)以上和中點(diǎn)以下的部分進(jìn)行排序，并且調(diào)用merge來(lái)合并結(jié)果 。如下是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)
            
          

下圖展示了在對(duì)擁有8項(xiàng)的一個(gè)列表開(kāi)始遞歸調(diào)用mergeSortHelper的過(guò)程中所生成的子列表。注意，在這個(gè)例子中，子列表在每一個(gè)層級(jí)都是平均劃分的，在第k層，有2^k個(gè)子列表需要合并。 如果最初列表的長(zhǎng)度不是2的冪，那么，無(wú)法在每一個(gè)層級(jí)都做到完全平均的劃分，并且最后的層級(jí)將不會(huì)擁有足夠的子列表 。

最后，下面是merge函數(shù)的代碼：

            
              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已經(jīng)用完
            i2 += 1
        elif i2 > high:
            copyBuffer[i] = lyst[i1] # 列表2已經(jīng)用完
            i1 += 1
        elif lyst[i1] < lyst[i2]:
            copyBuffer[i] = lyst[i1] # 將小的數(shù)放上去
            i1 += 1
        else:
            copyBuffer[i] = lyst[i2] # 將小的數(shù)放上去
            i2 += 1

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

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

（1）將索引指針設(shè)置為每個(gè)子列表的第1項(xiàng)，這分別是low和middle+1的位置。

（2）從每個(gè)子列表的第1項(xiàng)開(kāi)始，重復(fù)地比較各項(xiàng)。將較小的項(xiàng)從其子列表中復(fù)制到緩存中去，并且繼續(xù)處理子列表中的下一項(xiàng)。重復(fù)這個(gè)過(guò)程，直到兩個(gè)子列表中的所有項(xiàng)都已經(jīng)復(fù)制過(guò)了。 如果先到達(dá)了其中一個(gè)子列表的末尾，通過(guò)從另一個(gè)子列表復(fù)制剩余的項(xiàng)，從而結(jié)束這個(gè)過(guò)程 。

（3）將copyBuffer中l(wèi)ow到high之間的部分，復(fù)制回lyst對(duì)應(yīng)的位置。

2.合并排序的復(fù)雜度分析

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

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

指數(shù)算法：遞歸式的Fibonacci

遞歸實(shí)現(xiàn)

如果我們采用遞歸的Fibonacci函數(shù)來(lái)實(shí)現(xiàn)，調(diào)用的次數(shù)似乎比問(wèn)題規(guī)模的平方增長(zhǎng)的還要快，具體代碼如下：

            
              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函數(shù)如下：

            
              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
            
          

結(jié)果如下：

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

說(shuō)明工作量的快速增長(zhǎng)的另一種方式是顯示該函數(shù)針對(duì)給定的問(wèn)題規(guī)模的一個(gè)調(diào)用樹(shù)，下圖展示了當(dāng)使用遞歸函數(shù)來(lái)計(jì)算第6個(gè)斐波那契數(shù)的時(shí)候所用到的調(diào)用。

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

指數(shù)算法通常只對(duì)較小的問(wèn)題規(guī)模才切合實(shí)際。盡管遞歸的Fibonacci在設(shè)計(jì)上很優(yōu)雅，但是和使用循環(huán)按照線性時(shí)間運(yùn)行的較快版本相比，它還是差很多。

此外，使用相同參數(shù)重復(fù)調(diào)用的遞歸函數(shù)，例如Fibonacci函數(shù)，可以通過(guò)一種叫作記憶（memoization）的技術(shù)，來(lái)使得其更有效率，根據(jù)這個(gè)技術(shù)，程序維護(hù)一張記錄了函數(shù)中所使用的每一個(gè)參數(shù)的值的表。在函數(shù)遞歸地計(jì)算一個(gè)給定參數(shù)的值之前，它會(huì)檢查這張表，看看該參數(shù)是否已經(jīng)有了一個(gè)值了。如果是的，就直接返回這個(gè)值。如果沒(méi)有，繼續(xù)計(jì)算過(guò)程，并且隨后會(huì)將參數(shù)和值添加到這個(gè)表中。

Fibonacci函數(shù)轉(zhuǎn)換為一個(gè)線性算法

這種算法可以將復(fù)雜度降低到線性時(shí)間階。

            
              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
            
          

結(jié)果如下：

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

這里可以看出，該函數(shù)的新版本的性能已經(jīng)提升到了線性階。

本文是數(shù)據(jù)結(jié)構(gòu)（用Python實(shí)現(xiàn)）這本書的讀書筆記！