全面解讀其常見算法「常見算法的時間空間複雜度」

前言

一般來說，解決問題的方法不止一種。我們需要學習如何比較不同算法的性能，並選擇最佳算法來解決特定的問題。一個算法的好壞，我們可以從時間和空間兩個維度去衡量。並且，一般分為兩個階段，一是算法完成前的理論分析，二是算法完成後實際分析。

「理論分析」：這種算法的效率分析是通過假設所有其他因素，如處理器的速度等是恆定的，對算法的實現沒有影響。
「實際分析」：當算法實現後，我們需要考慮算法採用編程語言，然後在特定計算機上執行該算法，其消耗的時間與計算機的硬件水平相關。在此分析中，我們要收集實際的統計數據，如運行時間和所需空間。

本篇文章要討論的主要是算法的理論分析，從常見的時間、空間複雜度入手，介紹各種時間、空間複雜度的特點，並總結一些通用數據結構、排序算法、搜索算法相關操作的時間和空間複雜度。最後，針對遞歸操作，使用Master Theorem來分析其複雜度。

時間、空間複雜度簡介

時間複雜度

時間複雜度是指執行這個算法所需要的計算工作量，其複雜度反映了程序執行時間「隨輸入規模增長而增長的量級」，在很大程度上能很好地反映出算法的優劣與否。一個算法花費的時間與算法中語句的「執行次數成正比」，執行次數越多，花費的時間就越多。一個算法中的執行次數稱為語句頻度或時間頻度，記為T(n)，其中n稱為問題的規模，當n不斷變化時，它所呈現出來的規律，我們稱之為時間複雜度。比如：與，雖然算法的時間頻度不一樣，但他們的時間複雜度卻是一樣的，「時間複雜度只關注最高數量級，且與之係數也沒有關係」。通常一個算法由控制結構（順序，分支，循環三種）和原操作（固有數據類型的操作）構成，而算法時間取決於兩者的綜合效率。

空間複雜度

空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度，所謂的臨時佔用存儲空間指的就是代碼中「輔助變量所佔用的空間」，它包括為參數表中「形參變量」分配的存儲空間和為在函數體中定義的「局部變量」分配的存儲空間兩個部分。我們用 S(n)=O(f(n))來定義，其中n為問題的規模(或大小)。通常來說，只要算法不涉及到動態分配的空間，以及遞歸、棧所需的空間，空間複雜度通常為0(1)。一個一維數組a[n]，空間複雜度O(n)，二維數組為O(n^2)。

大O表示法

大O符號是由德國數論學家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數論》（Analytische Zahlentheorie）首先引入的。算法的複雜度通常用大O符號表述，定義為T(n) = O(f(n))。稱函數T(n)以f(n)為界或者稱T(n)受限於f(n)。如果一個問題的規模是n，解這一問題的某一算法所需要的時間為T(n)。T(n)稱為這一算法的「時間複雜度」。當輸入量n逐漸加大時，時間複雜度的極限情形稱為算法的「漸近時間複雜度」。空間複雜度同理。舉個例子，令，。

時間、空間複雜度計算方法

如圖展示了幾種常見的複雜度形式：非常糟糕的複雜度有O(n!)，O(2^n)，O(n^2)；比較糟糕的有O(nlog n)，可以接受的有O(n)，還不錯的有O(n)，非常好的有O(logn)和O(1)。

如何計算時間複雜度

如果算法執行所需要的臨時空間不隨着某個變量n的大小而變化，即此算法空間複雜度為一個常量，可表示為O(1)，如

a = 1
b = 2
c = a + b
b += a

「一個循環」，算法需要執行的運算次數用輸入大小n的函數表示，即 T(n) 。下面這個函數，語句頻度T(n) = 2 + 2*n + 1，那麼時間複雜度為O(2*n + 3) = O(n)，因為時間複雜度只關注最高數量級，且與之係數也沒有關係。

def fun(n):
    count1 = 0
    count2 = 0
    for i in range(n):
        count1 += 1
        count2 += 2
    return count

對於「多個循環」，假設循環體的時間複雜度為O(n)，各個循環的循環次數分別是a, b, c…，則這個循環的時間複雜度為 O(n×a×b×c…)。分析的時候應該由里向外分析這些循環。比如下面這個函數，複雜度為O(n*n*1) = O(n^2)

def fun(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count

對於「順序執行的語句」或者算法，總的時間複雜度等於其中最大的時間複雜度。比如下面這個函數，第1部分複雜度為O(n^2)，第2部分複雜度為O(n)，總複雜度為max(O(n^2), O(n)) = O(n^2)

def fun(n):
    # 第1部分複雜度為O(n^2)
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    # 第2部分複雜度為O(n)
    for i in range(n):
        count += 2
    return count

對於「條件判斷語句」，總的時間複雜度等於其中時間複雜度最大的路徑的時間複雜度。當n >= 0分支的複雜度最大，即總複雜度為O(n^2)

def fun(n):
    if n >= 0:
        # 第1部分複雜度為O(n^2)
        count = 0
        for i in range(n):
            for j in range(n):
                count += 1
    else:
        # 第2部分複雜度為O(n)
        for i in range(n):
            count += 2
    return count

「總結：時間複雜度分析的基本策略是：從內向外分析，從最深層開始分析。如果遇到函數調用，就要深入函數進行分析。」

如何計算空間複雜度

我們在寫代碼時，完全可以用空間來換取時間，比如字典樹，哈希等都是這個原理。算法在運行過程中臨時佔用的存儲空間隨算法的不同而異，有的算法只需要佔用少量的臨時工作單元，而且「不隨問題規模的大小而改變」，我們稱這種算法是「就地”進行的，是節省存儲的算法，空間複雜度為O(1)，注意這並不是說僅僅定義一個臨時變量；有的算法需要佔用的臨時工作單元數與解決問題的規模n有關，它隨着n的增大而增大，當n較大時，將佔用較多的存儲單元，例如將快速排序和歸併排序算法就屬於這種情況。

如果算法執行所需要的臨時空間不隨着某個變量n的大小而變化，即此算法空間複雜度為一個常量，可表示為 O(1)。如下代碼中的 i、j、t 所分配的空間都不隨着處理數據量變化，因此它的空間複雜度為O(1)。

i = 0
j = 1
t = i + j

這段代碼中，第一行定義了一個列表，這個列表的長度隨着n的規模不同，會不一樣，這裡空間複雜度為O(n)。

def fun(n):
    temp = []
    for i in range(n):
        temp.append(i)

對於一個算法，其時間複雜度和空間複雜度往往是相互影響的。當追求一個較好的時間複雜度時，可能會使空間複雜度的性能變差，即可能導致佔用較多的存儲空間；反之，追求一個較好的空間複雜度時，可能會使時間複雜度的性能變差，即可能導致佔用較長的運行時間。另外，算法的所有性能之間都存在着或多或少的相互影響。因此，當設計一個算法(特別是大型算法)時，要綜合考慮算法的各項性能，算法的使用頻率，算法處理的數據量的大小，算法描述語言的特性，算法運行的機器系統環境等各方面因素，才能夠設計出比較好的算法。