1.3 算法分析

當(dāng)我們開始處理包含數(shù)據(jù)集合的程序時，除了需要知道它的先驗條件和后置條件，通常還需要了解更多。處理一個包含10個甚至100個考試分數(shù)的列表倒是沒有任何問題的，但是線上商業(yè)的客戶列表可能包含成千上萬個元素；處理生物學(xué)問題的程序員可能得處理含有數(shù)百萬甚至數(shù)十億個核苷酸的DNA序列；搜索和索引網(wǎng)頁的應(yīng)用程序也需要處理類似數(shù)量級的數(shù)據(jù)集。當(dāng)數(shù)據(jù)集越來越大時，算法的效率就會和它的正確性同樣重要。如果一個算法能夠提供正確答案但需要10年計算時間，就明顯不太可能有實際用處。

通過算法分析，我們可以根據(jù)完成任務(wù)所需的時間和內(nèi)存使用狀況來評估算法。在本節(jié)中，我們將首先通過搜索數(shù)據(jù)集來了解算法分析技術(shù)。

1.3.1 線性搜索

搜索是指在集合中查找特定值的這一過程。例如一個維護俱樂部成員列表的程序可能需要查找特定成員的相關(guān)信息。這就涉及某種形式的搜索。搜索對我們來說是一個很好的問題，因為有許多相對效率不同的搜索算法可以用于對比。

為了透過現(xiàn)象看本質(zhì)，我們可以用在列表里查找特定數(shù)字這一問題來簡化我們的搜索問題。而且，在這里使用的原則將同樣適用于更復(fù)雜的搜索問題，例如搜索客戶列表以查找居住在愛荷華州的人。這個簡單搜索問題的規(guī)范如下所示：

def search(items, target):
    """Locate target in items
    pre: items is a list of numbers
    post: returns non-negative x where items[x] == target, if target in
          items; returns -1, otherwise"""

下面是一些可以說明其行為的交互式示例：

>>> search([3, 1, 4, 2, 5], 4)
2
>>> search([3, 1, 4, 2, 5], 7)
-1

在第一個例子里，函數(shù)會返回列表中元素4的索引。而在第二個示例中，返回值-1表示7不在列表中。

利用Python內(nèi)置的列表函數(shù)，我們可以輕松實現(xiàn)search功能：

# search1.py
def search(items, target):
    try:
        return items.index(target)
    except ValueError:
        return -1

index函數(shù)用于從列表中找出某個值第一個匹配項的索引位置。如果target不在列表中，則index函數(shù)會拋出ValueError異常。在這里，程序捕獲這個異常并返回-1。很明顯，我們實現(xiàn)的這個函數(shù)符合定義的規(guī)范；更有趣的一個問題是：這種函數(shù)的效率怎么樣？

一種用來確定算法效率的方法是進行實證檢驗。我們可以簡單地實現(xiàn)這個算法，并且用不同的數(shù)據(jù)集來驗證它，以查看需要多長時間。在Python里提供了計時相關(guān)的代碼，可以簡單地使用時間模塊（time）中的time時間函數(shù)來實現(xiàn)，它會返回從1970年1月1日開始到現(xiàn)在所經(jīng)過的秒數(shù)。我們可以在相關(guān)代碼執(zhí)行之前和之后調(diào)用這個方法，再輸出前后之間的差異。當(dāng)將搜索功能放在名為search1.py的模塊中之后，我們可以用下面的代碼直接驗證它：

# time_search.py
import time
from search1 import search
items = range(1000000) # create a big list
start = time.time()
search(items, 999999) # look for the last item
stop = time.time()
print stop - start
start = time.time()
search(items, 499999) # look for the middle item
stop = time.time()
print stop - start
start = time.time()
search(items, 10) # look for an item near the front
stop = time.time()
print stop - start

你可以在你自己的計算機上運行這段代碼，并且記下搜索3個數(shù)字的時間。根據(jù)這3個時間，你能知道index函數(shù)是如何工作的嗎？順便說一下，Python庫里還包含了一個名叫timeit的模塊，它提供了更為精確和復(fù)雜的計時方式。如果你需要進行大量的實證檢驗，那么值得深入研究一下這個模塊。

讓我們自己也像計算機一樣來思考，嘗試開發(fā)我們自己的搜索算法。假設(shè)有滿滿一頁沒有特定順序的數(shù)字，需要判斷數(shù)字13是否在這個列表中，你會怎么來解決這個問題？你可以像大多數(shù)人一樣，簡單地一個一個元素地掃描整個列表，并且把每個值與13進行比較。然后當(dāng)你找到13的時候，退出掃描并告訴我你找到了它。而如果直到列表的最后都沒有找到13的話，你會告訴我它不在這一頁里。

這種策略被稱為線性搜索（linear search），即逐個元素地搜索整個列表，直到找到目標值為止。這個算法可以直接寫成下面這樣簡單的代碼：

# search2.py
def search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

可以看到在代碼里有一個簡單的for循環(huán)遍歷整個列表的有效索引（range (len(items))）。程序在每個位置都會判斷這個元素是不是我們的目標（target）。如果找到了目標，則立刻終止循環(huán)，并返回這個位置的索引。而如果這個循環(huán)直到結(jié)束都沒有找到目標元素，則該函數(shù)返回-1。

這樣寫函數(shù)有一個問題：range表達式會創(chuàng)建一個與要搜索的列表大小相同的索引列表。而由于int通常需要4字節(jié)（32位）的存儲空間，所以當(dāng)有一個百萬級的數(shù)字列表的時候，代碼中的索引列表需要4MB的內(nèi)存。除了內(nèi)存使用情況，創(chuàng)建這樣的第二個大列表也會浪費相當(dāng)多的時間。Python有另一個名為xrange的表達式可以替代range使用。xrange只能被用在迭代里，而且它在運行的時候也不會創(chuàng)建一個新列表。要注意，在新的Python代碼中不再鼓勵使用xrange。

如果你的Python版本是2.3或更高版本，你也可以使用enumerate函數(shù)。這種優(yōu)雅的替代方案允許你遍歷列表，并且在每次迭代的時候，你都能獲得下一個元素和它的索引。下面是使用enumerate進行搜索的方式：

# search3.py
def search(items, target):
    for i,item in enumerate(items):
        if item == target:
            return i
    return -1

還有一種方法是使用while循環(huán)來避免使用range/xrange/enumerate時產(chǎn)生的問題：

# search4.py
def search(items, target):
    i = 0
    while i < len(items):
        if items[i] == target:
            return i
        i += 1
    return -1

注意一下，所有這些搜索功能的實現(xiàn)都使用了相同的算法——線性搜索。那么這個算法效率怎么樣？要想知道怎么評判，你可以先嘗試使用它。就像你已經(jīng)記錄過的3個使用列表index方法的時間一樣。你唯一需要更改的是導(dǎo)入前面實現(xiàn)的這些search功能，它們的參數(shù)和返回值是相同的。正是因為我們定義了一個規(guī)范，所以擁有不同的函數(shù)實現(xiàn)，客戶端代碼也不需要改變。這就是工作中常用到的實現(xiàn)的獨立性。很酷，對吧？

1.3.2 二分搜索

線性搜索算法并不難實現(xiàn)，并且它對中等大小的列表處理得很好。對于無序列表來說，線性搜索算法和其他任何算法都一樣好。Python里的in和index操作都實現(xiàn)了線性搜索算法。

如果我們遇到的是一個非常大的數(shù)據(jù)集合，這種情況下可能會希望數(shù)據(jù)按照某種方式進行組織，這樣我們就不用查看每個元素來判斷目標值在這個列表中的位置，或者是不是存在于這個列表。假設(shè)這個列表按順序（從低到高）存儲。一旦程序遇到了一個大于目標值的值，就可以退出線性搜索了，而不需要繼續(xù)查看列表的其余部分。平均來說，這能夠節(jié)約大概一半的工作量。實際上，如果列表已經(jīng)有序，我們甚至可以做得更好。

當(dāng)列表已經(jīng)有序的時候，你可能已經(jīng)知道了一個更好的搜索策略。還記得玩過的猜數(shù)游戲嗎？我選擇一個1～100的數(shù)字，你試著猜它是什么。每次你猜的時候，我都會告訴你你的猜測是正確、太高還是太低。那么你的策略是什么呢？

如果你和一個年紀非常小的孩子一起玩這個游戲，他很可能會采用一種隨機猜測數(shù)字的策略。而稍微大一些的孩子可能會采用與線性搜索相對應(yīng)的方法——猜測1、2、3、4等，直到找到那個值。

當(dāng)然，幾乎所有成年人都會先猜50。如果被告知目標值要高一些，那么它可能的范圍就是50～100。下一步就可以猜75。每次我們都猜測剩余數(shù)字的中間位置來嘗試縮小可能的范圍。這種策略被稱為二分搜索（binary search）。所謂的“二分”，也就是在每一步都把剩下的數(shù)字分成兩部分。

我們可以使用二分搜索策略來查看一個有序列表。其本質(zhì)上是使用兩個變量來跟蹤目標值可能在列表中的范圍的兩個端點。最初情況下，目標值可以在列表中的任何位置，因此我們將變量low和high分別設(shè)置為列表的第一個和最后一個位置。

這個算法的核心是一個查看剩余范圍中間元素與x進行比較的循環(huán)。如果x小于中間項，那么我們移動high變量，以便搜索縮小到較小的那半個部分；而如果x要大一些，那么我們移動low變量，將搜索范圍縮小到較大的那半個部分。當(dāng)找到了x或不再有任何要檢查的地方（即low > high）時，循環(huán)終止。下面的代碼在相同的搜索API里實現(xiàn)二分搜索：

# bsearch.py
def search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:          # There is still a range to search
        mid = (low + high) // 2 # position of middle item
        item = items[mid]
        if target == item :     # Found it! Return the index
            return mid
        elif target < item:     # x is in lower half of range
            high = mid - 1      #      move top marker down
        else:                   # x is in upper half
            low = mid + 1       #      move bottom marker up
    return -1                   # no range left to search
                                # x is not there

該算法比簡單的線性搜索要復(fù)雜一些。你可能會希望通過幾個示例搜索，來向自己證明它是對的。

1.3.3 非正式的算法比較

到目前為止，我們?yōu)楹唵蔚乃阉鲉栴}開發(fā)了兩種截然不同的算法。哪一個更好，取決于我們究竟認為什么是更好。例如，我們會覺得線性搜索算法更容易理解和實現(xiàn)；同時，我們可以預(yù)期二分搜索更為有效，因為它不用去查看列表里的每個值。從直覺上來說，我們可能會認為線性搜索是小型列表的更好選擇，而二分搜索則是大型列表的更好選擇。我們應(yīng)該怎樣來證實這種直覺呢？

與之前一樣，一種方法是進行實證檢驗。我們可以簡單地編寫兩種算法，通過在不同大小的列表上進行嘗試，來查看搜索需要多長時間。這些算法都不長，因此運行一些驗證并不困難。當(dāng)我們用一臺計算機（有點過時的筆記本電腦）進行此驗證時，對于長度為10或更短的列表，線性搜索更快；對于長度處于10～1000的范圍內(nèi)的列表來說，兩者沒有太大的差異；而隨著列表長度的增加，二分搜索顯然是贏家。對于一個擁有100萬個元素的列表，線性搜索平均要花2.5秒來找到一個隨機值，而二分搜索平均僅用0.0003秒。

實證分析證實了我們的直覺，但這是在特定情況下一臺特定機器的結(jié)果（固定的內(nèi)存總量、處理器速度、當(dāng)前負載等）。我們應(yīng)該怎樣保證這個特定的結(jié)果具有普適性呢？

還有一種方法是：抽象地分析各種算法來查看它們的效率。在其他因素相同的情況下，我們期望具有最少“步驟”的算法更有效。但是怎么計算步數(shù)呢？對于任意一個算法來說，其主循環(huán)的執(zhí)行次數(shù)都將取決于特定輸入。我們已經(jīng)猜到了二分搜索的優(yōu)勢會隨著列表長度的增加而增加。

為了解決這類問題，計算機科學(xué)家會分析算法要解決的特定問題的大小或難度所需采取的步驟。搜索的難度取決于集合的大小。顯然，在一個有100萬個元素的集合中找到一個數(shù)字，比在一個只有10個元素的集合中找到一個數(shù)字需要更多的步驟。相關(guān)問題是在大小為n的列表里查找值需要多少步驟。我們特別感興趣的是當(dāng)n變得非常大的時候會發(fā)生什么。

我們先來考慮線性搜索。如果列表有10個元素，算法最多會查看每個元素，因此循環(huán)最多迭代10次。假設(shè)列表有兩倍大，那么算法需要查看兩倍的元素。如果列表是3倍大，則需要查看3倍，以此類推。通常，所需的時間量與列表的大小n線性相關(guān)。因此，計算機科學(xué)家稱之為線性時間（linear time）算法。現(xiàn)在，你知道了為什么這個算法被稱為線性搜索。

那么二分搜索呢？讓我們從一個具體的例子來開始分析。假設(shè)有一個列表包含16個元素。每次循環(huán)后，剩余的范圍減半。一次循環(huán)執(zhí)行之后，還有8個元素需要考慮。下一次之后將還剩4個，然后剩下兩個，最后只有1個。循環(huán)迭代了多少次取決于在數(shù)據(jù)耗盡之前我們可以將范圍減半的次數(shù)。表1.1應(yīng)該能幫助你解決這個問題。

表1.1 列表大小和對分次數(shù)

你能發(fā)現(xiàn)表格里的規(guī)律嗎？每一次額外的循環(huán)迭代，都允許我們搜索兩倍大的列表。如果二分搜索循環(huán)i次，它可以在大小為2i的列表中找到一個值。每次循環(huán)時，它都會查看列表中的一個值（在中間位置）。要知道在大小為n的列表中一共檢查了多少個元素，我們需要解決這個關(guān)系：對于i，有n=2i。在這個公式中，i是一個基數(shù)為2的指數(shù)。利用對數(shù)，可以得到關(guān)系式i=log2n。如果你不太喜歡對數(shù)，那就記住這個值是大小為n的集合可以減半的次數(shù)就可以了。

這些數(shù)學(xué)分析告訴我們：二分搜索是對數(shù)時間算法的一個示例。解決給定問題所花費的時間隨著問題大小的對數(shù)增長而增長。在二分搜索的情況下，每次額外的迭代都會使我們可以解決的問題的大小增加一倍。

你可能不太理解二分搜索的有效性。讓我們試著把它放在這樣一個例子里。假設(shè)你有一本紐約市電話簿，其中按字母順序列出了1200萬個名字。你向走在街上的任何一個紐約人提出這樣一個建議（假設(shè)已經(jīng)知道他們的號碼）：“我會嘗試猜測你的名字。我每猜一個名字，請你告訴我你的名字是在我猜的名字按字母順序排列的之前還是之后。”你需要多少次猜測？

上面的分析顯示，這個問題的答案是log212000000。如果你沒有計算器在手邊，這里有一個快速估算的結(jié)果：210=1024或者說大概等于1000，以及1000×1000=1000000。也就是說210×210=220≈1000000。220大概就是100萬。因此，搜索100萬個名字只需要20次猜測。然后呢，我們只需要21次就能猜200萬個名字，22次猜400萬個，23次猜800萬個，24次猜測就能搜索1600萬個名字。我們只需要用24次猜測就能成功猜出紐約市任何一個陌生人的名字！相比之下，線性搜索需要（平均）600萬次猜測。因此，二分搜索是一個非常棒的算法！

我們之前說過，Python使用線性搜索算法來實現(xiàn)其內(nèi)置搜索方法。如果二分搜索更好的話，為什么Python不使用它呢？原因是二分搜索不太通用，為了能夠正常工作，進行二分搜索的列表必須有序。如果要對無序列表使用二分搜索，首先要做的就是將這個列表按照順序排列（sort）。這是計算機科學(xué)中另一個已經(jīng)經(jīng)過充分研究的問題，我們將在稍后討論它。

1.3.4 算法的正式分析

在比較線性搜索和二分搜索的時候，我們根據(jù)解決特定大小問題所需的抽象步驟的數(shù)量來評估兩種算法。我們發(fā)現(xiàn)線性搜索需要與列表大小成正比的步驟，而二分搜索則需要與列表大小的（基數(shù)為2）對數(shù)成比例的步驟。利用這種表征的好處是，它能夠告訴我們這些算法的一些信息，以及與這些信息無關(guān)的任何特定實現(xiàn)。我們預(yù)期二分搜索在大問題集上能做得更好，是因為它本身就是一種更高效的算法。

在進行這種分析時，我們通常不用關(guān)心解決特定問題的算法所需指令的確切數(shù)量，因為這是非常難以確定的。畢竟，不同的計算機機器語言、實現(xiàn)算法的不同語言，以及就像我們在搜索算法中看到的那樣，特定輸入數(shù)據(jù)的細節(jié)的不同，都會導(dǎo)致指令數(shù)量的不同。因此，我們需要抽象出不會影響算法確切運行時間的問題，也就可以忽略掉所有會影響算法在各種大小輸入上的相對性能的細節(jié)。要知道，我們的目標是確定算法在大數(shù)據(jù)量輸入時的執(zhí)行性能。現(xiàn)在的計算機速度很快，對于小規(guī)模的問題，效率一般不太可能成為瓶頸。

總而言之，在進行算法分析時，我們通常可以進行下面這些簡化。

?忽略使用不同語言和不同機器來實現(xiàn)算法所造成的差異。

?忽略各種操作的執(zhí)行速度的差異（例如，我們不會關(guān)心浮點除法計算是否比整數(shù)除法更慢）。假設(shè)所有的“基本操作”（賦值、比較、大多數(shù)數(shù)學(xué)運算等）花費相同的時間。

?假設(shè)所有與輸入大小無關(guān)的固定時間的操作都是等效的（就是說，我們不關(guān)心它是否需要10次操作、100次操作、甚至1000次操作，只要是在任意大小的輸入集里都需要執(zhí)行這些操作才能解決問題，我們就忽略它們）。

很明顯，這里的任何一個簡化都會讓比較的兩個算法的結(jié)果和實際運行時間不同，甚至?xí)ν粋€算法的不同實現(xiàn)實際運行時間產(chǎn)生顯著的影響。但這個結(jié)果仍然可以顯示我們所期望的對于輸入大小的函數(shù)值。因此，這個結(jié)果會告訴我們更大的問題的性能相對來說是什么樣的。計算機科學(xué)家們使用大O符號或者說漸近符號（asymptotic notation）來表示基于這些簡化的算法的時間復(fù)雜度。

在深入大O符號的細節(jié)之前，讓我們看幾個簡單的數(shù)學(xué)函數(shù)來獲得一些直觀感覺。假設(shè)函數(shù)f (n)=3n2+100n+50。你要在n很大的時候估計這個函數(shù)的值。這時，你應(yīng)該只考慮多項式的第一項。雖然在n比較小的時候，100n項能夠占據(jù)主導(dǎo)地位，但n變大之后，第二項和第三項對最終結(jié)果的貢獻是微不足道的。例如，在n=1000000時，只使用第一項得出的結(jié)果和函數(shù)的真實結(jié)果的差別在0.01%之內(nèi)。

你只需要看看第一項和第二項的圖形“形狀”（如圖1.2所示），就能夠明白為什么第一項在n增加時能占據(jù)主導(dǎo)地位了。從圖里可以看出，就算在0～1的范圍內(nèi)x＞x2，但只要x＞1，x2就一定會占據(jù)主導(dǎo)。所以，當(dāng)我們將x乘以某個常數(shù)（如100）時，雖然會改變那條直線的斜率，但因為函數(shù)x2向上彎曲，它仍然會超過100x（在x=100的時候）。因此，無論我們將x乘以哪個常數(shù)，這兩個圖形的形狀都表明，只要值足夠大，x2的曲線都將占主導(dǎo)地位。

圖1.2 0～1時x2＜x，但對于更大的值來說x2更大

大O符號可以用來表示這種只關(guān)注主導(dǎo)地位的函數(shù)。例如，當(dāng)算法被表示為O(n2)時就表明存在某些常數(shù)c和n0，當(dāng)n＞n0的時候，有n＜cn2。只要我們能找到這兩個常數(shù)，就能夠證明算法的時間復(fù)雜度是O(n2)。在多數(shù)情況下，它非常明顯（像上面的例子里一樣）。那么，函數(shù)3n2+100n+50的常數(shù)是什么呢？在這里我們并不需要一個嚴格的邊界。當(dāng)n＞1000000的時候，3n2+100n+50＜1000000n2，我們就可以將兩個常數(shù)都定義為1000000。如果算法是2n3，我們能找到兩個常數(shù)來證明它是O(n3)嗎？在實踐中，我們通常不太關(guān)心去找到這些常數(shù)。在大多數(shù)情況下，增長率就非常容易讓我們相信了。因為對于所有多項式，它最重要的部分都是最大的項，所以任何x次多項式都是O(nx)。

現(xiàn)在你已經(jīng)從數(shù)學(xué)細節(jié)上了解了大O符號，讓我們再看一些簡短的例子，并確定它們的運行時間：

n = input('enter n: ')
for i in range(n):
    print i

這個代碼片段的時間復(fù)雜度是O(n)，因為n的大小會決定有多少次操作——print語句將會被執(zhí)行n次，而input語句就執(zhí)行一次。讓我們仔細研究一下for語句，range語句將會生成一個包含n個元素的列表，這個生成過程就至少需要n步。每次迭代完for語句之后，變量i都會指向列表里的下一個元素，因此我們可以很容易地得出大約需要2n+1個基本步驟來執(zhí)行這個代碼片段。這也就足以表明，算法的時間復(fù)雜度是O(n)。在這里，我們忽略了在Python里也需要時間來檢測是否到達列表的末尾，因為在實際工作中，在得到代碼片段的時間復(fù)雜度的時候，我們通常不需要深入了解所有的細節(jié)。

思考下面這個代碼片段。你能確定它運行的時間復(fù)雜度嗎？

n = input('enter n: ')
for i in range(100):
    print i

晃眼一看，因為有一個for循環(huán)，你可能會認為這個代碼的時間復(fù)雜度也是O(n)。但是，在這種情況下，無論輸入的值是什么，for循環(huán)都會且只會執(zhí)行100次。本質(zhì)上來說，這和100個print語句沒有任何區(qū)別，也就可以被理解為是100個常量時間的操作。所以，無論輸入任何數(shù)值，這段代碼片段都能以相同的常量時間運行，在這里我們將所有常量操作都簡單表達為O(1)。

下面是一個有兩個循環(huán)的例子：

n = input('enter n: ')
for i in range(n):
    print i
for j in range(n):
    print j

在這個例子里，因為兩個循環(huán)按順序一個接一個地執(zhí)行，所以總共時間復(fù)雜度可以表達為O(n+n)。你可以先把它看作O(2n)，而常數(shù)乘數(shù)不會影響大O符號，因此仍然是O(n)。通常來說，當(dāng)需要將算法的順序執(zhí)行部分的時間復(fù)雜度加在一起時，整個算法的大O就是各部分的大O的最大值。這也就意味著，你只需要找到算法執(zhí)行步驟最多的部分，然后分析它，就能得到整個算法的時間復(fù)雜度。

讓我們再來看看另一個有兩個循環(huán)的例子：

n = input('enter n: ')
for i in range(n):
    for j in range(n):
        print i, j

在這個片段中，循環(huán)是嵌套的。而且，第二個循環(huán)對第一個循環(huán)的每次迭代都要迭代n次。也就是說print語句總共要執(zhí)行n2次，所以代碼的時間復(fù)雜度為O(n2)。一般來說，對于嵌套循環(huán)，時間復(fù)雜度是每個循環(huán)迭代次數(shù)的乘積。

接著來關(guān)注下面這個例子：

n = input('enter n: ')
total = 0
for i in range(n):
    for j in range(10):
         print i, j
         total = total + 1

這個例子里也有兩個嵌套循環(huán)，你可能認為它的時間復(fù)雜度也是O(n2)。但要注意，無論n的值是多少，內(nèi)層循環(huán)總是迭代10次。我們?nèi)匀豢梢杂谩白屆總€循環(huán)迭代次數(shù)相乘”的這個規(guī)則，因此迭代次數(shù)是10n。所以這個代碼片段的時間復(fù)雜度是O(n)，在漸近分析中會忽略掉常數(shù)系數(shù)。

讓我們嘗試一個稍微麻煩一點的嵌套循環(huán)案例：

n = input('enter n: ')
for i in range(n):
    for j in range(i, n):
        print i, j

這段代碼里還是有兩個嵌套循環(huán)，但內(nèi)層循環(huán)在外層循環(huán)的每次迭代中，都循環(huán)不同的次數(shù)。在這種情況下，之前那個簡單的乘法規(guī)則就不起作用了，但好在這種分析并不太難。那么，我們想要知道當(dāng)輸入為n的時候，print語句一共執(zhí)行了多少次，應(yīng)該怎么做呢？第一次迭代外層循環(huán)的時候，內(nèi)層循環(huán)迭代了n次。第二次的時候，內(nèi)層循環(huán)迭代了n ? 1次，以此類推。直到最后，在外層循環(huán)的最后一次迭代中，內(nèi)層循環(huán)只迭代1次。那么內(nèi)層循環(huán)的迭代的總次數(shù)，只需要將它們?nèi)慷技悠饋砭湍艿贸觯矗?+2+…+n。

你應(yīng)該曾經(jīng)在數(shù)學(xué)課里見到過這個公式。當(dāng)然，如果沒有的話，下面是解決這個問題的一種方法。先把這個公式與自身相加，然后把它寫成下面這樣：

每一列的和都是n+1，一共有n列。所以，所有列的和就是。而這個和是原始公式的兩倍，因此除以2就能得出公式。展開公式，就會有二次多項式，所以我們可以得出結(jié)論，這段代碼片段的時間復(fù)雜度為O(2n)。

最后，這里有一個使用while循環(huán)的小例子：

n = input('enter n: ')
while n > 1:
    n = n // 2  # // is integer division

這段代碼片段與之前的所有其他代碼片段都不一樣——有一個不會迭代n次的循環(huán)。每次迭代的時候，n都會除以2。所以，我們應(yīng)該去確定n等于1所需要的循環(huán)次數(shù)。這和我們之前提到的“猜數(shù)字游戲”里的二分搜索是同一個問題。每次輸入的大小翻倍的時候，迭代次數(shù)加1。因此，輸入為n時，算法的步數(shù)是等式2x=n，其中x表示步數(shù)。所以，答案是x=log2n。在許多算法里，輸入都會被不斷地被分成兩半。在這種情況下，我們最終都可以得到O(log2n)這樣的時間復(fù)雜度。

讓我們回到搜索函數(shù)，你現(xiàn)在有了能夠正式分析代碼的所有工具。我們的線性搜索使用了一個會迭代n次的for循環(huán)，所以它的時間復(fù)雜度是O(n)。這也是它被稱為線性搜索的原因：函數(shù)的運行時間是一個線性函數(shù)（多項式最高次冪為1次）。而且就像前面提到過的，排序列表的二分搜索算法的時間復(fù)雜度是O(log2n)。因此循環(huán)（最多）迭代log2n次就能夠完成整個流程，而且每次循環(huán)體執(zhí)行的操作數(shù)都是常量。

時間復(fù)雜度能夠告訴我們，在面對大數(shù)據(jù)集的時候，我們的算法效率如何。對于僅僅會執(zhí)行一兩次的代碼，效率通常不是一個重要的問題。然而，當(dāng)你的程序需要兩年的時間來解決一個問題的時候，效率就成了一個大問題。大O符號可以讓我們推斷并確定程序在更大的數(shù)據(jù)集上需要運行多長時間。如果我們想要知道這個程序在兩倍大的輸入集的情況下需要執(zhí)行多長的時間，只需要在函數(shù)中插入2n來代替n。比如說，一個算法的分析結(jié)果是O(n2)，然后我們讓輸入集翻倍，我們可以預(yù)期它需要4倍的時間來執(zhí)行，因為(2n)2就是4n2。換句話說，如果我們的算法在大小為100萬的輸入集上需要執(zhí)行1min，那么我們完全可以預(yù)期它會在200萬的輸入集上花4min。

1.3.5 大O符號與Θ 符號

從理論上來說，大O符號只給出了算法效率的上限。回顧一下大O符號的定義。如果算法的時間復(fù)雜度是O(n)，那么它的復(fù)雜度也同樣可以表示為O(n2)、O(n3)等。通常來說，絕大多數(shù)算法的時間復(fù)雜度都是O(2n)，但是當(dāng)我們想要比較兩個特定算法的時候，這樣說沒有任何意義。而且，當(dāng)我們對算法進行大O分析時，我們總會試圖去找到一個更“嚴格”的上界。比如我們都知道的，當(dāng)列表的大小翻倍時，線性搜索要發(fā)現(xiàn)一個數(shù)字不在列表之中，需要花費兩倍的時間。然而，這里提到的線性搜索的漸近增長率是n，但是如果可以知道確切的增長率，顯然將會為我們提供更多的信息。

這里，我們引入Θ（Theta符號）來描述更嚴格的上（下）限。要證明算法的時間復(fù)雜度是，必須證明有常數(shù)、和，使得算法對于所有，執(zhí)行步數(shù)都會大于且小于。通過將算法的時間復(fù)雜度限制在f (n)的兩個倍數(shù)之間，我們可以明確執(zhí)行步數(shù)將和f (n)以相同速率增長，因此算法的執(zhí)行步數(shù)（對于較大的n）基本上等于f (n)的某個倍數(shù)的值。實際上，我們一般不會去找這個常量的確切的值，除非分析的算法特別復(fù)雜。有關(guān)函數(shù)邊界的示例，如圖1.3所示。

圖1.3 0.5x2介于0.25x2和0.75x2之間

在算法分析中，常見的一些函數(shù)的增長率如表1.2所示。從這個表格里我們可以看出，算法的復(fù)雜度函數(shù)對于它能不能在合理的時間內(nèi)解決問題非常重要。指數(shù)級（如2n）增長的算法，并不能用于解決哪怕只是普通大小的問題。如果計算機每秒可以執(zhí)行10億次操作，那么當(dāng)輸入的大小是100的時候，完成一個指數(shù)算法需要多長時間？利用表1.2所示的信息，我們可以知道2100大約是1030（也就是1后面跟上30個零）。這是一個非常大的數(shù)字。將它除以每秒10億次操作可以得出結(jié)論，在輸入大小為100的時候，運行這個算法需要1021秒，也就是超過1013年。而宇宙通常被認為是在100億～200億年前誕生的，所以這是一個比宇宙生命還要大上千倍的時間！

表1.2 常見函數(shù)的近似增長率

當(dāng)我們已經(jīng)知道解決特定大小的問題需要多長時間的時候，就可以使用Θ 符號來估計解決與之相比更大尺寸的問題所需要的時間。比如說，有一個的排序算法需要25秒才能對計算機上的100萬個元素進行排序，由此就可以估計出在同樣的計算機上使用相同的代碼對200萬個元素排序需要多長時間。從上面的信息中可以得出方程s。有一點需要注意，Θ 符號（和大O符號一樣）不會表示出最大項前面的常數(shù)乘數(shù)。但是，在列出等式的時候，需要包含這個常數(shù)乘數(shù)，這樣可以求解c：。現(xiàn)在，我們就可以計算，也就是100s。

可能你已經(jīng)發(fā)現(xiàn)，在這個情況下我們甚至都不需要去求解c。因為我們已經(jīng)知道算法的時間復(fù)雜度是，而現(xiàn)在我們想知道當(dāng)輸入大小翻倍時會發(fā)生什么。我們可以把2n帶入n并展開，得到：。也就是，在使用算法時，需要用4倍的時間來解決兩倍的問題。這和我們之前的答案一樣（）。

很明顯，我們將盡可能地使用Θ 符號來表明算法的性能。對于一些復(fù)雜的算法，很難去證明一個嚴格的邊界，在這種情況下我們可能只會去證明一個非嚴格的上界（大O符號）。通常來說，我們也只會分析算法的最壞情況下的時間復(fù)雜度。可能你會覺得平均情況下的時間復(fù)雜度更有用，但這個值一般并不太好得到。對于線性搜索，我們可以知道最好的情況是Θ (1)，最壞的情況是Θ (n)，因此很容易得出平均情況也是Θ (n)。因為，當(dāng)我們在一個不重復(fù)的列表中搜索每一個元素的時候，這個元素可能會在第一、第二、第三……一直到最后一個位置上被找到。所以，尋找的元素的總數(shù)是n(n+1)/2，對于平均情況來說，只需要除以搜索的次數(shù)n就好了，也就是Θ (n)。而對于二分搜索，確定平均情況的時間復(fù)雜度將會更加困難。