1暮刃、復(fù)雜度分析

我們現(xiàn)在所實現(xiàn)的這個動態(tài)數(shù)組，對于添加操作來說爆土，它的時間復(fù)雜度是O(n)的椭懊。是因為對于我的時間復(fù)雜度來說，通常我們都是考慮最壞的情況步势，雖然在尾部添加1個元素氧猬，它的時間復(fù)雜度是O(1)的。但是我們不能僅僅考慮這種情況坏瘩，正是因為如此對于通常的這種動態(tài)數(shù)組盅抚，添加操作時間復(fù)雜度是O(n)級別的。但是如果我們保證添加元素的時候倔矾，只在我們組的尾部添加元素的話妄均，換句話說，我肯定inserFirst和insert這兩個方法哪自，我根本不用的話丰包，很顯然，此時這個添加操作壤巷，它的時間復(fù)雜度就變成O(1)的了邑彪。但是由于對我們的動態(tài)數(shù)組來說，有resize這個方法胧华。思考一下寄症，我們的復(fù)雜度分析分析的都是最最壞的情況，在這種情況下最壞的情況就是insertLast了矩动，添加1個元素有巧，同時也要進行擴容，由于這個擴容是一個O(n)級別的復(fù)雜度铅忿，所以使得我們整個添加操作依然是O(n)級別的剪决。

image

2、不是每次都最壞

當然，我從最壞的角度這么分析是對的柑潦，但是這里我們忽略了一個問題享言。這個問題其實就是我們不可能每一次添加元素的時候，都觸碰這個resize操作渗鬼。根據(jù)我們之前的邏輯览露，假設(shè)我們的數(shù)組有十個空間，那么我們要添加10次元素之后譬胎，才會觸發(fā)一次resize差牛，而觸發(fā)這一次resize之后，我們的數(shù)組的容量就會變成20堰乔。此時我們添加元素要再添加10個元素才會再觸發(fā)一次resize偏化，之后我們整個數(shù)組空間就會變成40，我們要再添加20次元素镐侯，才會再觸發(fā)一次resize侦讨，以此類推。我們根本不可能每次添加元素都觸發(fā)這個resize苟翻，正因為如此對于這種情況我們使用最壞的情況分析是稍微有一些不合理的韵卤，此時我們應(yīng)該怎么分析這個insertLast的時間復(fù)雜度呢？

image

3崇猫、均攤分析

我們可以這樣的來看這個問題沈条，假設(shè)當前我這個數(shù)組容量為8的話，并且我每一次添加都使用insertLast诅炉，也就是在添加元素這一部上我都是O(1)的復(fù)雜度蜡歹。很顯然我需要經(jīng)過8次元素的添加，每一次都是O(1)的復(fù)雜度汞扎。之后我再添加第9個元素的時候季稳，我就發(fā)現(xiàn)我現(xiàn)在的數(shù)組已經(jīng)滿了，所以首先我要resize一下澈魄。那么這個resize操作景鼠，我要把之前添加的八個元素全都復(fù)制到新的這個靜態(tài)數(shù)組中。所以消耗8的時間痹扇，之后我再添加這一次元素再加上1铛漓。也就是整體上，我這九次操作就觸發(fā)了一次resize鲫构，總共的其實進行了17次基本的操作浓恶。在這里恳守，我們假想這個基本的操作就是給一個空間賦上一個值稿辙，那么這17次基本操作就是9次的添加操作和8次的這個元素轉(zhuǎn)移的操作。這樣來看的話演侯，相當于對于這9次操作，平均來講伐憾，每次這個insertLast操作大概進行了兩次基本操作勉痴，那么這個計算方法是17÷9他比2了還少一些，但是呢树肃，在這里我約等于2了蒸矛。換句話說，我們把這個結(jié)論再推廣一下胸嘴，假設(shè)我們當前這個數(shù)組容量等于n的話雏掠，那么相當于我要進行n加1次的添加操作才會觸發(fā)一次resize×酉瘢總共進行了2n加1次基本操作乡话。這個2n加1的計算方法就是n加上這個n加1，那么用2n加1除以n加1耳奕，平均來講其實我們每一次的insertLast操作進行了兩次基本操作蚊伞。同學(xué)們可以仔細思考一下這樣的一種計算方式，相當于是說我在考慮我的resize操作實際上不可能每次insertLast的時候都會觸發(fā)一次resize吮铭。所以我綜合n加1次insertLast，那么n加1次insertLast其實只會觸發(fā)一次的resize颅停，我將這一次resize的時間平攤給了這n加1次的insertLast谓晌。

image

4、均攤時間復(fù)雜度

于是得到了這個結(jié)論癞揉，平均每一次這個inserLast的操作進行了兩次基本操作纸肉，平均每次進行兩次基本操作，意味著什么喊熟？意味著這樣來算的話柏肪，我們的這個insertLast操作它的時間復(fù)雜度是O(1)級別的，它和我們當前這個數(shù)組中有多少個元素是完全沒有關(guān)系的芥牌。在我們的這個例子里其實這樣均攤計算比計算最壞的情況是有意義的烦味，這就是因為那個最壞的情況不會每次都出現(xiàn)。那么壁拉，我們這樣計算復(fù)雜度就稱之為是均攤復(fù)雜度谬俄，關(guān)于均攤復(fù)雜度，其實弃理，很多算法的教材中可能都不進行介紹溃论，但是在實際工程中，這樣的一個思想的還是蠻有意義的痘昌。就是一個相對比較耗時的操作钥勋，如果我們能保證他不會每次都觸發(fā)的話炬转，那么這個相對比較耗時的操作，相應(yīng)的這個時間是可以分攤到其它的操作中來的算灸。我們用同樣的思考扼劈，也可以想象removeLast的這個操作，雖然它的最壞時間復(fù)雜度O(n)級別的乎婿，但是它的均攤復(fù)雜度也是O(1)級別的测僵。

image

5、極端情況考慮

現(xiàn)在我們通過均攤復(fù)雜度的分析谢翎，看起來insertLast和removeLast這兩個操作捍靠，其實都是O(1)級別的操作∩可是當我們同時思考這兩個操作的時候出現(xiàn)了一個問題榨婆，這個問題呢，通常稱為復(fù)雜度的震蕩褒侧。這個問題是什么呢良风？我們簡單的來看一下，假設(shè)現(xiàn)在我們有一個數(shù)組闷供，他們這個數(shù)組烟央，它的容量的是n，并且呢歪脏，現(xiàn)在已經(jīng)裝滿了這個元素疑俭。那么想象一下此時我再調(diào)用一下insertLast這個操作的話，添加1個新的元素婿失，顯然要擴容钞艇。那么這個擴容的過程就會耗費O(n)的時間。之后豪硅，馬上進行removeLast的這個操作哩照，根據(jù)我們之前的邏輯，在上一個操作里懒浮，由于我擴容了擴容之后飘弧，我現(xiàn)在的容量的其實就變成2n了。現(xiàn)在我又把剛剛添加的那個元素給刪除了嵌溢，在刪除之后眯牧，現(xiàn)在我這個數(shù)組中的元素數(shù)是n，n是2n的二分之一赖草。所以此時對于removeLast這個操作我們觸發(fā)了它的這個縮容的過程学少，也就是又要調(diào)用一遍resize，它的時間復(fù)雜度依然是O(n)的秧骑。在這種情況下版确，假如我又添加了一次元素扣囊，再調(diào)一次insertLast，其實重復(fù)了一下之前的過程绒疗，現(xiàn)在由于我的容積是n的侵歇，那么我就又要擴容擴容到2n的情況，時間復(fù)雜度是O(n)級別的吓蘑。之后我再進行一下刪除操作惕虑，刪除之后，我現(xiàn)在這個數(shù)組中的元素有n個元素磨镶，他是當前2n這個容積的二分之一溃蔫。所以我要再進行縮容，這個縮絨的過程又耗費O(n)的時間琳猫。我之前曾經(jīng)說過伟叛，對于調(diào)用insertLast和removeLast的來說都是每隔n次，才會觸發(fā)一次resize脐嫂，而不會每次都觸發(fā)resize统刮。但是現(xiàn)在我們制造了一個情景，當我們同時看這個insertLast和removeLast的時候账千，存在某種情況侥蒙，每一次都會耗費O(n)的復(fù)雜度，這就是復(fù)雜度的震蕩匀奏。

image

6辉哥、復(fù)雜度震蕩

明明在均攤的時候，我們想的挺好攒射，應(yīng)該變成一個O(1)的復(fù)雜度，但是在一些特殊的情況下恒水，這個復(fù)雜度猛地躥到了O(n)這個級別会放，產(chǎn)生了這個震蕩。對于這個問題應(yīng)該怎么解決呢钉凌？我們可以簡單的來分析一下咧最，這個問題發(fā)生的原因是什么？出問題的原因御雕，其實在于removeLast的時候矢沿，我們resize的有些過于著急，也就是說我們采用了一種酸纲，有的時候稱為是非常激進的非常急的一個策略捣鲸。我們的元素變?yōu)楫斍叭莘e的二分之一的時候，我們馬上就把當前的容積也縮絨成為了二分之一闽坡，此時栽惶，我們整個數(shù)組中元素是滿的愁溜，也就是元素的個數(shù)和容積的數(shù)量是相等的。那么外厂，在這種情況下冕象，我們再添加1個元素，自然而然的就需要進行擴容了汁蝶。解決方案是什么渐扮？

7、懶惰的解決方案

解決方案是使用相對來說更加懶惰一些的策略掖棉。那么墓律，這是什么意思呢？我們可以看一下啊片，比如說當前這個數(shù)組初始的時候只锻，它的容積是n，元素是空的紫谷，當我們把這個數(shù)組的元素全都填滿的時候齐饮。根據(jù)我們剛才的設(shè)計，此時我們再添加1個元素笤昨，那么我們就需要擴容了祖驱，這是一定的。因為我們添加元素的時候瞒窒，如果容量不夠的話捺僻，只能通過擴容來處理，但關(guān)鍵在于當我們刪除1個元素的時候崇裁，那么此時我們數(shù)組中的元素數(shù)量是容積的二分之一了匕坯，不著急，現(xiàn)在就把我們的整個動態(tài)數(shù)組的容量進行縮容拔稳。而是再等等葛峻，如果后面一直有刪除操作的話，刪除到了是整個數(shù)組容積的四分一了巴比，那么此時术奖，我們再來說，看來現(xiàn)在我們的這個數(shù)組確實是用不了這么大的空間轻绞。我們再進行縮容采记，但是縮容只縮容整個數(shù)組的二分之一的空間，我們還預(yù)留出了一半的空間政勃。在這種情況下唧龄，如果我們再要添加元素，也不需要馬上就觸發(fā)擴容操作奸远。我們的策略就變成了选侨，我們數(shù)組中的元素數(shù)是我們整個容積的四分之一的時候掖鱼，才將整個容積減半，也就是說我們犯懶了援制，不是在數(shù)組中的元素數(shù)是容積的一半的時候戏挡，我們就馬上把這個容積變成一半了。通過這樣的策略我們就防止了復(fù)雜度的震蕩晨仑，這種懶惰的方式褐墅，其實是很有意思的一種方式，在算法的領(lǐng)域洪己，有的時候我們懶一些妥凳，反而最終算法的整體性能會更好。在后續(xù)我講到線段樹的時候答捕，還會有這樣的一個例子逝钥，大家會看到。當我們更懶的時候拱镐，其實是在改善我們的算法性能艘款，不過在這里，同學(xué)們不要誤會沃琅，我們說哗咆，我們的算法更懶，不代表這個代碼容易編寫益眉，也不代表代碼量更少晌柬，那么在后續(xù)。那個線段樹的例子中同學(xué)們就會看到郭脂，其實我們要向加入這個懶的機制年碘，反而要寫更多的代碼，對于這點的同學(xué)展鸡，現(xiàn)在先有個印象就好了盛泡。

8、代碼實現(xiàn)

那么下面呢娱颊？我們把我們的這種懶的策略，實際用編程的方式反應(yīng)在自己的這個動態(tài)數(shù)據(jù)相應(yīng)的代碼中凯砍。

// 刪除某個位置上的元素
int AMGArray::remove(int index) {
    if ( index < 0 || index >= size ) {
        cout << "remove Index 不合法 " << index << endl;
        return -1;
    }
    // 從index位置開始往后賦值
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i + 1];
    }
    int res = data[index];
    data[size - 1] = 0;  // 游蕩元素
    size--;
    // 縮容
    if ( size == capacity / 4 && 0 != capacity / 2 ) {
        resize(capacity / 2);
    }
    return res;
}