Python 數據結構 2.時間復雜度和空間復雜度

Life is a journey

???????????????????? ? ? ?—— 25.2.28

一、引例：窮舉法

1.單層循環

所謂窮舉法，就是我們通常所說的枚舉，就是把所有情況都遍歷了的意思。

例：給定n（n ≤ 1000）個元素ai，求其中奇數有多少個

判斷一個數是偶數還是奇數，只需要求它除上2的余數是0還是1，那么我們把所有數都判斷一遍，并且對符合條件的情況進行計數，最后返回這個計數器就是答案，這里需要遍歷所有的數，這就是窮舉

def JudgeNum(self, n: int, a: List[int]) -> int:count = 0for i in range(n):if a[i] % 2 == 1:count += 1return count

時間復雜度 O(n)

2.雙層循環

例2：給定n（n ≤ 1000）個元素ai，求有多少個二元組（i，j），滿足ai + aj是奇數（i < j）。

def JudgeNum(self, n: int, a[]: List[int]) -> int: count = 0for i in range(n):for j in range(i + 1, n):if (a[i} + a[j]) % 2 == 1:count += 1return count

時間復雜度 O(n^2)

3.三層循環

例3：給定n（n ≤ 1000）個元素ai，求有多少個三元組（i，j，k），滿足ai + aj + ak是奇數（i < j < k）。

def JudgeNum(self, n: int, a: list[int]) -> int:count = 0for i in range(n):for j in range(i + 1, n):for k in range(j + 1, n):if (a[i] + a[j] + a[k]) % 2 == 1:count += 1return count

時間復雜度 O(n^3)

隨著循環嵌套的越多，時間消耗會越來越多，并且三個循環是乘法的關系，也就是遍歷次數隨著n的增加，呈現立方式的增長

4.遞歸枚舉

例：給定n(n ≤ 1000)個元素ai 和一個整數 k(k ≤ n)，求有多少個有序k數組，滿足他們的和是偶數

我們需要根據k的不同，決定寫幾層循環，k的最大值為1000，也就意味著我們要寫1000個if-else語句，顯然，這樣是無法接受的，比較暴力的做法是采用遞歸

二、時間復雜度

1.時間復雜度的表示法

在進行算法分析時，語句總的執行次數 T(n) 是關于問題規模 n 的函數，進而分析 T(n) 隨著 n 的變化情況而確定 T(n) 的數量級

算法的時間復雜度，就是算法的時間度量，記作：T(n)=O(f(n)) 用大寫的 O 來體現算法時間復雜度的記法，我們稱之為：大 O 記法

Ⅰ、時間函數

時間復雜度往往會聯系到一個函數，自變量：表示規模，應變量：表示執行時間。

這里所說的執行時間，是指廣義的時間，也就是單位并不是"秒"、"毫秒"這些時間單位，它代表的是一個"執行次數"的概念。我們用? f(n) 來表示這個時間函數。

Ⅱ、經典函數舉例

在例1中，我們接觸到了單層循環，這里的 n 是一個變量，隨著 n 的增大，執行次數增大，執行時間就會增加，所以就有了時間函數的表示法如下：f(n) = n

這就是經典的線性時間函數

在例2中，我們接觸到了雙層循環，它的時間函數表示法如下：f(n) = n * (n - 1) / 2

這是一個平方級別的時間函數

在例3中，我們接觸到了三層循環，它的時間函數表示法如下：f(n) = n * (n - 1) * (n - 2) / 6

這是一個立方級別的時間函數

2.時間復雜度

一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

并且我們有一個更加優雅的表示法，即：T(n)=O(f(n))，其中 O?念成大O

1) 當 f(n) = n，我們稱這個算法擁有線性時間復雜度，記作 O(n);

2) 當 f(n) = n * (n-1) / 2，我們稱這個算法擁有平方級時間復雜度，記作 O(n^2);

3) 當 f(n) = n * (n-1) * (n-2) / 6,我們稱這個算法擁有立方級的時間復雜度，記作 O(n^3);

這時候我們發現，f 的函數可能很復雜，但是 O?表示的函數往往比較簡單，它舍棄了一些"細節“

3.高階無窮小

如果 lim(β / α) = 0，則稱 ”β 是比 α較高階的無窮小“

例：f(n) = n * (n - 1) / 2

共兩部分組成，一部分是 n ^ 2 的部分，另一部分是 n 的部分，顯而易見，一定是 n ^ 2，相對于 n ^ 2 來說，n 可以忽略不計

隨著 n 的增長，線性的部分增長已經跟不上平方部分，這樣，線性部分的時間消耗相對于平方部分來說已經”微不足道“，所以我們直接忽略，于是就有時間復雜度表示如下：

T(n) = O(f(n))

? ? ? ? = O(1/2 * n ^ 2 - 1 / 2 * n)

? ? ? ? = O(1/2 * n ^ 2)

? ? ? ? = O(n ^ 2)

所以，它的時間復雜度就是O(n ^ 2)了

4.簡化系數

發現上述的公式推到的過程中，將 n ^ 2 前面的系數 1/2 去掉了，這是由于時間復雜度描述的更多的是一個數量級，所以盡量減少干擾項，對于兩個不同的問題，可能執行時間不同，但是我們可以說他們的時間復雜度是一樣的

三、常見的時間復雜度

1.常數階

max = 1024
def getMax() -> int:return max

沒有循環，是常數時間，表示為O(1)

2.對數階

例4：給定n(n ≤ 10000)個元素的有序數組 ai 和整數 v，求 v 在數組中的下標，不存在則輸出 -1

這個問題是一個常見的查詢問題，我們可以用O(n)的算法遍歷整個數組，然后去找 v 的值

當然，也有更快的方法，注意到題目中的條件，數組 ai 是有序的，所以我們可以利用二分查找來實現

def bin(n: int, a: List[int], v:int) -> int:left = 0,right = n - 1mid = 0while left <= right:mid = (left + right) // 2if a[mid] < v:left = v + 1elif a[mid] > v:right = v - 1else:return midreturn -1

這是一個二分查找的實現，時間復雜度為O(logn)

每次相當于把n切半，即：

n -> n / 2 -> n / 4 -> … -> n / 2 ^ k -> … -> 0

f(n) = O(n) = O(k) = O(logn)

3.根號階

例5：給定一個數 n(n ≤ 10 ^ 9)，問 n 是否是一個素數（素數的概念：除了1和它本身，沒有其他因子）

基于素數的概念，我們可以枚舉所有 i 屬于[2, n)，看能否整除 n，一旦能整除，代表找到了一個銀子，則不是素數，當所有數枚舉完還沒找到，他就是素數

但是這樣做，顯然效率太低，我們進行一些思考，得到如下算法：

import mathdef isPrime(n: int) -> bool:if n <= 1:return Falsesqrtn = math.sqrt(n)for i in range(2, sqrtn + 1):if n % i == 0:return Falsereturn True

這個算法的時間復雜度為：O(根號n)

為什么只需要枚舉 根號n 以內的數呢？

因為一旦有一個因子 s，必然有另一個因子 n / s，它們之間必然有一個大小關系，無論是 s ≤ n / s，還是 n / s ≤ s，都能通過兩邊乘上 s 得出：

比根號n小的數中，如果沒有這樣一個因子，則比根號n大的數中也不會存在這樣一個因子

4.線性階

例1中，我們接觸到了單層循環，這里的 n 是一個變量，隨著 n 的增大，執行次數增大，執行時間就會增加，所以就有了時間函數的表示法如下：f(n) = n

5.線性對數階

例6：給定n(n ≤ 100000)個元素 ai，求滿足 ai + aj = 1024 的有序二元組(i, j)有多少對

我們可以先對所有元素 ai 按照遞增排序，然后枚舉 ai，并且在[i + 1, n)范圍內查找是否存在 ai + aj = 1024

def Find(n: int, a: List[int]) -> int:count = 0sort(a)for i in range(n):j = 1024 - a[i]left, right = i + 1, n - 1while left <= right:mid = left + (right - left) // 2if a[mid] == target:count += 1breakelif a[mid] < taegrt:left = mid + 1else:right = mid - 1return count

?f(n) = O(n * logn) = O(nlogn)

6.多項式階

多項式的含義是函數 f(n) 可以表示成如下形式：

所以 O(n^5)、O(n^4)、O(n^3)、O(n^2)、O(n)都是多項式時間

7.指數階?

例7：給出n(n ≤ 15)個點，以及每兩個點之間的關系（連通還是不連通），求一個最大的集合，使得在這個集合中都連通

這是求子集的問題，由于最多只有 15 個點，我們就可以枚舉每個點選或者不選，總共 2^n 種情況，然后再判斷是否滿足題目中的連通性，這個算法時間復雜度為 O(n ^ 2 * 2 ^ n)；

8.階乘階

例8：給定n(n ≤ 12)個點，并且給出任意兩點間的距離，求從 s 點開始經過所有點回到 s 點的距離的最小值

這個問題就是典型的暴力枚舉所有情況求解，可以把這些點當成是一個排列，所以排列方案數為： n！

四、如何判斷時間復雜度

1.標準

首先，我們需要一個標準，也就是總的執行次數多少合適

我們把其定義為 S = 10 ^ 6

2.問題規模

有了標準以后，我們還需要知道問題規模，也就是O(n)中的n

3.套公式

然后就是憑感覺套公式了

????????當 n < 12 時，可能是需要用到階乘級別的算法，即 O(n!)

????????當 n < 16 時，可能是需要狀態壓縮的算法，比如 O(n?^ 2)、O(n * 2 ^ n)、O(n ^ 2 * 2 ^ n)

????????當 n < 30 時，可能是需要 O(n ^ 4)的算法，因為 30 ^ 4 差不多接近 10 ^ 6

????????當 n < 100 時，可能是需要 O(n)的算法，因為 1003= 106

????????當n < 1000 時，可能是需要 O(n ^ 2)的算法，因為 1000 ^?2 = 10 ^ 6

????????當n < 100000 時，可能是需要 O(n * log2n)、O(n * (log2n) ^ 2)的算法

????????當n < 1000000 時，可能是需要 O(根號n)、O(n)的算法

五、空間復雜度

????????空間復雜度是指算法在執行過程中所需的額外存儲空間。這包括算法在運行時使用的變量、數組、鏈表等數據結構所占用的內存空間。它和算法的時間復雜度一起，是衡量算法性能的重要指標之一。

????????在算法設計中，我們通常希望盡可能地降低空間復雜度，以減少內存的使用，提高算法的效率。然而，在某些情況下，為了實現算法的功能，可能需要使用更多的存儲空間。

六、常見數據結構的空間復雜度

1.順序表：O(n)，其中 n 是順序表的長度

2.鏈表：O(n)，其中 n 是鏈表的長度

3.棧：O(n)，其中 n 是棧的最大深度

4.隊列：其中 n 是隊列的最大長度

5.哈希表：O(n)，其中 n 是哈希表中元素的數量

6.樹：O(n)，其中 n 是樹的節點數量

7.圖：O(n + m)，其中 n 是圖中頂點的數量，m 是圖中邊的數量

七、空間換時間

通常使用額外空間的目的，就是為了換取時間上的效率，也就是我們常說的空間換時間。

最經典的空間換時間就是動態規劃，例如求一個斐波那契數列的第 n 項的值，如果不做任何優化就是利用循環進行計算，時間復雜度 (n)，但是如果引入了數組，將計算結果預先存儲在數組中，那么每次詢問只需要 O(1) 的時間復雜度就可以得到第 n 項的值，而這時，由于引入了數組所以空間復雜度就變成了 O(n)。