Сортировка почти сортированного массива (элементы, неуместные не больше, чем k)
Меня недавно задали этот вопрос интервью:
Вам дают массив, который почти отсортирован в этом каждый из
Nэлементы могут быть неуместны не больше, чемkположения от корректного отсортированного порядка. Найдите пространство и время эффективным алгоритмом для сортировки массива.
Я имею O(N log k) решение следующим образом.
Давайте обозначим arr[0..n) означать элементы массива от индекса 0 (включительно) к N (эксклюзивный).
- Вид
arr[0..2k)- Теперь мы знаем это
arr[0..k)находятся в отсортированных положениях их финала... - ... но
arr[k..2k)может все еще быть неуместенk!
- Теперь мы знаем это
- Вид
arr[k..3k)- Теперь мы знаем это
arr[k..2k)находятся в отсортированных положениях их финала... - ... но
arr[2k..3k)может все еще быть неуместенk
- Теперь мы знаем это
- Вид
arr[2k..4k) - ....
- Пока Вы не сортируете
arr[ik..N), затем Вы сделаны!- Этот заключительный шаг может быть более дешевым, чем другие шаги, когда у Вас есть меньше, чем
2kэлементы оставлены
- Этот заключительный шаг может быть более дешевым, чем другие шаги, когда у Вас есть меньше, чем
На каждом шаге Вы сортируете самое большее 2k элементы в O(k log k), помещение, по крайней мере, k элементы в их финале отсортировали положения в конце каждого шага. Существуют O(N/k) шаги, таким образом, полная сложность O(N log k).
Мои вопросы:
-
O(N log k)оптимальный? Это может быть улучшено? - Можно ли сделать это, (частично) не обращаясь те же элементы?
4 ответа
Как Боб Седжвик показал в своей диссертационной работе (и последующих), сортировка вставкой полностью разрушает «почти отсортированный массив». В этом случае ваша асимптотика выглядит хорошо, но если k <12, я уверен, что сортировка вставкой выигрывает каждый раз. Я не знаю, есть ли хорошее объяснение , почему сортировка вставкой работает так хорошо, но место для поиска можно найти в одном из учебников Седжвика под названием Алгоритмы (он сделал много изданий для разных языков).
Я понятия не имею, является ли O (N log k) оптимальным, но, ближе к делу, мне все равно - если k мало, имеют значение постоянные множители, а если k велико, вы можете а также просто отсортируйте массив.
Сортировка вставкой решит эту проблему без повторной сортировки тех же элементов.
Нотация Big-O очень хорошо подходит для класса алгоритмов, но в реальном мире константы имеют значение. Слишком легко упустить это из виду. (И я говорю это как профессор, преподававший нотацию Big-O!)
Ваше решение является хорошим, если k достаточно велико. Нет лучшего решения с точки зрения временной сложности; каждый элемент может оказаться неуместным на k мест, что означает, что вам нужно выучить log2 k бит информации, чтобы разместить его правильно, что означает, что вам нужно сделать log2 k По крайней мере, сравнений - так что сложность должна быть не менее O (N log k) .
Однако, как указывали другие, если k мало, постоянные члены убьют вас. В этом случае используйте что-то очень быстрое для каждой операции, например сортировку вставкой.
Если вы действительно хотите быть оптимальным, вы бы реализовали оба метода и переключились с одного на другой в зависимости от k .
Если использовать только модель сравнения, то оптимальным будет O(n log k). Рассмотрим случай, когда k = n.
Чтобы ответить на ваш другой вопрос, да, это можно сделать без сортировки, используя кучи.
Используйте min-кучу из 2k элементов. Сначала вставляем 2k элементов, затем удаляем min, вставляем следующий элемент и т.д.
Это гарантирует O(n log k) времени и O(k) пространства, а кучи обычно имеют достаточно маленькие скрытые константы.
Поскольку k, очевидно, должно быть довольно маленьким, сортировка вставками, вероятно, является наиболее очевидным и общепринятым алгоритмом.
При сортировке вставкой на случайных элементах вам нужно просканировать N элементов и переместить каждый из них в среднем на N/2 позиций, что дает ~N*N/2 общих операций. Константа "/2" игнорируется в характеристике big-O (или аналогичной), что дает сложность O(N2).
В предложенном вами случае ожидаемое число операций равно ~N*K/2 - но поскольку k - константа, весь член k/2 игнорируется в характеристике big-O, поэтому общая сложность равна O(N).