數(shù)據(jù)規(guī)模

時(shí)間復(fù)雜度

并不是所有的雙層循環(huán)都是O（n^2）的

復(fù)雜度實(shí)驗(yàn)來確定復(fù)雜度

// O(N) 兩倍增加 int findMax( int arr[], int n ){assert( n > 0 );int res = arr[0];for( int i = 1 ; i < n ; i ++ )if( arr[i] > res )res = arr[i];return res;}

隨后，O（n^2），數(shù)據(jù)規(guī)模乘二，時(shí)間復(fù)雜度乘4……
隨著數(shù)據(jù)的增加，可以看到O（logN）

遞歸算法時(shí)間復(fù)雜度分析

不是有遞歸的函數(shù)就一定是O（nlogn）
深入：主定理

resize的復(fù)雜度分析——均攤復(fù)雜度 amortized time complexity

均攤分析和平均情況時(shí)間復(fù)雜度，前者是一個(gè)序列的操作取平均值，后者是針對(duì)不同輸入來計(jì)算平均值
動(dòng)態(tài)數(shù)組（Vector）每一個(gè)操作增加一個(gè)元素，刪除一個(gè)元素相應(yīng)的復(fù)雜度，就需要Amortized Time
動(dòng)態(tài)棧，動(dòng)態(tài)隊(duì)列類似（數(shù)組）

對(duì)于添加操作來說，最壞的情況是addLast(e)的時(shí)候，也需要進(jìn)行resize，那么復(fù)雜度就是O(n)級(jí)別的了。但是我們忽略了個(gè)問題：我們根本不可能每次操作的時(shí)候都會(huì)觸發(fā)resize，因此我們使用最壞的情況分析添加操作的時(shí)間復(fù)雜度是不合理的

17次基本操作包含了9次添加操作 + 8次元素轉(zhuǎn)移操作
平均，每次addLast操作，進(jìn)行2次基本操作（ 17/9 約等于2 ）
假設(shè)capacity=n，n+1次addLast，觸發(fā)resize，總共進(jìn)行2n+1次基本操作
平均，每次addLast操作，進(jìn)行2次基本操作（ 2n+1/n+1 約等于 2 ）
將1次resize的時(shí)間平攤給了n+1次addLast的時(shí)間，于是得到了平均每次addLast操作進(jìn)行2次基本操作的結(jié)論
這樣均攤計(jì)算，時(shí)間復(fù)雜度是O(1)級(jí)別的，這和我們數(shù)組中有多少個(gè)元素是沒有關(guān)系的
在這個(gè)例子里，這樣均攤計(jì)算，比計(jì)算最壞情況是有意義的，這是因?yàn)樽顗牡那闆r是不會(huì)每次都出現(xiàn)的。
關(guān)于均攤復(fù)雜度，其實(shí)在很多算法書中都不會(huì)進(jìn)行介紹，但是在實(shí)際工程中，這樣的一個(gè)思想是蠻有意義的：就是一個(gè)相對(duì)比較耗時(shí)的操作，如果我們能保證他不會(huì)每次都被觸發(fā)的話，那么這個(gè)相對(duì)比較耗時(shí)的操作它相應(yīng)的時(shí)間是可以分?jǐn)偟狡渌牟僮髦衼淼摹?
同理，我們看removeLast操作，均攤復(fù)雜度也為O(1)

resize的復(fù)雜度分析——復(fù)雜度震蕩
但是，當(dāng)我們同時(shí)看addLast和removeLast操作的時(shí)候：
假設(shè)我們現(xiàn)在有一個(gè)數(shù)組，這個(gè)數(shù)組的容量為n，并且現(xiàn)在也裝滿了元素，那么現(xiàn)在我們?cè)僬{(diào)用一下addLast操作，顯然在添加一個(gè)新的元素的時(shí)候會(huì)需要擴(kuò)容（擴(kuò)容會(huì)耗費(fèi)O(N)的時(shí)間），之后我們馬上進(jìn)行removeLast操作（根據(jù)我們之前的邏輯，在上一個(gè)操作里通過擴(kuò)容，容量變?yōu)榱?n，在我們刪除1個(gè)元素之后，元素又變?yōu)榱薾 = 2n/2，根據(jù)我們代碼中的邏輯，會(huì)觸發(fā)縮容的操作，同樣耗費(fèi)了O(n)的時(shí)間）；那么我們?nèi)绻賏ddLast、removeLast…等相繼依次操作

對(duì)于addLast和removeLast來說，都是每隔n次操作都會(huì)觸發(fā)resize，而不會(huì)每次都觸發(fā)
但是現(xiàn)在我們制造了一種情景：同時(shí)看addLast和removeLast的時(shí)候，每一次都會(huì)耗費(fèi)O(n)的復(fù)雜度，那么這就是復(fù)雜度的震蕩。
resize的復(fù)雜度分析——出現(xiàn)復(fù)雜度震蕩的原因及解決方案
removeLast時(shí)resize過于著急（采用了Eager的策略: 一旦我們的元素變?yōu)楫?dāng)前容積的1/2的時(shí)候，我們馬上就把當(dāng)前的容積也縮容為1/2）
解決方案: Lazy （在線段樹中，也會(huì)用到類似的思路）
當(dāng)元素變?yōu)楫?dāng)前容積的1/2時(shí)，不著急把當(dāng)前容積縮容，而是等等；如果后面一直有刪除操作的話，當(dāng)刪除元素到整個(gè)數(shù)組容積的1/4時(shí)，那么這樣看來我們的數(shù)組確實(shí)用不了這么大的容積，此時(shí)我們?cè)賮磉M(jìn)行縮容，縮容整個(gè)數(shù)組的1/2（這樣，即便我們要添加元素，也不需要馬上觸發(fā)擴(kuò)容操作）
當(dāng) size == capacity / 4時(shí)，才將capacity減半

總結(jié)

以上是生活随笔為你收集整理的玩转数据结构——均摊复杂度和防止复杂度的震荡（笔记）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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