这个 n x n 转置算法会被认为是就地算法吗？
Would this n x n transpose algorithm be considered an in place algorithm?
根据我的研究，我获得了关于这个简单算法的相互矛盾的信息。该算法是一个基本的矩阵转置，它转置一个 n x n 矩阵 A.
我目前的理解是该算法将 运行 在 O(n^2) 时间并且具有 space 复杂度 O(1) 因为我们操作的矩阵与我们操作的矩阵相同处理.
但是-我也被告知它实际上会 运行 O(n) 时间并且也有 space O(n) 的复杂度。这意味着它不会就地，因为它需要额外的 space 进行操作。
对于下面的转置算法，哪个思维过程是正确的？
Transpose(A)
1. for i = 1 to n -1
2. for j = i + 1 to n
3. exchange A[i, j] with A[j,i]
由于工作量与数组中元素的数量成正比，而这些元素占据了它们自己的 space，因此可能会引起一些混淆。因此，通过一些符号滥用或疏忽，两者都会被称为“O(n)”。
但这是错误的，因为
n显然不是元素个数而是数组的rows/columns个数；
根据定义，space 复杂性不包括输入和输出数据，但需要任何辅助 space。
因此我们可以确认时间复杂度 O(n²) - 实际上是 Θ(n²) - 和 space 复杂度 O(1)。算法是in-place.
最后备注：
如果我们将元素个数记为m，时间复杂度为O(m)，不矛盾
根据我的研究，我获得了关于这个简单算法的相互矛盾的信息。该算法是一个基本的矩阵转置，它转置一个 n x n 矩阵 A.
我目前的理解是该算法将 运行 在 O(n^2) 时间并且具有 space 复杂度 O(1) 因为我们操作的矩阵与我们操作的矩阵相同处理.
但是-我也被告知它实际上会 运行 O(n) 时间并且也有 space O(n) 的复杂度。这意味着它不会就地，因为它需要额外的 space 进行操作。
对于下面的转置算法，哪个思维过程是正确的？
Transpose(A)
1. for i = 1 to n -1
2. for j = i + 1 to n
3. exchange A[i, j] with A[j,i]
由于工作量与数组中元素的数量成正比，而这些元素占据了它们自己的 space，因此可能会引起一些混淆。因此，通过一些符号滥用或疏忽，两者都会被称为“O(n)”。
但这是错误的，因为
n显然不是元素个数而是数组的rows/columns个数；
根据定义，space 复杂性不包括输入和输出数据，但需要任何辅助 space。
因此我们可以确认时间复杂度 O(n²) - 实际上是 Θ(n²) - 和 space 复杂度 O(1)。算法是in-place.
最后备注：
如果我们将元素个数记为m，时间复杂度为O(m)，不矛盾