到底什么才是真正的空間復(fù)雜度?
關(guān)注公眾號(hào)“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識(shí)！
你好，我是彤哥，一個(gè)每天爬二十六層樓還不忘讀源碼的硬核男人。
上一節(jié)，我們一起學(xué)習(xí)了復(fù)雜度分析的套路和常見的復(fù)雜度。
但是，我們的案例基本都是以時(shí)間復(fù)雜度為主，很少接觸到空間復(fù)雜度。
那么，到底什么才是真正的空間復(fù)雜度呢？在空間與時(shí)間發(fā)生沖突時(shí)又該如何權(quán)衡呢？
本節(jié)，我們就來(lái)解決這兩個(gè)問(wèn)題。
來(lái)個(gè)例子現(xiàn)在有一個(gè)算法是這樣的，給定一個(gè)數(shù)組，將數(shù)組中每個(gè)元素都乘以2返回，我實(shí)現(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;
}
暫且不論這兩個(gè)算法孰好孰壞，你來(lái)猜猜他們的空間復(fù)雜度各是多少？
你可能會(huì)說(shuō)第一個(gè)算法的空間復(fù)雜度為O(n)，第二個(gè)算法的空間復(fù)雜度為O(1)。
錯(cuò)！兩個(gè)算法的空間復(fù)雜度都是O(n)。
也不能說(shuō)你完全錯(cuò)了，因?yàn)榇蟛糠謺蛘哔Y料都弄錯(cuò)了。
是時(shí)候了解真正的空間復(fù)雜度了。
空間復(fù)雜度與額外空間復(fù)雜度空間復(fù)雜度，是指一個(gè)算法運(yùn)行的過(guò)程占用的空間，這個(gè)空間包括輸入?yún)?shù)的占用空間和額外申請(qǐng)的空間。
所以，針對(duì)上面兩個(gè)算法：
第一個(gè)算法，輸入?yún)?shù)n，額外空間n，兩者相加為2n，去除常數(shù)項(xiàng)，空間復(fù)雜度為O(n)；
第二個(gè)算法，輸入?yún)?shù)n，額外空間0，兩者相加為n，空間復(fù)雜度為O(n)。
可以看到，使用空間復(fù)雜度很難判斷這兩個(gè)算法的好壞，所以，誕生了另一個(gè)概念——額外空間復(fù)雜度。
額外空間復(fù)雜度，是指一個(gè)算法運(yùn)行過(guò)程中額外申請(qǐng)的空間。
使用額外空間復(fù)雜度，針對(duì)上面兩個(gè)算法：
第一個(gè)算法，額外空間為n，額外空間復(fù)雜度為O(n)；
第二個(gè)算法，額外空間為0，額外空間復(fù)雜度為O(1)；
似乎沒見過(guò)有O(0)這種寫法。
可以看到，使用額外空間復(fù)雜度能夠很輕易地判斷兩個(gè)算法的好壞（從空間占用的角度）。
所以，是時(shí)候糾正錯(cuò)誤的概念了，以后與人交流的時(shí)候請(qǐng)使用“額外空間復(fù)雜度”這個(gè)概念。
時(shí)間與空間的權(quán)衡時(shí)間與空間往往是一組糾纏在一起的概念，就像很多小說(shuō)中寫的一樣，主角最終領(lǐng)悟了時(shí)空法則，成為了最強(qiáng)者，小說(shuō)結(jié)束。
在數(shù)據(jù)結(jié)構(gòu)與算法中也是一樣，時(shí)間與空間往往同時(shí)出現(xiàn)，而且經(jīng)常朝著相反的方向運(yùn)動(dòng)。
比如，對(duì)于排序算法：
冒泡排序，時(shí)間復(fù)雜度O(n^2)，空間復(fù)雜度O(1)
歸并排序，時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(n)
所以，有兩種思想：以時(shí)間換空間，以空間換時(shí)間。
那么，哪種算法更好呢？
我認(rèn)為，如果有時(shí)間、空間同時(shí)比較小的為最好，退而求其次，我選擇以空間換時(shí)間，畢竟，隨著計(jì)算機(jī)硬件技術(shù)地不斷發(fā)展，空間越來(lái)越不值錢，而時(shí)間卻越來(lái)越值錢，所以，以空間換時(shí)間也是一種常用的思想，在我們后續(xù)的課程中會(huì)出現(xiàn)大量以空間換時(shí)間的案例。
后記想知道冒泡排序和歸并排序算法的復(fù)雜度如何計(jì)算嗎？來(lái)呀，關(guān)注我吧。
本節(jié)，我們從一個(gè)小例子入手，分析了兩種算法的空間復(fù)雜度，并引出空間復(fù)雜度的真身——額外空間復(fù)雜度，最后，通過(guò)對(duì)比冒泡排序和歸并排序的時(shí)間復(fù)雜度和空間復(fù)雜度，得出了以空間換時(shí)間的思想。
到這里，關(guān)于復(fù)雜度相關(guān)的章節(jié)就寫完了，從下一節(jié)開始，我們將進(jìn)入常用數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)中，敬請(qǐng)期待。
P.S. 下周將進(jìn)行晉升答辯，會(huì)停更幾天，敬請(qǐng)諒解。