基本复杂度混淆

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个数组不会改变空间复杂度。