空間複雜度
出自 MBA智库百科(https://wiki.mbalib.com/)
空間複雜度(Space Complexity)
目錄 |
空間複雜度是指對一個演算法在運行過程中臨時占用存儲空間大小的量度，用o()來表示。
記做S(n)=O(f(n))。比如直接插入排序的時間複雜度是O(n^2),空間複雜度是O(1) 。而一般的遞歸演算法就要有O(n)的空間複雜度了，因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要占用的存儲空間兩個方面衡量。
類似於時間複雜度的討論，一個演算法的空間複雜度(SpaceComplexity)S(n)定義為該演算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間複雜度也常常簡稱為空間複雜度。空間複雜度(SpaceComplexity)是對一個演算法在運行過程中臨時占用存儲空間大小的量度。一個演算法在電腦存儲器上所占用的存儲空間，包括存儲演算法本身所占用的存儲空間，演算法的輸入輸出數據所占用的存儲空間和演算法在運行過程中臨時占用的存儲空間這三個方面。演算法的輸入輸出數據所占用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本演算法的不同而改變。存儲演算法本身所占用的存儲空間與演算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的演算法。演算法在運行過程中臨時占用的存儲空間隨演算法的不同而異，有的演算法只需要占用少量的臨時工作單元，而且不隨問題規模的大小而改變，這種演算法是“就地\"進行的，是節省存儲的演算法。
分析一個演算法所占用的存儲空間要從各方面綜合考慮。如對於遞歸演算法來說，一般都比較簡短，演算法本身所占用的存儲空間較少，但運行時需要一個附加堆棧，從而占用較多的臨時工作單元；若寫成非遞歸演算法，一般可能比較長，演算法本身占用的存儲空間較多，但運行時將可能需要較少的存儲單元。一個演算法的空間複雜度只考慮在運行過程中為局部變數分配的存儲空間的大小，它包括為參數表中形參變數分配的存儲空間和為在函數體中定義的局部變數分配的存儲空間兩個部分。若一個演算法為遞歸演算法，其空間複雜度為遞歸所使用的堆棧空間的大小，它等於一次調用所分配的臨時存儲空間的大小乘以被調用的次數(即為遞歸調用的次數加1，這個1表示開始進行的一次非遞歸調用)。演算法的空間複雜度一般也以數量級的形式給出。如當一個演算法的空間複雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個演算法的空間複雜度與以2為底的n的對數成正比時，可表示為O(log2n)；當一個演算法的空間複雜度與n成線性比例關係時，可表示為O(n).若形參為數組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應實參變數的地址，以便由系統自動引用實參變數。
對於一個演算法，其時間複雜度和空間複雜度往往是相互影響的。當追求一個較好的時間複雜度時，可能會使空間複雜度的性能變差，即可能導致占用較多的存儲空間。
反之，當追求一個較好的空間複雜度時，可能會使時間複雜度的性能變差，即可能導致占用較長的運行時間。另外，演算法的所有性能之間都存在著或多或少的相互影響。因此，當設計一個演算法(特別是大型演算法)時，要綜合考慮演算法的各項性能，演算法的使用頻率，演算法處理的數據量的大小，演算法描述語言的特性，演算法運行的機器系統環境等各方面因素，才能夠設計出比較好的演算法。演算法的時間複雜度和空間複雜度合稱為演算法的複雜度。
