在開始二刷前，先走出舒適區(qū)，硬啃一波性能分析。盡可能用人話說清楚復(fù)雜度究竟是個啥玩意。

時間復(fù)雜度

什么是時間復(fù)雜度

顧名思義，時間復(fù)雜度（也作漸進(jìn)時間復(fù)雜度）就是描述算法運(yùn)行時間的函數(shù)。通常會用操作單元數(shù)量來代表程序消耗的時間，默認(rèn)CPU的每個單元運(yùn)行消耗的時間都是相同的。

舉個例子，假設(shè)算法問題的規(guī)模為n，那么操作單元數(shù)量便用函數(shù)f(n)來表示，隨著數(shù)據(jù)規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，記為O(f(n))。乂，這里引入了一個新的字母O，這是啥呢？

什么是大O

大O用來表示上界，上界就是算法最壞情況的運(yùn)行時間，即任意數(shù)據(jù)輸入的運(yùn)行時間最大為大O。

俗話說的好，拋開輸入數(shù)據(jù)形式來考慮運(yùn)行時間就是耍流氓。拿插入排序來說，在數(shù)據(jù)有序的情況下運(yùn)行時間是O(n)，但當(dāng)數(shù)據(jù)是逆序，插入排序的運(yùn)行時間就是O(n2)，因此插入排序的時間復(fù)雜度是O(n2) 。這不是我說的，是算法導(dǎo)論規(guī)定的（

這時候杠精就會說，乂，快速排序的時間復(fù)雜度是O(nn)，但是在數(shù)據(jù)已經(jīng)有序的情況下，它的運(yùn)行時間不是是O(n2) 嘛？確實，嚴(yán)格從大O的定義來講，快速排序的時間復(fù)雜度應(yīng)該是O(n2)。業(yè)內(nèi)的默認(rèn)規(guī)定大O代表的就是一般情況。畢竟你都有序了，還排它干嘛呢

不同數(shù)據(jù)規(guī)模的差異

時間復(fù)雜度定義為O(f(n))。從數(shù)學(xué)上考慮f(n)，當(dāng)它含有常數(shù)項且數(shù)據(jù)規(guī)模很小時，甚至用O(n2)的算法比用O(n)的更合適。但是，經(jīng)常有題解會說：”忽略常數(shù)項之后，O(n)優(yōu)于O(n2)“，這是為啥呢？

這又涉及到大O的定義，大O就是數(shù)據(jù)量級非常大的情況下所表現(xiàn)出的時間復(fù)雜度，此時常數(shù)項系數(shù)已不起決定性作用。

給出常見的比較：O(1) < O(n) < O(n) < O(nn) < O(n2) < O(n3) < O(2) < O(n!)

順便提一嘴，學(xué)過數(shù)學(xué)的都知道，f(n)可以簡化，例如后面的式子中如果包含前面的式子，那也可以忽略。

O(n)以什么數(shù)為底？

這時候，學(xué)數(shù)學(xué)的同學(xué)要問了：乂，平時說某算法的時間復(fù)雜度是n的，那么一定是以2為底n的對數(shù)么？

這個同學(xué)數(shù)學(xué)學(xué)的相當(dāng)好，在數(shù)學(xué)中，是不存在沒有底數(shù)的對數(shù)表達(dá)式的。但是在編程的世界里，有一種忽略底數(shù)的描述。舉個例子，假如有兩個算法，它們的時間復(fù)雜度分別是n和n。根據(jù)高中數(shù)學(xué)， n= 10 * 。 10是一個常數(shù)，大O中常數(shù)項可忽略。由此可見，大O中，任何底數(shù)其實都是一個玩意，所以可以將其忽略。

超時測試實驗結(jié)果

任何開發(fā)計算機(jī)程序員的軟件工程師都應(yīng)該能夠估計這個程序的運(yùn)行時間是一秒鐘還是一年。對于計算機(jī)硬件要至少有大概的概念，這也是為啥力扣的提示中提示各種數(shù)據(jù)范圍和時間限制，要會根據(jù)這些提示估計程序的時間復(fù)雜度大概是多少，再采取符合要求的算法。

直接給出大致的實驗結(jié)果，數(shù)字代表對應(yīng)時間復(fù)雜度的算法每秒能運(yùn)行的次數(shù)：（一定不是我懶得自己敲一遍）O(n)：、O(n2)：、O(nn)：。

空間復(fù)雜度

和時間類似，空間復(fù)雜度也可以用O(f(n))來表示。采用此種辦法可以對程序運(yùn)行中需要多少內(nèi)存進(jìn)行估計。

常見問題

第一個常識是——空間復(fù)雜度是考慮程序運(yùn)行時占用內(nèi)存的大小，而不是可執(zhí)行文件的大小。

第二個常識是——很多因素會影響程序真正使用的內(nèi)存，所以空間復(fù)雜度僅僅是個大體的預(yù)估。

第三個常識是——O(1)、O(n)等空間復(fù)雜度都好理解，而O(n)的空間復(fù)雜度在遞歸算法中出現(xiàn)。

Java的內(nèi)存管理

Java依賴內(nèi)置虛擬機(jī)來做內(nèi)存管理，因此不需要程序員去考慮內(nèi)存泄漏的問題。

順便引入一下內(nèi)存對齊的概念，在Java八股中很少提到，了解一下?？缙脚_的編程語言都需要做內(nèi)存對齊，其實并不僅限于C語言，當(dāng)然內(nèi)存對齊還有助于大幅度提高運(yùn)行速度。

CPU讀取內(nèi)存不是一次讀取單個字節(jié)，而是一塊一塊的來讀取內(nèi)存，塊的大小可以是2，4，8，16個字節(jié)，具體取多少個字節(jié)取決于硬件。在存儲數(shù)據(jù)時，如果劃分的是四字節(jié)，而實際數(shù)據(jù)只占用一字節(jié)，那么多余的三字節(jié)就被浪費了。但是在讀取過程中，每次讀對應(yīng)的地址位置即可，而不需要讀多個，再裁剪、拼貼。所謂的內(nèi)存對齊，就是犧牲空間，換取時間。

遞歸分析

接下來，就用最難分析的遞歸算法為例，總結(jié)一下算法性能的分析方法。

求x的n次方

譬如，現(xiàn)在你在面試阿里云，面試官出了一道題：求x的n次方。這還不簡單，秒寫出如下代碼：

int result = 1;  // 注意 任何數(shù)的0次方等于1
for (int i = 0; i < n; i++) result = result * x;
return result;

此時，面試官問，有無效率更高的算法呢？這時候馬上想到了遞歸，開寫！

int function(int x, int n) {
    if (n == 0) return 1; // return 1 同樣是因為0次方是等于1的
    return function(x, n - 1) * x;
}

面試官微微一笑，問：此代碼時間復(fù)雜度是多少呢？遞歸嘛，復(fù)雜度肯定是O(n)，你這么答，遂寄。

遞歸算法的時間復(fù)雜度本質(zhì)上是要看: 遞歸的次數(shù) * 每次遞歸中的操作次數(shù)。每次n-1，遞歸了n次時間復(fù)雜度是O(n)，每次進(jìn)行了一個乘法操作，乘法操作的時間復(fù)雜度是一個常數(shù)項1，所以這份代碼的時間復(fù)雜度是 n × 1 = O(n)。

正確的標(biāo)準(zhǔn)答案如下，利用了等比數(shù)列的求和公式，抽取出了遞歸操作：

int function(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    int t = function(x, n / 2);//若將此式子放入判斷語句中，則復(fù)雜度仍為O(n)
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}

僅僅有一個遞歸調(diào)用，且每次都是n/2 ，所以一共調(diào)用了log以2為底n的對數(shù)次。這么答，面試官應(yīng)該是很滿意的，但是初見的同學(xué)會感覺非常抽象。接下來用圖表詳細(xì)說明。

顯然有如下公式：，轉(zhuǎn)換形式之后可得：。又因為每次遞歸都是一次乘法操作，它的時間復(fù)雜度即為O(n)。

斐波那契數(shù)列

動態(tài)規(guī)劃刷的第一道題就是此題，代碼基本都能背出來了：

int fibonacci(int i) {
       if(i <= 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonacci(i-2);
}

非常簡單的式子，但是每次遞歸有1次加法，有2個遞歸調(diào)用（這里采用2叉樹分析）。其復(fù)雜度為O()，很明顯太大了。

那就減少一下遞歸的調(diào)用次數(shù)唄：

int fibonacci(int first, int second, int n) {
    if (n <= 0) return 0;
    if (n < 3) {
        return 1;
    } else if (n == 3) {
        return first + second;
    } else {
        return fibonacci(second, first + second, n - 1);
    }

用first和second來記錄當(dāng)前相加的兩個數(shù)值，此時就不用兩次遞歸了。只是遞歸了n次，所以時間復(fù)雜度是O(n)。遞歸算法的空間復(fù)雜度 = 每次遞歸的空間復(fù)雜度 * 遞歸深度。從代碼中可以看出每次遞歸所需要的空間大小都是一樣的，它需要的空間是一個常量，并不會隨著n的變化而變化，每次遞歸的空間復(fù)雜度就是O(1)。

遞歸第n個斐波那契數(shù)的話，遞歸調(diào)用棧的深度就是n（又是二叉樹的知識，畫圖?。?。每次遞歸的空間復(fù)雜度是O(1)， 調(diào)用棧深度為n，所以這段遞歸代碼的空間復(fù)雜度就是O(n)。

總結(jié)

對于時間和空間復(fù)雜度有了最基本的了解，以后每刷一題，都要學(xué)會自己分析其性能。