时间戳

首页 > 解决方案 > 有人能告诉我解决这个 zigag 遍历问题的时间复杂度吗

python - 有人能告诉我解决这个 zigag 遍历问题的时间复杂度吗

问题描述

之字形遍历

这是来自算法专家的问题之一，这是我涉及数学的解决方案

def zigzagTraversal(arr):
out = []
test = 1
out.append(arr[0][0])
while test <= len(arr)+len(arr[0]):
    for j in range(len(arr[0])):
        for i in range(len(arr)):
            if test % 2 == 1:
                if i + j == test:
                    # print(arr[i][j])
                    out.append(arr[i][j])
            else:
                if i + j == test:
                    out.append(arr[j][i])
    test += 1
return out
print(zigzagTraversal([[1, 3, 4, 10],
                   [2, 5, 9, 11],
                   [6, 8, 12, 15],
                   [7, 13, 14, 16]]))

标签： pythonarraystimetime-complexityzigzag

解决方案

让N=len(arr), M=len(arr[0]). 此代码具有O(NM^2+N^2M)复杂性（或O(N^3)对于方形输入矩阵）。原因如下：外层循环 ( while) 完全等价于循环（因为您在末尾for递增并且永远不会在其他地方更改它）并且将被执行多次。然后您进入第二个循环，该循环恰好执行了几次。然后是内循环 -次。中间循环的每一步都会重复内部循环，与外部循环相同。所以我们必须将所有这些计数相乘。当然，所有内部操作都不是原子的，但对于小数据来说，平均而言。如果您的输入很大，我建议预先分配（将其创建为）以避免其增长成本并将当前的第一个免费索引保留为附加变量。testN+MNMO(1)outout = [None for _ in range(N*M)]

推荐阅读