Python算法中時間復雜度和空間復雜度的示例分析

小編給大家分享一下Python算法中時間復雜度和空間復雜度的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

算法復雜度分為時間復雜度和空間復雜度。

其作用：

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

簡單來說，時間復雜度指的是語句執行次數，空間復雜度指的是算法所占的存儲空間

計算時間復雜度的方法：

• 用常數1代替運行時間中的所有加法常數

• 修改后的運行次數函數中，只保留最高階項

• 去除最高階項的系數

時間復雜度

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

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

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)

 幾次循環就是n的幾次方的時間復雜度

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

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

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

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

空間復雜度

空間復雜度：用來評估算法內存占用大小的一個式子

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

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

以上是“Python算法中時間復雜度和空間復雜度的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！