python - 如何在没有 2 个 for 循环的情况下迭代矩阵

Question

我有一项练习，要求对矩阵“m”的元素进行迭代，困难在于运行时间应该是线性的，这意味着如果我使用 for 循环，则只允许使用一个。

我现在的问题是，我总是发现自己想要使用 2 个 for 循环，但运行时间不是线性的，而是二次的。我正在考虑迭代 m[i]，然后检查这些是否只是 Int 0，但这将再次是 2 个 for 循环，或者也许看看我是否可以加入这些元素。可悲的是，我已经找不到任何有用的东西了。我还考虑过使用“x in list”参数，但这也没有帮助。

提前致谢。

m = [[0,0,0],
     [1,0,1],
     [1,0,0]]


#for i in m
#check all elements in m[i] for Ints '0'    

#m[0] --> All Elements are the Integer 0
#--> Output: True.
#The output should be a Boolean 'True', when the elements of one m[i] are all Integers 0.

Answer 1

我会记住，运行时分析是基于输入的大小。也就是说，如果您的输入由 n 个元素组成，并且您对每个元素恰好迭代一次，则时间复杂度为 O(n)。如果您的矩阵大小为 n x m，那么我相信线性度将定义为 O(n x m)，即输入大小呈线性。

此外，嵌套 for 循环的存在并不一定意味着程序的运行时间是二次的，尽管这可能是考虑运行时间的有用方法。

编辑:这不会改变理论上的运行时间，但您可以查看矢量化内置函数(如 python 中的 sum)来完全处理每一行。正如我所说，这不会改变算法运行时，但底层优化和矢量化可以加快每个矩阵元素的简单迭代速度。

作为对“两个 for 循环总是意味着 O(n^2)”的阐述:这仅在以下情况下成立:

# n elements in the input
for i in range(n):
    for j in range(n):
        # do things

# another possibility
# n elements in the input
for i in range(n):
    for j in range(i):
        # worst case, i == j, bringing this to O(n^2)
        # do things