Python矩阵原地转置算法的时间与空间复杂度咨询

嘿，先提个小细节：你说这是“原地转置”，但实际代码里用了deepcopy(matrix)创建了原矩阵的完整副本，所以这其实不是真正的原地算法哦——原地算法的核心是直接在原矩阵上修改，不会额外创建和原矩阵同规模的副本。不过咱们还是来仔细分析这个版本的复杂度：

时间复杂度 #

假设原矩阵是m行n列的（总共有m*n个元素）：

• deepcopy(matrix)：深拷贝整个矩阵需要遍历所有元素，时间开销是O(m*n)。
• 生成new的列表推导式：外层循环跑n次（对应原矩阵的列数），每次要遍历m行取出对应位置的元素，这部分同样是O(m*n)的时间。
• 后续的matrix.append(new)循环：这里你不小心每次append的是整个new列表（应该是matrix.append(i)吧？），但不管怎样，这部分的时间开销和前面的O(m*n)比起来可以忽略不计。

总的来说，整个函数的时间复杂度是O(m*n)，所有核心操作的时间都和矩阵元素总数成线性关系。

空间复杂度 #

• reference是原矩阵的深拷贝，占用了O(m*n)的空间。
• new列表存储了转置后的完整矩阵，同样占用O(m*n)的空间。
• 虽然你用matrix.clear()清空了原矩阵，但额外创建的这两个同规模矩阵是主要的空间开销。

所以这个版本的空间复杂度是O(m*n)。

如果想要实现真正的原地转置（通常只适用于方阵，也就是m=n的情况），可以通过交换矩阵中(i,j)和(j,i)位置的元素来实现，那样空间复杂度就能降到O(1)啦。

内容的提问来源于stack exchange，提问作者Prashin Jeevaganth