Вносит ли зацикливание в обратном порядке (список) сложность времени моей функции?

Question

Короткий, но простой вопрос. Я изучал сложность времени для интервью по кодированию, и я не могу найти краткий ответ на это. Я знаю, что этот вопрос существует на SO. Какова временная сложность изменения списка Python? .

В Python есть два метода циклического перемещения по спискам. Вы можете либо перебрать list.reverse (), который переворачивает список на месте во время сложности O (n), либо вы можете перебрать реверс (list). Мой вопрос: использование обратной (список) также сложность O (n) или нет?

Я могу представить два возможных ответа: либо он фактически переворачивает список (в этом случае я бы сказал: Да, он добавляет O (n)), либо он просто перебирает список с другой стороны (в этом случае я сказал бы, нет: это не). Кто-нибудь может дать мне однозначный ответ на это?

Answer 1

Встроенная reversed, как и многие другие в Python 3, возвращает итератор и, следовательно, не требует дополнительных n итераций. Когда речь идет о нотации big-O, это не имеет значения, но вы заинтересованы в этом факторе, поэтому нет,

for i in reversed(my_list): 

проходит список ровно один раз. Это как раз тот смысл вспомогательных функций этого типа.

Обратите внимание, что вы могли бы использовать

for i in my_list[::-1]:

, который является обычным способом итерации, но использование нарезки уже возвращает список - так же, как и my_list.reverse, дополнительно n.