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

Question

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

Это правильно?

Спасибо

Answer 1

РЕДАКТИРОВАТЬ 2 :

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

РЕДАКТИРОВАТЬ : очевидно, вы упустили момент, поэтому я постараюсь уточнить.

Во-первых, вставка 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 .. i has быть перемещенным.

Итак, сумма больше, чем \ sum_i i = O (N²).