額外空間演算法

① 演算法的空間復雜度指的是什麼

空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n^2),空間復雜度是O(1) 。

而一般的遞歸演算法就要有O(n)的空間復雜度了，因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要佔用的存儲空間兩個方面衡量。

類似於 時間復雜度的討論，一個演算法的空間復雜度S(n)定義為該演算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。空間復雜度(SpaceComplexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。

一個演算法在計算機存儲器上所佔用的存儲空間，包括存儲演算法本身所佔用的存儲空間，演算法的輸入輸出數據所佔用的存儲空間和演算法在運行過程中臨時佔用的存儲空間這三個方面。演算法的輸入輸出數據所佔用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本演算法的不同而改變。

(1)額外空間演算法擴展閱讀：

分析

分析一個演算法所佔用的存儲空間要從各方面綜合考慮。如對於遞歸演算法來說，一般都比較簡短，演算法本身所佔用的存儲空間較少，但運行時需要一個附加堆棧，從而佔用較多的臨時工作單元；

若寫成非遞歸演算法，一般可能比較長，演算法本身佔用的存儲空間較多，但運行時將可能需要較少的存儲單元。

一個演算法的空間復雜度只考慮在運行過程中為局部變數分配的存儲空間的大小，它包括為參數表中形參變數分配的存儲空間和為在函數體中定義的局部變數分配的存儲空間兩個部分。

若一個演算法為遞歸演算法，其空間復雜度為遞歸所使用的堆棧空間的大小，它等於一次調用所分配的臨時存儲空間的大小乘以被調用的次數(即為遞歸調用的次數加1，這個1表示開始進行的一次非遞歸調用)。

② 想問您一些排序演算法的偽代碼，謝啦

冒泡排序：網頁鏈派皮接

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序演算法，就是如何使得記錄按照要求排列的方法。排序演算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的演算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規范，要得到一個符合實際的優秀演算法，得經過大量的推理和分析。

C++自帶的algorithm庫函數中提供了排序演算法。

穩定的

冒泡排序（bubble sort） — O(n^2）

雞尾酒排序(Cocktail sort，雙向的冒泡排序) — O(n^2）

插掘羨友入排序（insertion sort）— O(n^2)

桶排序（bucket sort）— O(n); 需要 O(k) 額外空間

計數排序(counting sort) — O(n+k); 需要 O(n+k) 額外空間

合並排序（merge sort）— O(nlogn); 需要 O(n) 額外空間

原地合並排序— O(n^2)

二叉排序樹排序 （Binary tree sort） — O(nlogn)期望判槐時間； O(n^2)最壞時間； 需要 O(n) 額外空間

鴿巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間

基數排序（radix sort）— O(n·k); 需要 O(n) 額外空間

Gnome 排序— O(n^2)

圖書館排序— O(nlogn) with high probability，需要 （1+ε)n額外空間

不穩定的

選擇排序（selection sort）— O(n^2)

希爾排序（shell sort）— O(nlogn) 如果使用最佳的現在版本

組合排序— O(nlogn)

堆排序（heapsort）— O(nlogn)

平滑排序— O(nlogn)

快速排序（quicksort）— O(nlogn) 期望時間，O(n^2) 最壞情況； 對於大的、亂數列表一般相信是最快的已知排序

Introsort— O(nlogn)

耐心排序— O(nlogn+k) 最壞情況時間，需要 額外的 O(n+k) 空間，也需要找到最長的遞增子串列（longest increasing subsequence）

不實用的

Bogo排序— O(n×n!) 期望時間，無窮的最壞情況。

Stupid sort— O(n^3); 遞歸版本需要 O(n^2) 額外存儲器

珠排序（Bead sort） — O(n) or O（√n)，但需要特別的硬體

Pancake sorting— O(n)，但需要特別的硬體

stooge sort——O（n^2.7）很漂亮但是很耗時