旋转矩阵的 Python 程序。为什么我的程序花费了这么多时间？

Question

我用 Python 2.7 编写了这个程序，它在某些测试用例中显示运行时错误，并且在某些测试用例中花费了 10 秒以上。我是编码新手，不明白为什么要花这么多时间。

该程序用于逆时针旋转矩阵的元素。

Input
4 4 1

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Output
2 3 4 8 
1 7 11 12 
5 6 10 16 
9 13 14 15 

第一个输入是行数(M)、列数(N)、旋转数(R)。 然后逐行输入矩阵的元素。输出显示旋转。 M 和 N 中较小的一个总是偶数。

这是我的程序:

def printAsNeeded(matrix):
    length = len(matrix)
    n = len(matrix[0])
    for i in range(length):
        a = str()
        for j in range(n):
            a = a+str(matrix[i][j])+' '
        print a

def rotate(matrix):
    count = 0
    M = len(matrix)
    N = len(matrix[0])
    rmatrix = []
    for i in range(M):
        rmatrix.append([])
        for j in range(N):
            rmatrix[i].append(0)
    if(M<N):
       mag = M/2
    else:
       mag = N/2
    #down: 
    for i in range(mag):
        for j in range(count, M - (count+1)):
            rmatrix[j+1][i] = matrix[j][i]
        count = count+1
    count = 0
    #up
    for i in range(N-1, mag-1, -1):
        for j in range(count, M - (count+1)):
            rmatrix[j][i] = matrix[j+1][i]
        count = count+1
    count = 0
    #right
    for i in range(M-1, mag-1, -1):
        for j in range(count, N - (count+1)):
            rmatrix[i][j+1] = matrix[i][j]
        count = count+1
    count = 0
    #left
    for i in range(mag):
        for j in range(count, N - (count+1)):
            rmatrix[i][j] = matrix[i][j+1]
        count = count+1
    count = 0


    return rmatrix


M, N, R = raw_input().split()
M = int(M) #No of rows
N = int(N) #No of columns
R = int (R) #No of rotations
omatrix = []

for i in range(M):
    omatrix.append([])
    data = raw_input().split()
    for j in range(len(data)):
        omatrix[i].append(int(data[j]))

def matrixRotation(matrix, n):
    for i in range(n):
        matrix = rotate(matrix)
    printAsNeeded(matrix)

matrixRotation(omatrix, R)

Answer 1

对于方阵，你的算法有 O(M * M * R) complexity 。很容易看出:

def matrixRotation(matrix, n):
    for i in range(n):
        matrix = rotate(matrix)  # number of cycles = R

def rotate(matrix):
    mag = M/2
    count = 0
    for i in range(mag):  # number of cycles ~ M
        for j in range(count, M - (count+1)):  # number of cycles ~ M
            rmatrix[j+1][i] = matrix[j][i]
        count = count+1

因此，总步数增长得非常快，对于 100 次旋转的 1000x1000 矩阵，您将必须执行约 100M 步。

发明更好的算法超出了这个问题的范围(在现实生活中，无论如何你都会使用 NumPy)。但我看到的一个明显的初学者错误是您使用 range而不是xrange 。在这种情况下，效率非常低，因为您每次都会创建一个临时列表。