漸進(jìn)式復(fù)雜度分析

• • • 概念
    • 目的
    • 大O表示法
    • 復(fù)雜度分析方法
    • 常用復(fù)雜度級別
    • 復(fù)雜度分析的4個概念

概念

復(fù)雜度描述的是算法執(zhí)行時間（或占用空間）與數(shù)據(jù)規(guī)模的增長關(guān)系，描述了當(dāng)數(shù)據(jù)量趨近于無窮大的時候，算法的執(zhí)行時間或數(shù)據(jù)占用空間，因此常量級（不隨數(shù)據(jù)的增長而增長）的執(zhí)行時間是忽略的。

目的

和性能測試相比，復(fù)雜度分析有不依賴執(zhí)行環(huán)境、成本低、效率高、易操作、指導(dǎo)性強(qiáng)的特點。但是具體問題不一定符合負(fù)責(zé)度分析的結(jié)構(gòu)，所以特殊情況還是需要做性能測試。

大O表示法

為了方便計算，我們把每行代碼執(zhí)行一次的時間都看做相等的，因此只要計算該算法一共執(zhí)行了幾次代碼行就能得出時間復(fù)雜度。算法的執(zhí)行時間與每行代碼的執(zhí)行次數(shù)成正比，用T(n) = O(f(n))表示，其中T(n)表示算法執(zhí)行總時間，f(n)表示每行代碼執(zhí)行總次數(shù)，而n往往表示數(shù)據(jù)的規(guī)模。該方法把算法所需要的時間，空間簡單量化了，表達(dá)式一目了然，非常清晰。

復(fù)雜度分析方法

以時間復(fù)雜度為例，由于時間復(fù)雜度描述的是算法執(zhí)行時間與數(shù)據(jù)規(guī)模的增長變化趨勢，所以常量階、低階以及系數(shù)實際上對這種增長趨勢不產(chǎn)決定性影響，所以在做時間復(fù)雜度分析時忽略這些項。以下為常用方法：

單段代碼看高頻：比如循環(huán)。

多段代碼取最大：比如一段代碼中有單循環(huán)和多重循環(huán)，那么取多重循環(huán)的復(fù)雜度。

嵌套代碼求乘積：比如遞歸、多重循環(huán)等

多個規(guī)模求加法：比如方法有兩個參數(shù)控制兩個循環(huán)的次數(shù)，那么這時就取二者復(fù)雜度相加。

常用復(fù)雜度級別

• 多項式階：
  隨著數(shù)據(jù)規(guī)模的增長，算法的執(zhí)行時間和空間占用，按照多項式的比例增長。以下復(fù)雜度按照從低到高進(jìn)行排序：
  O(1)（常數(shù)階）、O(logn)（對數(shù)階）、O(n)（線性階）、O(nlogn)（線性對數(shù)階）、O(n^{2)（平方階）、O(n}3)（立方階）

• 非多項式階：
  隨著數(shù)據(jù)規(guī)模的增長，算法的執(zhí)行時間和空間占用暴增，這類算法性能極差。包括:
  O(2^n)（指數(shù)階）、O(n!)（階乘階）

復(fù)雜度分析的4個概念

最壞情況時間復(fù)雜度（best case time complexity）：代碼在最理想情況下執(zhí)行的時間復(fù)雜度。

最好情況時間復(fù)雜度（worst case time complexity）：代碼在最壞情況下執(zhí)行的時間復(fù)雜度。

平均時間復(fù)雜度（average case time complexity）：代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示。也叫作加權(quán)平局復(fù)雜度，或者期望時間復(fù)雜度。

均攤時間復(fù)雜度（amortized case time complexity）：在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級別的復(fù)雜度，個別情況是高級別復(fù)雜度且發(fā)生具有時序關(guān)系時，可以將個別高級別復(fù)雜度均攤到低級別復(fù)雜度上。基本上均攤結(jié)果就等于低級別復(fù)雜度。可以認(rèn)為均攤時間復(fù)雜度就是一種特殊的平均時間復(fù)雜度。（似乎使用這2種方法得出的結(jié)論是一樣的）

總結(jié)

以上是生活随笔為你收集整理的渐进式复杂度分析-学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。