Сложность времени вставки в связанный список

Question

Извинения, если этот вопрос чувствует себя как проверка решения, но этот вопрос был задан в моем выпускном тесте по выпускникам, и на этом есть многое место:

Что такое худшее время Сложность вставки $ n $ элементов в пустой связанный список, если связанный список должен поддерживаться в отсортированном порядке? .

На мой взгляд, ответ должен быть $ O (N ^ 2) $ потому что в каждой вставке нам придется вставить элемент в нужном месте и Возможно, что каждый элемент должен быть вставлен в последнее место, давая мне временную сложность $ 1 + 2 + ... (N-1) + N= O (n ^ ^ 2) $

Тем не менее, решение, которое я гласил, что мы можем сначала сортировать элементы в $ O (n \ log n) $ , а затем мы можем вставить их один К одному в $ O (n) $ , предоставив нам общую сложность $ O (n \ log n) $ < / span>.

Из данной формулировки вопроса, какое решение более APT? На мой взгляд, поскольку вопрос о том, что вопрос упоминает «связанный список должен поддерживаться в отсортированном порядке», я склонен сказать, что мы не можем заранее отсортировать элементы, а затем вставить их в отсортированный заказ.

Answer 1

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

практическая причина сделать это, вместо того, чтобы вставлять элементы, то сортировать, было бы, если объект связанного списка совместно используется с другим потоком, который требует его всегда отсортировать. (В таком сценарии вам нужно будет убедиться, что вставка одного элемента является атомным.) Итак, этот вопрос не просто делает странные требования для того, чтобы быть странным. Это такие требования, которые часто придумывают в реальном мире программирования.

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

Этот вопрос больше о понимании чтения, чем о алгоритмах. То, как это адрес, это немного трюк. Это несколько плохо сформулировано, потому что он полагается на точное чтение, но не может указывать на некоторые ключевые предположения, такие как тот факт, что получение элементов для вставки затрат $ O (n) $ Сравнение двух элементов можно сделать в $ O (1) $ , а входной домен эффективно неограничен (упражнение: придумайте $ o (n) $ алгоритм Если входы представляют собой целые числа в диапазоне $ [1,42] $ ). Но данный ответ правильный.

Вы сделали предположение, что нет способа использовать вспомогательную структуру данных. Ничто в заявлении о проблеме запрещает использование вспомогательных структур данных. Простой способ запрещать вспомогательные структуры данных, чтобы требовать $ O (1) $ Наверху памяти.

Обратите внимание, что даже в этом предположении ваши рассуждения неверны или, по крайней мере, неточны. Если вы узнали, что элементы приведены в правильном порядке, вы можете поддерживать указатель на хвост списка, и продолжать вставлять там, что примет $ O (n) $ . В худшем случае нет, если каждый элемент должен быть вставлен в последнюю позицию в целевом списке, но на последней позиции достигается при прохождении списка каким-либо образом. В худшем случае действительно $ \ theta (n ^ 2) $ , но чтобы доказать это, вы должны доказать, что поиск точки вставки в списке занимает $ \ Theta (n) $ time, и это требует доказательства того, что расстояние от любого указателя , в списке, ограничено ниже $ \ Omega (n) $ . Это так, если у вас есть постоянный номер $ a $ указателей (вы неявно предполагаемые $ a= 1 $ , с одним указателем в начале списка), так что вам нужно пройти хотя бы $ k / a $ us -Контассера "> $ k $ вставки в худшем случае.

Answer 2

Лучшая возможная структура, которую я знаю, представляют собой куча фибоначчи, вы можете вставлять элементы в $ O (1) $ и извлечь минимум в $ o (\ log (n)) $ , это означает, что если вам нужен отсортированный порядок всех элементов, вам требуется $ O (n \ log(n)) $ во время вставки новых элементов стоит только $ o (1) $ , я не знаю другой структуры, которая могла бы отставать от этого.

Answer 3

Это действительно сложный вопрос.Прежде всего, сложность O (NLOGN) применяется только для алгоритмов, которые используют сравнение между их элементами (сравнительный алгоритм).Существуют также алгоритмы, которые не являются сравнительными, такие как Radix, сорт, которую их сложность зависит от размера в битах, которые числа должны храниться в памяти.Поэтому, если мы предположим, что мы можем заранее отсортировать номера с любым алгоритмом, тогда мы также можем предположить, что номера являются натуральными, а максимальный элемент - m <10, поэтому с помощью Radix Worth вы получите наихудший случай O (10n)= O (n).Если мы не можем сделать никакого предположения, то вы правы.Если вам разрешено использовать только связанные списки и больше ничего более (без индексации любого вида), то сложность o (n ^ 2) (пузырька).

Answer 4

Это должно быть o (n). Следуйте алгоритму как -

1) Если связанный список пуст, то сделайте узел как голова и вернуть его.

2) Если значение вставленного узла меньше чем значение узла головы, затем вставьте узел В начале и сделайте его головой.

3) в цикле найдите соответствующий узел после который входной узел должен быть вставлен.

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

4) Вставьте узел после соответствующего узла найден на шаге 3