空間複雜度

空間複雜度是時間複雜度的記憶體孿生：當輸入變大時，演算法需要多少額外記憶體？就像我們為時間數步驟一樣，這裡我們數儲存——多少個單元、多深的待返回呼叫堆疊、多大的輔助陣列——把它寫成輸入規模 n 的函數，並用大 O 描述它的增長。時間告訴你能不能跑完；空間告訴你能不能裝得下。一個跑得快、卻要求比機器記憶體還多的程式，會乾脆崩掉，所以兩種代價都要緊。

我們通常指的是輔助空間：演算法在它拿到的輸入之外所用的額外記憶體。把一串數字求和，無論串列多長都只要一個累加值，所以是 O(1) 額外空間。合併排序在合併時會建臨時陣列，需要 O(n) 額外空間。遞迴演算法也悄悄占記憶體：每個未返回的呼叫都壓在呼叫堆疊上，所以一個深入 n 層的遞迴要花 O(n) 堆疊空間，深入 log n 層的則花 O(log n)——這是初學者常常忘掉的一筆真實開銷。

認得空間複雜度，會揭示出整個編程裡最常見的一種取捨：時間換空間。你常常可以靠「記住更多」來讓程式更快（一個雜湊表或一份記憶化快取，能把反覆的 O(n) 掃描變成 O(1) 查找，代價是記憶體），或者靠「重新算」來省記憶體（省下空間，花掉時間）。同時知道兩種複雜度，能讓你誠實地把你的演算法放到那條取捨線上，而不是日後才被它嚇一跳。