一、時間復雜度規則

1、計算時，往往只關注時間頻度中最高次項，其他次要項和常數項忽略
例如： T=3*n^3+2*n^2+10000時間的復雜度： O(n^3)
2、順序結構，時間復雜度按加法來計算
讓用戶輸入2個列表，一個列表的長度為m另一個為n，對這2個列表分別求和
比較他們的和的大小
循環遍歷，分別求和，比較大小
m步、n步 時間復雜度為O(m+n)
3、循環結構，時間復雜度按乘法來運算
T=n*n*3
4、分支結構：時間復雜度取最大值
5、沒有特殊說明時，算法的時間復雜度都是指最壞的時間復雜度

最優時間復雜度：算法完成工作最少需要多久
最壞時間復雜度：算法完成工作最多需要多久
平均時間復雜度：算法完成工作平均需要多久
均攤時間復雜度：平均時間復雜度的補充，應用場景極少

例題：用戶輸入長度為6的數組,數組由1-6六個數字組成,順序隨機，請返回數字6出現的位置

for i in range(6):if lst[i]==6:print(i)break

lst=[1,2,3,4,5,6] 最壞情況O(n)
lst=[6,2,3,4,5,1] 最好情況O(1)
平均時間復雜度
6出現在每個位置的幾率時一樣的，所以時間復雜度為（1+2+3+4+5+6）/6(O(n))

二、常見時間復雜度

下圖為算法的時間頻度的增長趨勢

時間頻度：一個算法中的語句執行次數稱為語句頻度或者時間頻度，記為T(n)
時間復雜度：隨著問題的數據規模的增長，算法的時間頻度的增長趨勢，記作O(F(n))，F(n)是T(n)的漸進函數

三、列表和字典的時間復雜度

總結

以上是生活随笔為你收集整理的python—时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。