Пространственно-временная сложность matrix_in_spiral_order (matrix) - PullRequest
Новая
       17

Пространственно-временная сложность matrix_in_spiral_order (matrix)

1 голос
/ 24 мая 2019

Я читаю интервью по элементам программирования на Python (Азиз, Ли, Пракаш) и не понимаю сложности пространства и времени для одного из их алгоритмов.Вопрос, заданный для возврата матрицы в спиральном порядке (пример здесь ).

В конце алгоритма авторы утверждают, что это O (n ^ 2) временная сложность, иO (1) Пространственная сложность.Прошло несколько лет с тех пор, как я формально изучал сложность, поэтому я не понимаю ни одного из этих утверждений.В приведенном ниже коде мы создаем новый массив со всеми элементами в спиральном порядке, что позволило бы мне полагать, что это не операция на месте, и, следовательно, сложность пространства O (nxn).

За сложность времени я тоже растерялся.Мы перебираем 2D-массив только один раз для каждого элемента.Не будет ли поэтому считаться O (n)?Чем это отличается от простого объединения этого в одномерный массив и его однократного прохождения? 

def matrix_in_spiral_order(square_matrix):
    SHIFT = ((0,1),(1,0),(0,-1),(-1,0))
    direction = x = y = 0
    spiral_ordering = []

    for _ in range(len(square_matrix)**2):
        spiral_ordering.append(square_matrix[x][y])
        square_matrix[x][y] = 0
        next_x,next_y = x + SHIFT[direction][0], y+ SHIFT[direction][1]
        if (next_x not in range(len(square_matrix)) or next_y not in range(
              len(square_matrix)) or square_matrix[next_x][next_y] == 0):
            direction = (direction +1) & 3
            next_x, next_y = x+ SHIFT[direction][0], y + SHIFT[direction][1]
        x,y = next_x, next_y
    return spiral_ordering

Я решил решить эту проблему рекурсивно, используя другое решение, но все еще хочу понять, как они пришли к своему анализувышеуказанный алгоритм.

1 Ответ

1 голос
/ 24 мая 2019

Похоже, что их определение N - это длина стороны матрицы, а ваше определение N - произведение сторон матрицы.Это похоже на шесть из одного, полдюжины другого, хотя открыто для дебатов относительно того, что является менее вводящим в заблуждение.

Что касается сложности пространства, еще раз, похоже, что их интерпретация заключается в том, что возвращаемый результатне считаетсяЭто достаточно справедливо, но это нужно сделать явным, и я думаю, что ваша интуиция в том, что она выражает сомнения по поводу обоих их утверждений, является разумной.

В качестве примечания, я согласен с @Blorgbeard, чтоАлгоритм, который они предоставили, не является образцовым.

...