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

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

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

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

其作用：

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

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

計(jì)算時(shí)間復(fù)雜度的方法：

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

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

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

時(shí)間復(fù)雜度是用來估計(jì)算法運(yùn)行時(shí)間的一個(gè)式子（單位），一般來說，時(shí)間復(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的幾次方的時(shí)間復(fù)雜度

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

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

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

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

空間復(fù)雜度

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

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

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

總結(jié)

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

您可能感興趣的文章: