前文學(xué)習(xí)：

python數(shù)據(jù)類型: python數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)類型.
python的輸入輸出: python數(shù)據(jù)結(jié)構(gòu)輸入輸出及控制和異常.
python面向?qū)ο? python數(shù)據(jù)結(jié)構(gòu)面向?qū)ο?

今天我們來(lái)學(xué)習(xí)的內(nèi)容是面試題中都避免不小了的問題，就是算法分析了，什么是算法分析，算法分析是用來(lái)分析一個(gè)算法的好壞的，大家完成一件事情寫不一樣的算法，就需要算法分析來(lái)評(píng)判算法的好壞，最常見的就是程序的復(fù)雜的O(n)。

1.算法分析的定義

有這樣一個(gè)問題：當(dāng)兩個(gè)看上去不同的程序 解決同一個(gè)問題時(shí)，會(huì)有優(yōu)劣之分么？答案是肯定的。算法分析關(guān)心的是基于所使用的計(jì)算資源比較算法。我們說(shuō)甲算法比乙算法好，依據(jù)是甲算法有更高的資源利用率或使用更少的資源。從這個(gè)角度來(lái)看，上面兩個(gè)函數(shù)其實(shí)差不多，它們本質(zhì)上都利用同一個(gè)算法解決累加問題。

計(jì)算資源究竟指什么？思考這個(gè)問題很重要。有兩種思考方式。

• 一是考慮算法在解決問題時(shí) 要占用的空間或內(nèi)存。解決方案所需的空間總量一般由問題實(shí)例本身決定，但算法往往也會(huì)有特定的空間需求。
• 二是根據(jù)算法執(zhí)行所需的時(shí)間進(jìn)行分析和比較。這個(gè)指標(biāo)有時(shí)稱作算法的執(zhí)行 時(shí)間或運(yùn)行時(shí)間。要 衡 量 sumOfN 函數(shù)的執(zhí)行時(shí)間，一個(gè)方法就是做基準(zhǔn)分析。也就是說(shuō)，我們會(huì)記錄程序計(jì)算出結(jié)果所消耗的實(shí)際時(shí)間。在 Python 中，我們記錄下函數(shù)就所處系統(tǒng)而言的開始時(shí)間和結(jié)束時(shí)間。time 模塊中有一個(gè) time 函數(shù)，它會(huì)以秒為單位返回自指定時(shí)間點(diǎn)起到當(dāng)前的系統(tǒng)時(shí)鐘時(shí)間。在首尾各調(diào)用一次這個(gè)函數(shù)，計(jì)算差值，就可以得到以秒為單位的執(zhí)行時(shí)間。

舉個(gè)例子：我們需要求解前n個(gè)數(shù)之和，通過計(jì)算所需時(shí)間來(lái)評(píng)判效率好壞。(這里使用time函數(shù),并計(jì)算5次來(lái)看看大致需要多少時(shí)間)

第一種方法：循環(huán)方案

import time
def sumOfN2(n): 
        start=time.time()
        thesum=0
        for i in range(1,n+1):
            thesum=thesum+i
        end=time.time()
        return thesum,end-start
#循環(huán)5次        
for i in range(5):
     print("Sum is %d required %10.7f seconds" % sumOfN2(10000)) 

結(jié)果如下：

第二種方法：公式方法

#直接利用求和公式
def sumOfN3(n): 
        start=time.time()
        thesum=(1+n)*n/2
        end=time.time()
        return thesum,end-start
for i in range(5):
     print("Sum is %d required %10.7f seconds" % sumOfN3(10000)) 

結(jié)果如下：

直覺上，循環(huán)方案看上去工作量更大，因?yàn)橛行┎襟E重復(fù)。這好像是耗時(shí)更久的原因。而且，循環(huán)方案的耗時(shí)會(huì)隨著 n 一起增長(zhǎng)。然而，這里有個(gè)問題。如果在另一臺(tái)計(jì)算機(jī)上運(yùn)行這個(gè)函數(shù)，或用另一種編程語(yǔ)言來(lái)實(shí)現(xiàn)，很可能會(huì)得到不同的結(jié)果。如果計(jì)算機(jī)再舊些，sumOfN3 的執(zhí)行時(shí)間甚至更長(zhǎng)。
我們需要更好的方式來(lái)描述算法的執(zhí)行時(shí)間?；鶞?zhǔn)測(cè)試計(jì)算的是執(zhí)行算法的實(shí)際時(shí)間。 這不是一個(gè)有用的指標(biāo)，因?yàn)樗蕾囉谔囟ǖ挠?jì)算機(jī)、程序、時(shí)間、編譯器與編程語(yǔ)言。我們希 望找到一個(gè)獨(dú)立于程序或計(jì)算機(jī)的指標(biāo)。這樣的指標(biāo)在評(píng)價(jià)算法方面會(huì)更有用，可以用來(lái)比較不同實(shí)現(xiàn)下的算法。

2. 大O記法

這里為了讓大家知道一些函數(shù)的增長(zhǎng)速度，我決定將一些函數(shù)的列舉出來(lái)。

例：計(jì)算如下程序的步驟數(shù)，和數(shù)量級(jí)大O

a = 5
b = 6
c = 10
for i in range(n): 
    for j in range(n): 
        x = i * i 
        y = j * j 
        z = i * j 
for k in range(n): 
    w = a * k + 45  
    v = b * b
d = 33

這段程序的賦值次數(shù)為：

大家可以自己算一下。

3. 不同算法的大O記法

這里我們采用不同的算法實(shí)現(xiàn)一個(gè)經(jīng)典的異序詞檢測(cè)問，所謂異序詞，就是組成單詞的字母一樣，只是順序不同，例如heart和earth，python和typhon。為了簡(jiǎn)化問題，我們假設(shè)要檢驗(yàn)的兩個(gè)單詞字符串的長(zhǎng)度已經(jīng)一樣長(zhǎng)。

3.1 清點(diǎn)法

該方法主要是清點(diǎn)第 1 個(gè)字符串的每個(gè)字符，看看它們是否都出現(xiàn)在第 2 個(gè)字符串中。如果是，那么兩個(gè)字符串必然是異序詞。清點(diǎn)是通過用 Python 中的特殊值 None 取代字符來(lái)實(shí)現(xiàn)的。但是，因?yàn)?Python 中的字符串是不可修改的，所以先要將第 2 個(gè)字符串轉(zhuǎn)換成列表。在字符列表中檢查第 1 個(gè)字符串中的每個(gè)字符，如果找到了，就替換掉。

def anagramSolution1(s1, s2):
    alist = list(s2)
    pos1=0
    stillOK = True
    while pos1 < len(s1) and stillOK:
          pos2 = 0
          found = False
          while pos2 < len(alist) and not found:
                if s1[pos1] == alist[pos2]:
                   found = True
                else:
                   pos2 = pos2 + 1
          if found:
                alist[pos2] = None
          else:
                stillOK = False
          pos1 = pos1 + 1
    return stillOK

來(lái)分析這個(gè)算法。注意，對(duì)于 s1 中的 n 個(gè)字符，檢查每一個(gè)時(shí)都要遍歷 s2 中的 n 個(gè)字符。 要匹配 s1 中的一個(gè)字符，列表中的 n 個(gè)位置都要被訪問一次。因此，訪問次數(shù)就成了從 1 到 n 的整數(shù)之和。這可以用以下公式來(lái)表示。

因此，該方法的時(shí)間復(fù)雜度是

3.2 排序法

盡管 s1 與 s2 是不同的字符串，但只要由相同的字符構(gòu)成，它們就是異序詞?；谶@一點(diǎn)， 可以采用另一個(gè)方案。如果按照字母表順序給字符排序，異序詞得到的結(jié)果將是同一個(gè)字符串。

def anagramSolution2(s1, s2):
       alist1 = list(s1)
       alist2 = list(s2)
       alist1.sort()
       alist2.sort()
       pos=0
       matches = True
       while pos < len(s1) and matches:
             if alist1[pos] == alist2[pos]:
                pos = pos + 1
             else:
                matches = False
      return matches

乍看之下，你可能會(huì)認(rèn)為這個(gè)算法的時(shí)間復(fù)雜度是O ( n ) O(n)O(n)，因?yàn)樵谂判蛑笾恍枰闅v一次就可以比較 n 個(gè)字符。但是，調(diào)用兩次 sort 方法不是沒有代價(jià)。我們?cè)诤竺鏁?huì)看到，排序的時(shí) 間復(fù)雜度基本上是O ( n 2 ) O(n2 )O(n2)或 O ( n l o g n ) O(nlogn)O(nlogn) ，所以排序操作起主導(dǎo)作用。也就是說(shuō)，該算法和排序過程的數(shù)量級(jí)相同。

3.3 蠻力法

用蠻力解決問題的方法基本上就是窮盡所有的可能。就異序詞檢測(cè)問題而言，可以用 s1 中 的字符生成所有可能的字符串，看看 s2 是否在其中。但這個(gè)方法有個(gè)難處。用 s1 中的字符生 成所有可能的字符串時(shí)，第 1 個(gè)字符有 n 種可能，第 2 個(gè)字符有 n-1 種可能，第 3 個(gè)字符有 n-2 種可能，依此類推。字符串的總數(shù)是n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ . . . . . . ∗ 3 ∗ 2 ∗ 1 n*(n-1)*(n-2)*......*3*2*1n∗(n−1)∗(n−2)∗......∗3∗2∗1,即為n ! n!n!也許有些字符串會(huì)重復(fù)，但程序無(wú)法預(yù)見，所以肯定會(huì)生成n ! n!n!個(gè)字符串。
當(dāng) n 較大時(shí)， n! 增長(zhǎng)得比2n還要快。實(shí)際上，如果 s1 有20個(gè)字符，那么字符串的個(gè)數(shù)就 是 20!= 2432902008176640000 。假設(shè)每秒處理一個(gè)，處理完整個(gè)列表要花 77146816596 年。 這可不是個(gè)好方案。

3.4 計(jì)數(shù)法

最后一個(gè)方案基于這樣一個(gè)事實(shí):兩個(gè)異序詞有同樣數(shù)目的 a、同樣數(shù)目的 b、同樣數(shù)目的 c，等等。要判斷兩個(gè)字符串是否為異序詞，先數(shù)一下每個(gè)字符出現(xiàn)的次數(shù)。因?yàn)樽址赡苡?26 種，所以使用 26 個(gè)計(jì)數(shù)器，對(duì)應(yīng)每個(gè)字符。每遇到一個(gè)字符，就將對(duì)應(yīng)的計(jì)數(shù)器加 1。最后， 如果兩個(gè)計(jì)數(shù)器列表相同，那么兩個(gè)字符串肯定是異序詞。

def anagramSolution4(s1, s2):
       c1=[0]*26
       c2=[0]*26

       for i in range(len(s1)):
           pos = ord(s1[i]) - ord('a')
           c1[pos] = c1[pos] + 1

       for i in range(len(s2)):
          pos = ord(s2[i]) - ord('a')
          c2[pos] = c2[pos] + 1
       j=0
       stillOK = True
       while j < 26 and stillOK:
             if c1[j] == c2[j]:
                j=j+1
             else:
                stillOK = False
       return stillOK

這個(gè)方案也有循環(huán)。但不同于方案 1，這個(gè)方案的循環(huán)沒有嵌套。前兩個(gè)計(jì)數(shù)循環(huán)都是 n 階 的。第 3 個(gè)循環(huán)比較兩個(gè)列表，由于可能有 26 種字符，因此會(huì)循環(huán) 26 次。全部加起來(lái)，得到總步驟數(shù) T (n) =2n - 26 ，即 O(n) 。我們找到了解決異序詞檢測(cè)問題的線性階算法。

4. 列表和字典操作的復(fù)雜度

4.1 列表

4.2 字典

到此這篇關(guān)于python數(shù)據(jù)結(jié)構(gòu)算法分析的文章就介紹到這了,更多相關(guān)python 算法分析內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論