Какова временная сложность операции move_to_end для OrderedDict в Python 3?

Question

Я нашел исходный код , и похоже, что это O (1), так как это в основном обновление связанного списка и dict.Хотя я не уверен.

Что ты думаешь?Спасибо!

Answer 1

Вы можете проверить чистую реализацию Python OrderedDict.move_to_end(), что эквивалентно реализации C:

def move_to_end(self, key, last=True):
    '''Move an existing element to the end (or beginning if last is false).
    Raise KeyError if the element does not exist.
    '''
    link = self.__map[key]
    link_prev = link.prev
    link_next = link.next
    soft_link = link_next.prev
    link_prev.next = link_next
    link_next.prev = link_prev
    root = self.__root
    if last:
        last = root.prev
        link.prev = last
        link.next = root
        root.prev = soft_link
        last.next = link
    else:
        first = root.next
        link.prev = root
        link.next = first
        first.prev = soft_link
        root.next = link

По сути, этот метод ищет ссылку в связанном спискев словаре self.__map и обновляет предыдущий и следующий указатели для ссылки и ее соседей.
Поскольку все вышеперечисленные операции занимают постоянное время, сложность OrderedDict.move_to_end() также постоянна.