Алгоритм для изменения элементов списка на месте?

Я изучаю структуру данных и эффективность алгоритмов в моем классе CS прямо сейчас, и я создал алгоритм для возврата нового списка элементов, которые в обратном порядке из исходного списка. Я пытаюсь понять, как это сделать с помощью списков Python, используя рекурсию, но решение ускользает от меня. Вот мой код:Алгоритм для изменения элементов списка на месте?

def reverse_list(in_list): 
    n = len(in_list) 
    print('List is: ', in_list) 
    if n <= 2: 
     in_list[0], in_list[-1] = in_list[-1], in_list[0] 
     return in_list 
    else: 
     first = [in_list[0]] 
     last = [in_list[-1]] 
     temp = reverse_list(in_list[1:-1]) 
     in_list = last + temp + first 
     print('Now list is: ', in_list) 
     return in_list 

if __name__ == '__main__': 
    list1 = list(range(1, 12)) 
    list2 = reverse_list(list1) 
    print(list2)

Как примечание стороны, это O (п) в среднем случае из-за его п/2 верно?

источник

2015-12-18 flybonzai

'in_list [1: -1]' находится в O (N), поэтому алгоритм находится в O (N²). Термин «средний случай» не применяется, здесь нет лучшего и худшего случая. – kay

Не могли бы вы немного объяснить, чтобы помочь мне разобраться? Спасибо :) – flybonzai

Ну, вы делаете операции N/2 = O (N), каждая из которых стоит O (N). O (N) * O (N) = O (N^2). Btw. Мне нравится идея вашего алгоритма. Единственная проблема заключается в том, что нарезка в Python создает копию, а Python не является хвостом рекурсивным. Можно сказать, что это недостаток Python, а не ваш алгоритм. – kay

Ваш n <= 2 кейс хорош. Это «на месте» в обоих обычных чувствах. Он изменяет тот же список, который передается, и использует только постоянный объем памяти в дополнение к перечню, переданному.

В общем случае у вас есть проблемы. Он использует много дополнительной памяти (n/2 уровня рекурсии, каждая из которых содержит два списка по рекурсивному вызову, поэтому все эти списки на всех уровнях должны существовать сразу), и он не изменяет список, переданный в (скорее, он возвращает новый список).

Я не хочу делать слишком много для вас, но ключ к решению этого - передать один (или два, если хотите) дополнительный параметр (ы) на рекурсивный шаг. Или необязательный параметр для вашей функции, либо определить рекурсивную вспомогательную функцию, которая их имеет. Используйте это, чтобы указать какой регион списка, чтобы обратить вспять на место.

Как упоминалось в комментариях, CPython не имеет оптимизации хвостовой рекурсии. Это означает, что ни один алгоритм, который использует call-recursion, подобный этому, никогда не будет действительно «на месте», поскольку он будет использовать линейные суммы стека. Но «на месте» в смысле «изменяет исходный список, а не возвращает новый», безусловно, выполнимо.

источник

2015-12-18 00:28:49

Я думал об этом, создаю first_index и last_index, которые будут перемещаться каждый раз, чтобы я мог сохранить один и тот же список. Это более или менее трек, о котором вы говорите? – flybonzai

@flybonzai: это тот! В этих упражнениях «использование рекурсии» обычно означает «найти способ взять экземпляр проблемы и превратить его в несколько меньший экземпляр той же проблемы». –

Вы действительно не хотите использовать рекурсию здесь, как это на самом деле не упрощать проблему для дополнительных издержек, связанных с вызовами функций:

list3 = list(range(1, 10)) 
for i in range(len(list3)/2): 
    list3[i], list3[len(list3)-i-1] = list3[len(list3)-i-1], list3[i] 
print(list3)

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

источник

2015-12-18 00:30:14 MasterOdin

Это гладкая реализация, спасибо! – flybonzai

Алгоритм для изменения элементов списка на месте?

ответ

Смежные вопросы