python數(shù)據(jù)結(jié)構(gòu)算法分析

更新時間：2022年01月25日 10:17:15 作者：柳小蔥

這篇文章主要介紹了python數(shù)據(jù)結(jié)構(gòu)算法分析,在python的數(shù)據(jù)結(jié)構(gòu)的章節(jié)中，我們上次學習到了python面向?qū)ο蟮乃枷?，即我們想用程序來實現(xiàn)一個東西，我們需是用對象的特征來描述我們想構(gòu)建的對象。感興趣的小伙伴可以查看下面內(nèi)容</P><P>

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

1.算法分析的定義

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

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

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

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

第一種方法：循環(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)方案看上去工作量更大，因為有些步驟重復。這好像是耗時更久的原因。而且，循環(huán)方案的耗時會隨著 n 一起增長。然而，這里有個問題。如果在另一臺計算機上運行這個函數(shù)，或用另一種編程語言來實現(xiàn)，很可能會得到不同的結(jié)果。如果計算機再舊些，sumOfN3 的執(zhí)行時間甚至更長。
我們需要更好的方式來描述算法的執(zhí)行時間?；鶞蕼y試計算的是執(zhí)行算法的實際時間。這不是一個有用的指標，因為它依賴于特定的計算機、程序、時間、編譯器與編程語言。我們希望找到一個獨立于程序或計算機的指標。這樣的指標在評價算法方面會更有用，可以用來比較不同實現(xiàn)下的算法。

2. 大O記法

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

例：計算如下程序的步驟數(shù)，和數(shù)量級大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記法

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

3.1 清點法

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

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

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

因此，該方法的時間復雜度是

3.2 排序法

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

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

乍看之下，你可能會認為這個算法的時間復雜度是O ( n ) O(n)O(n)，因為在排序之后只需要遍歷一次就可以比較 n 個字符。但是，調(diào)用兩次 sort 方法不是沒有代價。我們在后面會看到，排序的時間復雜度基本上是O ( n 2 ) O(n2 )O(n2)或 O ( n l o g n ) O(nlogn)O(nlogn) ，所以排序操作起主導作用。也就是說，該算法和排序過程的數(shù)量級相同。

3.3 蠻力法

用蠻力解決問題的方法基本上就是窮盡所有的可能。就異序詞檢測問題而言，可以用 s1 中的字符生成所有可能的字符串，看看 s2 是否在其中。但這個方法有個難處。用 s1 中的字符生成所有可能的字符串時，第 1 個字符有 n 種可能，第 2 個字符有 n-1 種可能，第 3 個字符有 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!也許有些字符串會重復，但程序無法預見，所以肯定會生成n ! n!n!個字符串。
當 n 較大時， n! 增長得比2n還要快。實際上，如果 s1 有20個字符，那么字符串的個數(shù)就是 20!= 2432902008176640000 。假設(shè)每秒處理一個，處理完整個列表要花 77146816596 年。這可不是個好方案。

3.4 計數(shù)法

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

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

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