numpy.transpose的时间复杂度

Question

np.transpose的时间复杂度是多少？

在我看来，它在内部循环了两个for循环，这意味着它应该具有O（n2）复杂度，但有人可以对此进行确认吗？另外，有什么办法可以减少矩阵转置的时间复杂度

Answer 1

在内存中，矩阵表示为连续内存块，就好像它是一个一维数组。N 维是我们人类用来使问题更易于理解的抽象。对于numpy，转置矩阵只是一个轴的变化，但内存并没有改变。

所以时间复杂度是O(1)因为要转置数组，numpy 只是交换每个轴的形状和步幅信息。

无需复制数据即可实现此目的。Numpy 可以简单地改变它对底层内存的看法来构造新数组。

如果你想加深这个话题，你可以看到这个带有插图的漂亮答案

Answer 2

它是O（1），因为它根本不复制数据。只需修改形状并大步前进。

>>> A = np.random.rand(3,4)
>>> A.flags
  C_CONTIGUOUS : True
  F_CONTIGUOUS : False
  OWNDATA : True
  WRITEABLE : True
  ALIGNED : True
  WRITEBACKIFCOPY : False
  UPDATEIFCOPY : False
>>> np.transpose(A).flags
  C_CONTIGUOUS : False
  F_CONTIGUOUS : True
  OWNDATA : False
  WRITEABLE : True
  ALIGNED : True
  WRITEBACKIFCOPY : False
  UPDATEIFCOPY : False

请注意C_CONTIGUOUS，F_CONTIGUOUS已交换，（即主要的迭代顺序更改），并且转置的数组具有OWNDATAfalse（即，它只是原始数组数据的视图）。

相关技巧：当您具有这样的视图时，要查找拥有数据的数组，您可以检查base属性

>>> np.transpose(A).base is A
True