時間復(fù)雜度
設(shè) 為問題規(guī)模. 當(dāng)
趨于無窮時, 若程序執(zhí)行的次數(shù)
與
為同階的無窮大, 則稱算法的時間復(fù)雜度
時間復(fù)雜度的求法: 對于一段代碼, 設(shè)執(zhí)行完畢需要m步, 然后設(shè)法尋找m與問題規(guī)模 n之間的等量關(guān)系(利用循環(huán)的邊界條件). 示例如下
def fun(n):
i = 0
while n >= (i+1)**2:
i += 1
分析 設(shè)執(zhí)行完畢需要m次. 第m次時 略小于
, 引入一個起修正作用的常數(shù)
, 有
即
也就是說時間復(fù)雜度為
參考資料
-
時間復(fù)雜度十道練習(xí)題目
-
時間復(fù)雜度和空間復(fù)雜度敢订，大O表示法【數(shù)據(jù)結(jié)構(gòu)和算法入門2】
https://www.bilibili.com/video/BV14j411f7DJ?from=search&seid=333313584522830031
-
【時間復(fù)雜度】聽說你覺得時間復(fù)雜度很復(fù)雜装处？不妨聽聽我的理解
https://www.bilibili.com/video/BV18g4y1i729/?spm_id_from=333.788.videocard.0
