基本複雜度混淆

Question

我有一個算法，它採用二維數組並且不使用額外的空間。因此，算法O（n^2）（因爲我正在處理整個輸入數組）或O（1）（因爲該算法不使用除輸入之外的任何額外空間）的空間複雜度，所以是空間複雜度

特別是在這個問題http://www.careercup.com/question?id=4959773472587776中，如果我們正確使用2個額外的1維數組，那麼無關緊要，因爲無論如何，輸入空間複雜度爲O（n^2）。
謝謝！

Answer 1

輔助空間複雜度不包含輸入空間，而空間複雜度爲。

對於輔助空間複雜度分析，只考慮額外的內存消耗。如果你的算法沒有使用任何額外的空間，那麼輔助空間的複雜度就是O（1）。

如果輸入具有大小m（= N×N的），並使用2個陣列大小n的，則輔助空間複雜性將是O(n)（或O(logm)）。

對於空間複雜度，由於您計算輸入大小，您是對的，使用2個數組不會改變空間複雜度。