Как перебрать матрицу без двух циклов for

Question

У меня есть упражнение, которое требует итерации по элементам матрицы 'm', сложность в том, что время выполнения должно быть линейным, что означает, что если я использую циклы, то допускается только один.

Моя проблема сейчас в том, что я всегда хочу использовать 2 forloops, но время выполнения не будет линейным, оно будет квадратичным. Я думал о том, чтобы просто выполнить итерацию по m [i], а затем проверить, являются ли они только Int 0, но это снова будет 2 forloops или, возможно, посмотреть, смогу ли я присоединиться к элементам. К сожалению, я не смог найти ничего полезного уже. Я также подумал об использовании аргумента «x в списке», но это также не помогло бы.

Спасибо заранее.

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

Вы можете перебирать матрицу, используя такой код:

m = [[0,0,0],
     [1,0,1],
     [1,0,0]]
r = 3
c = 3
for j in range(r*c):
    print ( "m[", j // c,"][",j % c,"] = ", m[j // c][ j % c] )

Дает:

m[ 0 ][ 0 ] =  0
m[ 0 ][ 1 ] =  0
m[ 0 ][ 2 ] =  0
m[ 1 ][ 0 ] =  1
m[ 1 ][ 1 ] =  0
m[ 1 ][ 2 ] =  1
m[ 2 ][ 0 ] =  1
m[ 2 ][ 1 ] =  0
m[ 2 ][ 2 ] =  0

Чтобы было яснее, что происходит, я использовал r дляколичество строк и c для количества столбцов.Он использует оператор целочисленного деления // и % оператор модуля для получения нормальных индексов, доступных из вложенных циклов for.

Answer 2

Я хотел бы иметь в виду, что анализ времени выполнения основан на размере входных данных.То есть, если ваши входные данные состоят из n элементов, и вы повторяете каждый элемент ровно один раз, это O(n).Если ваша матрица имеет размер n x m, то я считаю, что линейность будет определяться как O(n x m), то есть линейная по размеру ввода.

Кроме того, наличие вложенного цикла for не обязательно означает, чтовремя выполнения программы является квадратичным, хотя это может быть полезным способом думать о времени выполнения.

РЕДАКТИРОВАТЬ: Это не меняет теоретическое время выполнения, но вы можете взглянуть на векторизованные встроенные функции (например, sumв Python) обрабатывать каждую строку в целом.Как я уже сказал, это не меняет алгоритмическое время выполнения, но внутренняя оптимизация и векторизация могут ускорить простую итерацию по каждому элементу матрицы.

В качестве уточнения к "двум циклам 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