快捷導(dǎo)航

Python算法的時間復(fù)雜度和空間復(fù)雜度(實例解析)

更新時間：2019年11月19日 09:32:01 作者：Sch01aR#

算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度，簡單而講時間復(fù)雜度指的是語句執(zhí)行次數(shù)，空間復(fù)雜度指的是算法所占的存儲空間，本文通過代碼給大家介紹Python算法的時間復(fù)雜度和空間復(fù)雜度問題，感興趣的朋友一起看看吧

算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度。

其作用：

時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量；
而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。
（算法的復(fù)雜性體現(xiàn)在運行該算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間（即寄存器）資源，因此復(fù)雜度分為時間和空間復(fù)雜度）。

簡單來說，時間復(fù)雜度指的是語句執(zhí)行次數(shù)，空間復(fù)雜度指的是算法所占的存儲空間

計算時間復(fù)雜度的方法：

用常數(shù)1代替運行時間中的所有加法常數(shù)
修改后的運行次數(shù)函數(shù)中，只保留最高階項
去除最高階項的系數(shù)

時間復(fù)雜度

算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運行時間，時間復(fù)雜度常用“O”表述，使用這種方式時，時間復(fù)雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況

時間復(fù)雜度是用來估計算法運行時間的一個式子（單位），一般來說，時間復(fù)雜度高的算法比復(fù)雜度低的算法慢

print('Hello world') # O(1)
# O(1)
print('Hello World')
print('Hello Python')
print('Hello Algorithm')
for i in range(n): # O(n)
 print('Hello world')
for i in range(n): # O(n^2)
 for j in range(n):
 print('Hello world')
for i in range(n): # O(n^2)
 print('Hello World')
 for j in range(n):
 print('Hello World')
for i in range(n): # O(n^2)
 for j in range(i):
 print('Hello World')
for i in range(n):
 for j in range(n):
 for k in range(n):
  print('Hello World') # O(n^3)

幾次循環(huán)就是n的幾次方的時間復(fù)雜度

n = 64
while n > 1:
 print(n)
 n = n // 2

26 = 64，log264 = 6，所以循環(huán)減半的時間復(fù)雜度為O(log2n)，即O(logn)

如果是循環(huán)減半的過程，時間復(fù)雜度為O(logn)或O(log2n)

常見的時間復(fù)雜度高低排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

空間復(fù)雜度

空間復(fù)雜度：用來評估算法內(nèi)存占用大小的一個式子

a = 'Python' # 空間復(fù)雜度為1
# 空間復(fù)雜度為1
a = 'Python'
b = 'PHP'
c = 'Java'
num = [1, 2, 3, 4, 5] # 空間復(fù)雜度為5
num = [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]] # 空間復(fù)雜度為5*4
num = [[[1, 2], [1, 2]], [[1, 2], [1, 2]] , [[1, 2], [1, 2]]] # 空間復(fù)雜度為3*2*2

定義一個或多個變量，空間復(fù)雜度都是為1，列表的空間復(fù)雜度為列表的長度

總結(jié)

以上所述是小編給大家介紹的Python算法的時間復(fù)雜度和空間復(fù)雜度，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
如果你覺得本文對你有幫助，歡迎轉(zhuǎn)載，煩請注明出處，謝謝！

您可能感興趣的文章: