我們都知道數(shù)據(jù)結(jié)構(gòu)和算法都是為了讓代碼運(yùn)行得更快，并且消耗更少的存儲(chǔ)空間，但是我們要怎么才能知道一段代碼對(duì)時(shí)間和空間的損耗？
事后統(tǒng)計(jì)法
正常來說我們說代碼執(zhí)行得慢或者占用空間大，都是通過監(jiān)控系統(tǒng)或者統(tǒng)計(jì)得出的結(jié)論，這也被叫做事后統(tǒng)計(jì)法。
但他也有很多的問題：
- 結(jié)果與運(yùn)行環(huán)境強(qiáng)相關(guān)
不同的環(huán)境往往能得出不同甚至相反的結(jié)果。 - 與數(shù)據(jù)量強(qiáng)相關(guān)
在數(shù)據(jù)量小的時(shí)候性能可能非常良好，但是數(shù)據(jù)量一大，性能突然急劇下降。
大O復(fù)雜度表示法
image.png
T(n)：代碼執(zhí)行的時(shí)間
n：數(shù)據(jù)的規(guī)模
f(n): 每行代碼執(zhí)行的次數(shù)總和
O：代表代碼的執(zhí)行時(shí)間T(n)和f(n)成正比
大O時(shí)間復(fù)雜度表示法，它不代表代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，也叫做 漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱 時(shí)間復(fù)雜度。
時(shí)間復(fù)雜度分析
- 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
- 只關(guān)注量級(jí)最大的那段代碼
- 嵌套部分等于嵌套內(nèi)外復(fù)雜度的乘積
常見時(shí)間復(fù)雜度
image.png
O(1): 只要不存在循環(huán)遞歸，那么時(shí)間復(fù)雜度就是 O(1)
O(logn)、O(nlogn): 常見于 歸并排序、快速排序
O(m+n)、O(m·n): 當(dāng)代碼中存在兩個(gè)不可評(píng)估的數(shù)據(jù)時(shí)，時(shí)間復(fù)雜度為它們的總和或者乘積
版權(quán)聲明：筆記部分摘抄自極客時(shí)間中的課程及評(píng)論區(qū)
