алгоритм последовательной сортировки

Question

Я хотел сортировать элементы, которые поступают последовательно, т. Е. Я хочу, чтобы мой вектор сортировался до того, как появился следующий элемент. Я знаю, что сортировка вставки имеет сложность n^2, если у меня есть общее число n элементы. Слияние должно быть лучше. Однако часто говорят, что сортировка слияния имеет сложность n log n; но я думаю, это верно, если вы собираетесь сортировать n элементов сразу. Если они приходят, вместо этого, один за другим, и вам нужен временный вектор для сортировки, сложность возрастает до \ sum_ {i = 2}^n i log (i). Это все равно меньше n^2, я полагаю, но определенно больше, чем n log n.

Верно ли это?

Благодаря

Answer 1

EDIT 2:

\sum_{i=1}^N i log i > \sum_{i=1}^N i = O(N²) 

EDIT: судя по всему, вы пропустили точку, так что я постараюсь прояснить.

Во-первых, вставка N элементов в массив при обеспечении сортировки массива после каждой вставки может выполняться по сложности O (N²). Вы можете использовать следующий алгоритм для вставки один элемента:

• Поскольку массив отсортирован, использовать бинарный поиск, чтобы найти место, где вставлен элемент. Принимает время O (log i), где i - текущий размер массива.
• Вставьте элемент, перемещая все элементы после него на одно пятно справа. Это включает в себя перемещение до i элементов, так что это O (i).

Повторяя этот алгоритм для N вставок, получаем \ sum_i (i + log i) = O (N²).

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

Во-вторых, выполнение этой операции не может выполняться быстрее, чем O (N²): вставка одного элемента в массив размера i при сохранении отсортированного массива имеет сложность, превышающую O (i), поскольку она включает перемещение вверх до i элементов. Там просто нет обходного пути, чтобы обойти этот элементарный факт: если вставить 1 в [2,3,..,i], результат [1,2,3,..,i], что означает элементы 2, 3 .. я имел быть перемещен.

Таким образом, сумма больше, чем \ sum_i i = O (N²).