关于时间复杂度O(n）问题

Question

有不利用额外矩阵空间，达到逆时针旋转矩阵的时间复杂度为O(n）的办法吗

Answer 1

你可以考虑使用行向量或列向量来表示二维旋转矩阵。具体来说，你可以使用一个长度为2的向量来表示二维平面上的一点，然后通过乘以旋转矩阵来旋转这个向量。

例如，假设你有一个长度为n的向量v，你可以按照以下步骤将其逆时针旋转θ角度：

1. 创建一个长度为2的临时向量temp，temp[0]初始化为v[0]，temp[1]初始化为v[1]。
2. 对于i从2到n-1，将temp乘以旋转矩阵，并将结果存储回temp。即，temp = temp * 旋转矩阵。
3. 将temp的前两个元素存储回v，即v[0] = temp[0]，v[1] = temp[1]。

这个算法的时间复杂度是O(n)，因为你需要遍历长度为n的向量一次。同时，这个算法不需要使用额外的矩阵空间，因为它只使用了临时向量temp和一个长度为2的向量来表示旋转矩阵。