performance - 基本复杂性混淆

Question

我有一个算法，它接受一个二维数组并且不使用额外的空间。算法的空间复杂度也是 O(n^2) （因为我正在处理整个输入数组）或 O(1) （因为算法不使用除输入之外的任何额外空间）

特别是，在这个问题http://www.careercup.com/question?id=4959773472587776中，我们是否正确使用 2 个额外的一维数组并不重要，因为无论如何输入空间复杂度是 O(n^2) .
谢谢！

Answer 1

辅助空间复杂度不包括输入空间，而空间复杂度包括。

对于辅助空间复杂度分析，只考虑额外的内存消耗。如果您的算法不使用任何额外空间，则辅助空间复杂度为 O(1)。

如果输入的大小为m(= nxn)，并且您使用 2 个大小为 的数组n，则辅助空间复杂度将为O(n)(或O(logm))。

对于空间复杂度，由于您计算输入大小，您是对的，使用 2 个数组不会改变空间复杂度。