Временная сложность сортировки с лимитом

Question

Давайте возьмем три разных вида: Выбор, Пузырь и Быстрый. Вот как они работают с массивом размером n:

• Выбор: O (n ² ) в среднем и худшем случаях
• Bubble: O (n ² ) в среднем и наихудшем случаях
• Быстрая сортировка: O (n log n), O (n ² ) в среднем и наихудшем случаях

Если к ним применить предел L, какова будет временная сложность сортировки? Я предположил, что ответом будет: O (nL) и O (n log L) - это правильно? Почему или почему нет? Кроме того, есть ли определенный тип сортировки массивов, который работает лучше других при выполнении сортировки с ограничением?

Например:

a = [1, 4, 2, 7, 4, 22, 49, 0, 2]
sort(a, limit=4)
==> [0, 1, 2, 2]

Answer 1

Сортировка выбора: временная сложность для сортировки выбора будет O (nL). В сортировке выбора мы добавляем следующий наименьший элемент в несортированной части списка к отсортированной части списка. Поскольку нам нужно только L отсортированных элементов, нам нужно только итерировать L раз. В каждой итерации мы должны перебирать несортированную часть списка, чтобы найти наименьший элемент, поэтому нам нужно всего n * L итераций. Это приводит к O (nL).

Bubble sort: временная сложность для сортировки выбора будет O (nL). Обычная сортировка пузырьков помещает текущий самый большой элемент в конец списка после каждой итерации. Мы можем изменить пузырьковую сортировку так, чтобы в каждой итерации мы помещали наименьший элемент в начало списка. Вместо того, чтобы начинать с начала массива, мы начинаем с конца массива. Нам нужно только L итераций, чтобы найти L отсортированных элементов, поэтому сложность по времени становится O (nL).

Быстрая сортировка: Быстрая сортировка делит массив на две части и сортирует каждую часть с помощью рекурсии. Временная сложность все равно будет O (log (n) * n), потому что в быстрой сортировке нет «контрольной точки». У нас никогда не бывает частично отсортированного списка, который содержит L наименьших элементов, когда мы выполняем быструю сортировку.

Сортировка слиянием: идея похожа на идею быстрой сортировки. Нам нужно достичь базового варианта рекурсии и объединить результаты, чтобы получить полностью отсортированный список, поэтому у нас все еще есть время выполнения O (log (n) * n).