O (n) сложность понимания списка Python с функцией zip ()

Question

В настоящее время я работаю над учебником со следующим кодом:

# numpy where
A = np.array([1,2,3,4])
B = np.array([100, 200, 300, 400])
condition = np.array([True, True, False, False])

answer = [(A_val if cond else B_val) for A_val, B_val, cond in zip(A, B, condition)]

answer
# Out: [1, 2, 300, 400]

Вопрос: Какова может быть сложность этого питона этой конструкции, смесь понимания списка и почтового индекса() function?

Каждая переменная, переданная в zip (), действует как еще один цикл for?а как насчет самого понимания списка?

Спасибо за вашу помощь!

Answer 1

Время работы zip(*args) равно O(len(args) * min(len(a) for a in args).Вы не можете обязательно сводить это к O(n) без конкретных предположений об аргументах (например, что число списков (len(args)) является постоянным).

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

Но если вы не можете сделать эти конкретные предположения, подумайте оэто как O(n) может ввести вас в заблуждение.

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

Answer 2

Вы перебираете списки A, B, condition после добавления элемента в answer с каждым предпринятым шагом, поэтому сложность составляет O(n), где n - это размер кратчайшегоlist

Является ли каждая переменная, переданная в zip (), как другой цикл for?

Думайте об этом как об одном цикле, добавив еще 1 аргумент к zipдобавьте O(1) в каждой итерации или O(n) для всех n итераций.(при условии, что наименьший аргумент имеет размер n)
Например, для zip(X1,X2,...,Xm) вы выполняете O(mn) работу, но m является константой, поэтому O(n).(опять же, предполагая, что наименьший размер аргументов равен n)