輔助複雜的排序修飾

Question

根據geekforgeeks：

Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criteria than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.

但是，假設一個場景，一個修改歸併排序，在那裏是return一個全新的有序數組保持輸入陣列不變。

new sorted array which is returned會被視爲temporary space？ 換句話說，輔助複雜性still是O（n）和空間是O（n）？

Answer 1

我從來沒有聽說過輔助空間複雜性這個詞。但是空間複雜度的正則概念將輸入和輸出空間分開，並且算法的空間複雜度是任何額外的空間，對於其他一些更加限制性的模型來衡量空間複雜度，甚至無法在輸入空間中進行寫入是隻讀的，輸出只能寫入一次，但從理論的角度來看，這些只是有趣的。

所以我猜輸出空間不應該被視爲輔助空間的一部分，我的意思是說你需要這個空間，沒有辦法你可以避免它，這就是爲什麼在某些分析中運行時間也使用輸出尺寸作爲參數。

所以是的，您用於輸出的空間可能不會被視爲額外的空間，不過，在mergesort的情況下，您無法避免這個O（n）額外的空間，因爲您沒有觸摸輸入，所以你需要另一個輔助數組來完成合並步驟。