Временная сложность спирального обхода двумерной матрицы?

Question

Я учусь обходить двумерную матрицу по спирали, и я наткнулся на следующий алгоритм:

def spiralOrder(self, matrix):

    result = []

    while matrix:
        result.extend(matrix.pop(0))
        matrix = zip(*matrix)[::-1]

    return result

В настоящее время мне сложно разобраться во временной сложности этого вопроса с помощью функции zipбыть в то время как цикл.

Буду очень признателен, если кто-нибудь поможет мне разобраться в сложности времени с объяснениями.

Спасибо!

Answer 1

Независимо от того, как вы проходите 2D-матрицу, временная сложность всегда будет квадратичной с точки зрения размеров.

Матрица m × n, следовательно, занимает O (mn) время прохождения независимо от того, является ли она спиральной или мажорной.

Answer 2

Известной временной сложностью для этой задачи является постоянная O (MxN), где M - количество строк, а N - количество столбцов в матрице MxN.Это потрясающий алгоритм, но похоже, что он может быть медленнее.

При более тщательном рассмотрении каждой итерации цикла выполняются следующие операции:

pop() # O(1)
extend() # O(k) where k is the number of elements added that operation
*matrix # O(1) -> python optimizes unpacking for native lists
list(zip()) # O(j) -> python 2.7 constructs the list automatically and python 3 requires the list construction to run
[::-1] # O(j/2) -> reverse sort divided by two because zip halved the items

Независимо от того, сколько итераций цикла будет выполнено, к тому времени, когда эта операция завершится, вы получитенаименее называемый result.extend для каждого элемента (MxN элементов) в матрице.Так что лучший случай - это O (MxN).

Где я менее уверен, сколько времени добавляются повторяющиеся почтовые индексы и обращения к спискам.Цикл вызывается только примерно M + N-1 раз, но zip / reverse выполняется для (M-1) * N элементов, а затем для (M-1) * (N-1) элементов и так далее.Мое лучшее предположение состоит в том, что этот тип функции является по крайней мере логарифмическим, поэтому я предполагаю, что общая временная сложность где-то около O (MxN log (MxN)).

https://wiki.python.org/moin/TimeComplexity