空間複雜度分析

習題預習

1. 什麼是空間複雜度分析？
2. 如何計算算法的空間複雜度？
3. 空間複雜度分析為什麼很重要？
4. 什麼是常數空間複雜度？
5. 如何減少算法的空間複雜度？

說明知識

Space Complexity Analysis是指對於一個算法，在執行過程中所需要使用的記憶體空間的分析。這是一個重要的術語，因為計算機中的記憶體容量是有限的，如果算法的記憶體空間過多，就可能會導致計算機崩潰或程序出錯。

舉例來說，假設我們要寫一個算法來對一個包含n個元素的陣列進行選擇排序。這個算法的時間複雜度是O(n^2)，但在空間複雜度上，我們需要使用一個暫存的變量temp來交換元素的位置，以及一個指針i來執行循環。所以，這個算法的空間複雜度是O(1)，即不會隨著問題規模n的增加而增加。

舉另一個例子，假設我們要寫一個算法來計算一個n x n的矩陣的轉置矩陣。這個算法需要先創建一個新的n x n的矩陣，再進行迭代計算。因此，這個算法的空間複雜度是O(n^2)，即當問題規模n增加時，空間複雜度會隨之增加。

總之，空間複雜度是分析一個算法的重要方面，因為它可以幫助我們確定該算法在實際應用時所需的系統資源，以及在大規模數據上的運算效能。

彙總重點

1. 空間複雜度是什麼：空間複雜度是指算法在解決問題時所需要的額外空間大小。

2. 額外空間：額外空間是指在算法執行期間，除了輸入本身所佔用的空間之外，需要額外申請的空間大小。

3. 判斷額外空間大小：需要計算數據結構所佔空間大小、遞歸調用所佔空間大小以及程序需要的臨時變量所佔空間大小。

4. O(1)的空間複雜度：一些算法運行的期間額外使用的空間是不變的，空間複雜度為O(1)。

5. 常見的O(n)的空間複雜度的算法：快速排序、歸並排序、堆排序等需要額外申請數組的排序算法，以及圖論中的廣度優先搜索和深度優先搜索算法。

6. 如何減少空間複雜度：可以採用 in-place 操作，在原來的數據結構上進行修改，避免額外申請空間，或者使用空間佔用更小的數據結構來代替原先的數據結構。

7. 空間複雜度的重要性：在實際開發中，空間複雜度與時間複雜度同樣重要，因為低空間複雜度可以減少內存的佔用，提高程序的運行效率，降低開發成本。

知識測驗

1. 給定一個大小為n的整數數組，複製它的內容並佔用O(n)的額外空間。在此情況下，輸入數組的空間複雜度是多少？
   答: O(n)

2. 評估一個n x n的方陣的空間複雜度，如果每個元素是一個布爾值。
   答: O(n^2)

3. 找出一個排序好的數列中的唯一元素並返回它。可以使用O(1)的額外空間，但不能更改原始數組。
   答: O(1)

4. 有一個m x n的矩陣，它的每個元素只能是0或1。找到最大全為1的正方形的邊長。請評估此算法的空間複雜度。
   答: O(n^2)

5. 給定一個大小為n的整數數組，求解數組中唯一的重複元素。可以使用O(1)的額外空間，但不能更改原始數組。
   答: O(1)