復(fù)雜度是評估算法效率的重要指標(biāo)之一。在Python中，我們需要了解算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是指算法運(yùn)行時(shí)間與輸入規(guī)模的關(guān)系。通常使用大O符號表示。例如，若算法的時(shí)間復(fù)雜度為O(n)，則隨著輸入規(guī)模n的增大，算法的執(zhí)行時(shí)間會線性增加。

空間復(fù)雜度

空間復(fù)雜度是指算法執(zhí)行過程中所需要的存儲空間和輸入數(shù)據(jù)規(guī)模的關(guān)系。通常使用大O符號表示。例如，若算法的空間復(fù)雜度為O(1)，則無論輸入規(guī)模大小，所需要的存儲空間是恒定的。

時(shí)間復(fù)雜度示例代碼

def foo(a):
n = len(a)
for i in range(n):   # O(n)
for j in range(i+1, n):  # O(n^2)
if a[i] >a[j]:
a[i], a[j] = a[j], a[i]
return a
# O(n^2)

上述代碼的時(shí)間復(fù)雜度為O(n^2)，因?yàn)槭褂昧藘蓪友h(huán)，而每層循環(huán)的次數(shù)都與n相關(guān)。

空間復(fù)雜度示例代碼

def bar(n):
s = [0] * n   # O(n)
return s
# O(n)

上述代碼的空間復(fù)雜度為O(n)，因?yàn)閯?chuàng)建了一個(gè)長度為n的列表。