數據規模

時間復雜度

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

復雜度實驗來確定復雜度

// 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），數據規模乘二，時間復雜度乘4……
隨著數據的增加，可以看到O（logN）

遞歸算法時間復雜度分析

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

resize的復雜度分析——均攤復雜度 amortized time complexity

均攤分析和平均情況時間復雜度，前者是一個序列的操作取平均值，后者是針對不同輸入來計算平均值
動態數組（Vector）每一個操作增加一個元素，刪除一個元素相應的復雜度，就需要Amortized Time
動態棧，動態隊列類似（數組）

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

17次基本操作包含了9次添加操作 + 8次元素轉移操作
平均，每次addLast操作，進行2次基本操作（ 17/9 約等于2 ）
假設capacity=n，n+1次addLast，觸發resize，總共進行2n+1次基本操作
平均，每次addLast操作，進行2次基本操作（ 2n+1/n+1 約等于 2 ）
將1次resize的時間平攤給了n+1次addLast的時間，于是得到了平均每次addLast操作進行2次基本操作的結論
這樣均攤計算，時間復雜度是O(1)級別的，這和我們數組中有多少個元素是沒有關系的
在這個例子里，這樣均攤計算，比計算最壞情況是有意義的，這是因為最壞的情況是不會每次都出現的。
關于均攤復雜度，其實在很多算法書中都不會進行介紹，但是在實際工程中，這樣的一個思想是蠻有意義的：就是一個相對比較耗時的操作，如果我們能保證他不會每次都被觸發的話，那么這個相對比較耗時的操作它相應的時間是可以分攤到其它的操作中來的。
同理，我們看removeLast操作，均攤復雜度也為O(1)

resize的復雜度分析——復雜度震蕩
但是，當我們同時看addLast和removeLast操作的時候：
假設我們現在有一個數組，這個數組的容量為n，并且現在也裝滿了元素，那么現在我們再調用一下addLast操作，顯然在添加一個新的元素的時候會需要擴容（擴容會耗費O(N)的時間），之后我們馬上進行removeLast操作（根據我們之前的邏輯，在上一個操作里通過擴容，容量變為了2n，在我們刪除1個元素之后，元素又變為了n = 2n/2，根據我們代碼中的邏輯，會觸發縮容的操作，同樣耗費了O(n)的時間）；那么我們如果再addLast、removeLast…等相繼依次操作

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