由于最近開始準備藍橋杯(python組)，開始對編程基礎(chǔ)進行一些復(fù)習(xí)，當我發(fā)現(xiàn)藍橋?qū)Υ蠖鄶?shù)題目程序運行時間及大小有要求時，我知道我不得不考慮性能問題，而不是能跑就行🤓

寫下這篇文章希望對其他同志有幫助吧

什么是算法的時間復(fù)雜度和空間復(fù)雜度

算法（Algorithm）是指用來操作數(shù)據(jù)、解決程序問題的一組方法。衡量不同算法的優(yōu)劣，主要還是根據(jù)算法所占的空間和時間兩個維度去考慮。一個問題總有無數(shù)種解決辦法，對于同一個問題，我們可以使用不同的方法去解決，但使用不同算法所耗費的資源和時間不同。

世界上沒有完全完美的東西，也沒有最合適你的女孩，不存在既不消耗最多的時間，也不占用最多的空間的完美無瑕的程序，魚和熊掌不可得兼，那么就需要我們從中去尋找一個平衡點，寫出能出色解決問題的較為完美的代碼。

時間維度

時間維度指執(zhí)行當前算法所消耗的時間，通常用時間復(fù)雜度來描述，算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。度量一個程序的執(zhí)行時間通常有兩種方法：

事后統(tǒng)計法

該方法有兩個缺陷：一是要想對設(shè)計的算法的運行性能進行評測，必須先依據(jù)算法編制相應(yīng)的程序并實際運行；二是所得時間的統(tǒng)計量依賴于計算機的硬件、軟件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)勢。

事前分析法

程序運行前，對算法進行估算。程序運行時所消耗的時間取決于：算法采用的策略、方法；編譯產(chǎn)生的代碼質(zhì)量；問題的輸入規(guī)模；計算機硬件執(zhí)行的速度。

時間頻度

程序執(zhí)行所耗費的時間，從理論上是不能算出來的，必須實際運行測試才能知道。

一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度T(n)，它只是一個估計值，一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。

時間復(fù)雜度

在計算機科學(xué)中，時間復(fù)雜度是一個描述算法運行時間如何隨著輸入數(shù)據(jù)規(guī)模變化的度量。它是對算法運行時間增長趨勢的一種抽象表示。

在時間頻度中，n稱為問題的規(guī)模，當n不斷變化時，時間頻度T(n)也會不斷變化。如果想知道它變化時呈現(xiàn)什么規(guī)律時，需要引入時間復(fù)雜度概念。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。

常見時間復(fù)雜度量級

O(1) - 常數(shù)時間復(fù)雜度

這種復(fù)雜度表示算法的運行時間不隨輸入數(shù)據(jù)的大小而改變。

def constant_time_function(x): ?return x * 2 ?# 這是一個常數(shù)時間操作 ?# 無論x的值是多少，這個函數(shù)都只需要一個固定的時間來完成

O(n) - 線性時間復(fù)雜度

這種復(fù)雜度表示算法的運行時間與輸入數(shù)據(jù)的大小成正比。

def linear_time_function(arr): ?total = 0 ?for num in arr: ?# 遍歷數(shù)組中的每個元素 ?total += num ?# 這是一個常數(shù)時間操作 ?return total ?# 如果arr的長度為n，則這個函數(shù)需要n個時間單位來完成

O(n^2) - 二次時間復(fù)雜度

這種復(fù)雜度表示算法的運行時間與輸入數(shù)據(jù)大小的平方成正比。

def linear_time_function(arr): ?total = 0 ?for num in arr: ?# 遍歷數(shù)組中的每個元素 ?total += num ?# 這是一個常數(shù)時間操作 ?return total ?# 如果arr的長度為n，則這個函數(shù)需要n個時間單位來完成

O(log n) - 對數(shù)時間復(fù)雜度

這種復(fù)雜度通常出現(xiàn)在基于分治的算法中，如二分查找。

def linear_time_function(arr): ?total = 0 ?for num in arr: ?# 遍歷數(shù)組中的每個元素 ?total += num ?# 這是一個常數(shù)時間操作 ?return total ?# 如果arr的長度為n，則這個函數(shù)需要n個時間單位來完成

O(n log n) - 線性對數(shù)時間復(fù)雜度

這種復(fù)雜度通常出現(xiàn)在排序算法中，如歸并排序和快速排序（在平均情況下）。

 # 這個過程的時間復(fù)雜度為O(n log n)。快速排序也類似，通過選擇一個基準元素并將數(shù)組分成兩部分， 
# 然后遞歸地對兩部分進行排序，其平均時間復(fù)雜度也是O(n log n)。
def merge_sort(lst):if len(lst) <= 1:return lst
?mid = len(lst) // 2left_half = merge_sort(lst[:mid])right_half = merge_sort(lst[mid:])
?return merge(left_half, right_half)
?
def merge(left, right):merged = []left_index = 0right_index = 0
?while left_index < len(left) and right_index < len(right):if left[left_index] < right[right_index]:merged.append(left[left_index])left_index += 1else:merged.append(right[right_index])right_index += 1
?merged += left[left_index:]merged += right[right_index:]
?return merged
?
lst = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(lst)) ?# 輸出：[3, 9, 10, 27, 38, 43, 82]

O(2^n) - 指數(shù)時間復(fù)雜度

這種復(fù)雜度表示算法的運行時間隨輸入數(shù)據(jù)的大小呈指數(shù)級增長，通常出現(xiàn)在遞歸算法中，且沒有適當?shù)募糁蛴洃浕?/p>

def exponential_time_function(n): ?if n == 0: ?return 1 ?else: ?return 2 * exponential_time_function(n - 1) ?# 每次遞歸調(diào)用都會使問題規(guī)模減半，但總時間呈指數(shù)增長 ?# 對于一個輸入n，這個函數(shù)的時間復(fù)雜度為O(2^n)

空間復(fù)雜度

空間復(fù)雜度是對在運行過程中臨時占用存儲空間大小的一個量度，同樣反映的是一個趨勢

關(guān)于空間復(fù)雜度 S(n) 的討論，一個算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，空間復(fù)雜度并不是程序占用了多少bytes的空間，因為這個也沒有太大意義，空間復(fù)雜度算的是變量的個數(shù)?？臻g復(fù)雜度計算規(guī)則基本跟時間復(fù)雜度類似，也使用大O漸進表示法。它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度。

常見空間復(fù)雜度

常數(shù)空間 O(1)*O*(1)：

空間需求是固定的，不隨輸入規(guī)模變化。例如，交換兩個數(shù)的值：

def swap(a, b):temp = aa = bb = tempreturn a, b
?
print(swap(1, 2)) ?# 輸出：(2, 1)

線性空間 O(n)*O*(*n*)：

空間需求與輸入規(guī)模線性相關(guān)。例如，創(chuàng)建一個與輸入規(guī)模大小相同的新列表：

def swap(a, b):temp = aa = bb = tempreturn a, b
?
print(swap(1, 2)) ?# 輸出：(2, 1)

二次空間 O(n2)*O*(*n*2)：

空間需求與輸入規(guī)模的平方成正比。例如，創(chuàng)建一個 n×nn×n 的二維數(shù)組：

def swap(a, b):temp = aa = bb = tempreturn a, b
?
print(swap(1, 2)) ?# 輸出：(2, 1)

時間復(fù)雜度和空間復(fù)雜度的計算

時間復(fù)雜度計算

時間復(fù)雜度是衡量算法執(zhí)行時間隨輸入數(shù)據(jù)規(guī)模增長而變化的快慢程度的指標。它通常表示為輸入數(shù)據(jù)規(guī)模n的函數(shù)，即T(n)。算法的時間復(fù)雜度越低，表示它在處理大規(guī)模數(shù)據(jù)時所需的執(zhí)行時間越短，效率越高。

識別基本操作：

• 基本操作是算法中執(zhí)行次數(shù)最多的操作，它通常是算法的核心部分，決定了算法的整體性能。

• 在分析時，需要關(guān)注循環(huán)、遞歸等可能導(dǎo)致操作次數(shù)大量增加的部分。

計算執(zhí)行次數(shù)：

• 對于單層循環(huán)，執(zhí)行次數(shù)通常是輸入數(shù)據(jù)規(guī)模n的線性函數(shù)，即O(n)。

• 對于嵌套循環(huán)，需要分別計算每一層循環(huán)的迭代次數(shù)，并將它們相乘得到總執(zhí)行次數(shù)。例如，兩層嵌套循環(huán)的執(zhí)行次數(shù)通常為O(n^2)。

• 對于遞歸算法，需要分析遞歸調(diào)用的次數(shù)和遞歸深度，以及每次遞歸調(diào)用中的操作次數(shù)。

應(yīng)用大O表示法：

• 大O表示法用于簡化執(zhí)行次數(shù)的表達式，只保留最高階項，并忽略系數(shù)和常數(shù)項。這是因為當n足夠大時，高階項的增長速度將遠遠超過低階項和常數(shù)項。

• 例如，如果執(zhí)行次數(shù)為3n2)。

考慮最壞情況：

• 在分析時間復(fù)雜度時，通?？紤]最壞情況，即輸入數(shù)據(jù)使得算法執(zhí)行時間最長的情況。這是因為最壞情況給出了算法性能的上界，有助于評估算法在最不利條件下的表現(xiàn)。

示例分析：

• 線性搜索：在最壞情況下，需要遍歷整個數(shù)組才能找到目標元素，因此時間復(fù)雜度為O(n)。

• 二分搜索：在有序數(shù)組中查找元素時，每次將搜索范圍減半，因此時間復(fù)雜度為O(log n)。

• 冒泡排序：通過相鄰元素的比較和交換進行排序，每趟排序都會將最大的元素移動到數(shù)組的末尾。在最壞情況下，需要進行n-1趟排序，每趟排序的比較次數(shù)為n-i（i為當前趟數(shù)），因此總時間復(fù)雜度為O(n^2)。

• 歸并排序：將數(shù)組分成兩半分別排序，然后合并結(jié)果。每次合并的復(fù)雜度為O(n)，遞歸深度為log n，因此總時間復(fù)雜度為O(n log n)。

空間復(fù)雜度的計算

分析存儲需求：

• 包括算法中定義的局部變量、數(shù)組、鏈表、棧、隊列等數(shù)據(jù)結(jié)構(gòu)所占用的空間。

• 注意區(qū)分輸入數(shù)據(jù)所占用的空間和算法執(zhí)行過程中產(chǎn)生的臨時空間。輸入數(shù)據(jù)所占用的空間通常不計入空間復(fù)雜度。

計算空間總量：

• 根據(jù)算法的執(zhí)行過程，計算所需存儲空間的總量。這包括所有局部變量和臨時數(shù)據(jù)結(jié)構(gòu)所占用的空間。

• 如果空間使用量與輸入數(shù)據(jù)規(guī)模成正比，則空間復(fù)雜度為O(n)等。

應(yīng)用大O表示法：

• 與時間復(fù)雜度類似，使用大O表示法來簡化空間總量的表達式。只保留最高階項，并忽略系數(shù)和常數(shù)項。

考慮遞歸?？臻g：

• 對于遞歸算法，需要考慮遞歸棧的深度。遞歸棧空間用于存儲遞歸調(diào)用過程中的局部變量和返回地址等信息。

• 如果遞歸深度與輸入數(shù)據(jù)規(guī)模成正比，則空間復(fù)雜度為O(n)。如果遞歸深度是固定的（如二分搜索），則空間復(fù)雜度為O(1)（不考慮系統(tǒng)?？臻g）。

示例分析：

• 常數(shù)空間：如果算法只使用固定數(shù)量的額外空間（如幾個變量），則空間復(fù)雜度為O(1)。

• 線性空間：如果算法使用與輸入數(shù)據(jù)規(guī)模成正比的額外空間（如一個長度為n的數(shù)組），則空間復(fù)雜度為O(n)。

• 遞歸空間：對于遞歸算法，如果遞歸深度與輸入數(shù)據(jù)規(guī)模成正比（如遞歸求解斐波那契數(shù)列），則空間復(fù)雜度為O(n)。如果遞歸深度是固定的（如二分搜索），則空間復(fù)雜度為O(1)（不考慮系統(tǒng)?？臻g）。但需要注意的是，在實際應(yīng)用中，系統(tǒng)?？臻g也是有限的，因此過深的遞歸可能會導(dǎo)致棧溢出錯誤。

寫在最后：

區(qū)分不同情況：時間復(fù)雜度和空間復(fù)雜度通?？紤]最壞情況，但也可以分析最好情況和平均情況。最好情況和平均情況可能給出更準確的算法性能評估，但在某些情況下（如在線算法或?qū)崟r系統(tǒng)），最壞情況可能更為重要。

考慮常數(shù)項和系數(shù)：雖然大O表示法忽略了常數(shù)項和系數(shù)，但在實際應(yīng)用中，它們可能對算法性能有顯著影響。特別是在處理小規(guī)模數(shù)據(jù)時，低階項和系數(shù)可能占據(jù)主導(dǎo)地位。因此，在評估算法性能時，需要綜合考慮時間復(fù)雜度和空間復(fù)雜度以及常數(shù)項和系數(shù)的影響。

綜合評估：在選擇算法時，除了時間復(fù)雜度和空間復(fù)雜度外，還需要考慮算法的穩(wěn)定性、可讀性、可維護性等因素。一個優(yōu)秀的算法應(yīng)該在這些方面都有良好的表現(xiàn)。