時間復(fù)雜度
表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以，也叫作漸進(jìn)時間復(fù)雜度（asymptotic time complexity），簡稱時間復(fù)雜度。大 O 時間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時間。
時間復(fù)雜度分析
- 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼：大 O 這種復(fù)雜度表示方法只是表示一種變化趨勢。我們通常會忽略掉公式中的常量、低階、系數(shù)，只需要記錄一個最大階的量級就可以了。
- 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度。
- 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
時間復(fù)雜度分類
1.最好情況時間復(fù)雜度：就是在最理想的情況下，執(zhí)行這段代碼的時間復(fù)雜度。
2.最壞情況時間復(fù)雜度：就是在最糟糕的情況下，執(zhí)行這段代碼的時間復(fù)雜度。
3.平均時間復(fù)雜度：加權(quán)平均值，也叫作期望值，所以平均時間復(fù)雜度的全稱應(yīng)該叫加權(quán)平均時間復(fù)雜度或者期望時間復(fù)雜度。
4.均攤時間復(fù)雜度：通過攤還分析得到的時間復(fù)雜度我們起了一個名字，叫均攤時間復(fù)雜度。
常見時間復(fù)雜度實(shí)例分析
多項(xiàng)式量級和非多項(xiàng)式量級。其中，非多項(xiàng)式量級只有兩個：O(2n) 和 O(n!)。
我們把時間復(fù)雜度為非多項(xiàng)式量級的算法問題叫作 NP（Non-Deterministic Polynomial，非確定多項(xiàng)式）問題。只要算法中不存在循環(huán)語句、遞歸語句，即使有成千上萬行的代碼，其時間復(fù)雜度也是Ο(1)。在采用大 O 標(biāo)記復(fù)雜度的時候，可以忽略系數(shù)
空間復(fù)雜度分析
時間復(fù)雜度的全稱是漸進(jìn)時間復(fù)雜度，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關(guān)系?？臻g復(fù)雜度全稱就是漸進(jìn)空間復(fù)雜度（asymptotic space complexity），表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。
總結(jié)：時間復(fù)雜度和空間復(fù)雜度，用來分析算法執(zhí)行效率與數(shù)據(jù)規(guī)模之間的增長關(guān)系，可以粗略地表示，越高階復(fù)雜度的算法，執(zhí)行效率越低。常見的復(fù)雜度并不多，從低階到高階有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)。
