到底什么才是真正的空間復雜度?

關注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎、架構(gòu)知識！

你好，我是彤哥，一個每天爬二十六層樓還不忘讀源碼的硬核男人。

上一節(jié)，我們一起學習了復雜度分析的套路和常見的復雜度。

但是，我們的案例基本都是以時間復雜度為主，很少接觸到空間復雜度。

那么，到底什么才是真正的空間復雜度呢？在空間與時間發(fā)生沖突時又該如何權(quán)衡呢？

本節(jié)，我們就來解決這兩個問題。

現(xiàn)在有一個算法是這樣的，給定一個數(shù)組，將數(shù)組中每個元素都乘以2返回，我實現(xiàn)了下面兩種形式：

private static int[] multi1(int[] array) {
int[] newArray = new int[array.length];
for (int i = 0; i < array.length; i++) {
        newArray[i] = array[i] * 2;
    }
return newArray;
}

private static int[] multi2(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = array[i] * 2;
    }
return array;
}

暫且不論這兩個算法孰好孰壞，你來猜猜他們的空間復雜度各是多少？

你可能會說第一個算法的空間復雜度為O(n)，第二個算法的空間復雜度為O(1)。

錯！兩個算法的空間復雜度都是O(n)。

也不能說你完全錯了，因為大部分書籍或者資料都弄錯了。

是時候了解真正的空間復雜度了。

空間復雜度，是指一個算法運行的過程占用的空間，這個空間包括輸入?yún)?shù)的占用空間和額外申請的空間。

所以，針對上面兩個算法：

• 第一個算法，輸入?yún)?shù)n，額外空間n，兩者相加為2n，去除常數(shù)項，空間復雜度為O(n)；

• 第二個算法，輸入?yún)?shù)n，額外空間0，兩者相加為n，空間復雜度為O(n)。

可以看到，使用空間復雜度很難判斷這兩個算法的好壞，所以，誕生了另一個概念——額外空間復雜度。

額外空間復雜度，是指一個算法運行過程中額外申請的空間。

使用額外空間復雜度，針對上面兩個算法：

• 第一個算法，額外空間為n，額外空間復雜度為O(n)；

• 第二個算法，額外空間為0，額外空間復雜度為O(1)；

似乎沒見過有O(0)這種寫法。

可以看到，使用額外空間復雜度能夠很輕易地判斷兩個算法的好壞（從空間占用的角度）。

所以，是時候糾正錯誤的概念了，以后與人交流的時候請使用“額外空間復雜度”這個概念。

時間與空間往往是一組糾纏在一起的概念，就像很多小說中寫的一樣，主角最終領悟了時空法則，成為了最強者，小說結(jié)束。

在數(shù)據(jù)結(jié)構(gòu)與算法中也是一樣，時間與空間往往同時出現(xiàn)，而且經(jīng)常朝著相反的方向運動。

比如，對于排序算法：

• 冒泡排序，時間復雜度O(n^2)，空間復雜度O(1)

• 歸并排序，時間復雜度O(nlogn)，空間復雜度O(n)

所以，有兩種思想：以時間換空間，以空間換時間。

那么，哪種算法更好呢？

我認為，如果有時間、空間同時比較小的為最好，退而求其次，我選擇以空間換時間，畢竟，隨著計算機硬件技術地不斷發(fā)展，空間越來越不值錢，而時間卻越來越值錢，所以，以空間換時間也是一種常用的思想，在我們后續(xù)的課程中會出現(xiàn)大量以空間換時間的案例。

想知道冒泡排序和歸并排序算法的復雜度如何計算嗎？來呀，關注我吧。

本節(jié)，我們從一個小例子入手，分析了兩種算法的空間復雜度，并引出空間復雜度的真身——額外空間復雜度，最后，通過對比冒泡排序和歸并排序的時間復雜度和空間復雜度，得出了以空間換時間的思想。

到這里，關于復雜度相關的章節(jié)就寫完了，從下一節(jié)開始，我們將進入常用數(shù)據(jù)結(jié)構(gòu)與算法的學習中，敬請期待。

P.S. 下周將進行晉升答辯，會停更幾天，敬請諒解。