Существует ли алгоритм O (nlog (n)) для инвертирования просто связанного списка?

Question

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

Это определенно неправильно - инверсия O (n) не является проблемой - просто просмотрите список и меняйте указатели по мере продвижения. Требуются три временных указателя - это постоянная дополнительная память.

Я полностью понимаю, что O (nlog (n)) хуже (медленнее), чем O (n).

Но из любопытства - каким может быть алгоритм O (nlog (n)) для инвертирования просто связанного списка? Алгоритм с постоянной дополнительной памятью предпочтителен.

Answer 1

Я думаю, вы в замешательстве. Вы говорите, что O (n log (n)) на самом деле хуже, чем O (n). Возможно, вы имеете в виду O (log n)? Если так, ответ - нет. Вы не можете инвертировать связанный список в O (log n). O (n) тривиально (и очевидное решение). O (n log (n)) не имеет большого смысла.

Редактировать: Хорошо, значит, вы имеете в виду O (n log (n)). Тогда ответ - да. Как? Легко. Вы сортируете список:

1. Подсчитайте длину списка. Стоимость: O (n);
2. Создать массив того же размера;
3. Скопируйте элементы связанного списка в массив в порядке random , поместив исходный порядок как часть элемента. Например: [A, B, C] -> [(B, 2), (C, 3), (A, 1)]. Стоимость: O (n);
4. Сортировка массива с использованием эффективной сортировки (например, быстрой сортировки) в обратном исходном порядке, например [(C, 3), (B, 2), (A, 1)]. Стоимость: O (n log (n));
5. Создать связанный список из обращенного массива. Стоимость: O (n).

Общая стоимость: O (n log (n))

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

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

И да, это патологический вопрос (и ответ). Конечно, вы можете сделать это в O (n).

Answer 2

Каждый алгоритм O (n) также является O (n log n), поэтому ответ - да.

Answer 3

Глупая идея, но O (n log n), а не O (n)

• Назначьте каждому элементу списка уникальный идентификатор. Идентификатор каждого преемника должен быть больше, чем идентификатор элемента (O (n))
• Сортировка элементов в порядке возрастания с использованием идентификатора в качестве ключа с использованием любого алгоритма сортировки, основанного на сравнении (O (n log n))
• Создайте новый список, используя порядок, заданный сортировкой элементов (O (n))

Answer 4

Ну ...

Вы можете использовать рекурсию, которая принимает связанный список и инвертирует его, вызывая себя с двумя половинами связанного списка, где, если на входе всего два узла, он инвертирует их.

Это крайне неэффективно, но я считаю, что это O (nlog (n)) ...

Что-то вроде следующего в псевдокоде (при условии, что у вас есть функция len, которая возвращает длину списка в O (n), и функция sub_list(list, start_id, end_id), которая возвращает подмножество списка, начиная с start_id и заканчивая end_id в O (N)):

function invert(list)

    if len(list) == 1 return list

    if len(list) == 2:
        new_list = list.next
        new_list.next = list
        return new_list

    middle_of_list = len(list) / 2  <-- integer division

    first_half = invert ( sub_list(list, 1, middle_of_list) )
    second_half = invert ( sub_list(list, middle_of_list+2, len(list) )

    first_half.next = second_half

    return first_half

Answer 5

Если вопрос на самом деле относится к алгоритму Ω (nlgn), возможно, подойдет этот слишком сложный алгоритм?

• построить сбалансированную древовидную структуру из связанного списка
• каждый лист содержит как исходное значение из связанного списка, так и порядковый номер значения в связанном списке; используйте индекс в качестве ключа дерева
• пройти по дереву, чтобы сообщить обо всех листьях в обратном порядке к исходному индексу
• создать новый связанный список из соответствующих значений

Answer 6

Если вы педантичны, тогда этот алгоритм равен O (n log n), потому что указатели имеют размер не менее log n и должны быть назначены n раз.

Но на самом деле машины имеют фиксированный размер слова, поэтому это обычно не учитывается.