Какова сложность наихудшего случая для сортировки ведра?

Question

Я только что прочитал страницу Википедии о Bucket sort .В этой статье говорится, что сложность наихудшего случая - O (n²).Но я думал, что сложность в худшем случае была O (n + k), где k - количество сегментов.Вот как я вычисляю эту сложность:

1. Добавьте элемент в корзину.При использовании связанного списка это O (1)
2. Проходя по списку и помещая элементы в правильное ведро = O (n)
3. Слияние ведра = O (k)
4. O (1) * O (n) + O (k) = O (n + k)

Я что-то упустил?

Answer 1

Чтобы объединить сегменты, их сначала нужно отсортировать.Рассмотрим псевдокод, приведенный в статье в Википедии:

function bucketSort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    nextSort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

nextSort(buckets[i]) сортирует каждое из отдельных сегментов.Как правило, для сортировки сегментов используется другая сортировка (т. Е. Сортировка вставкой), так как при уменьшении и размере различные нерекурсивные сортировки часто повышают производительность.

Теперь рассмотрим случай, когда всеn элементы оказываются в одном ведре.Если мы используем сортировку вставками для сортировки отдельных сегментов, это может привести к худшему результату O(n^2).Я думаю, что ответ должен зависеть от того, какую сортировку вы выберете для сортировки отдельных сегментов.

Answer 2

Если вы можете гарантировать, что каждый сегмент представляет собой уникальное значение (эквивалентные элементы), то сложность времени в наихудшем случае будет O (m + n), как вы указали.

Answer 3

Что если алгоритм решит, что каждый элемент принадлежит одному и тому же сегменту?В этом случае связанный список в этом сегменте необходимо просматривать при каждом добавлении элемента.Это занимает 1 шаг, затем 2, затем 3, 4, 5 ... n .Таким образом, время - это сумма всех чисел от 1 до n , которая равна (n ^ 2 + n) / 2, то есть O (n ^ 2).

Конечно, это «наихудший случай» (все элементы в одном сегменте) - алгоритм, позволяющий рассчитать, в какой сегмент для размещения элемента, обычно предназначен для предотвращения такого поведения.

Answer 4

Это дополнительный ответ к @perreal. Я пытался опубликовать это как комментарий, но это слишком долго. @perreal правильно указывает, когда сортировка ведра имеет смысл. Разные ответы делают разные предположения о том, какие данные сортируются. НАПРИМЕР. если сортируемые ключи являются строками, то диапазон возможных ключей будет слишком большим (больше, чем массив сегментов), и нам нужно будет использовать только первый символ строки для позиций сегмента или какой-либо другой стратегии. Отдельные корзины должны быть отсортированы, потому что они содержат элементы с разными ключами, что приводит к O (n ^ 2).

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

Я хотел бы добавить, что если вы сталкиваетесь с O (n ^ 2) из-за природы сортируемых ключей, сортировка по сегментам может быть неправильным подходом. Если у вас есть диапазон возможных ключей, который пропорционален размеру ввода, вы можете воспользоваться линейной сортировкой временных интервалов, если в каждом сегменте будет храниться только 1 значение ключа.

Answer 5

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

Теперь предположим, что входные данные не получены из равномерного распределения.Как уже указывалось @mfrankli, в худшем случае это может привести к ситуации, в которой все предметы попадают, например, в первое ведро.В этом случае для вставки сортировки потребуется в худшем случае O (n ^ 2).

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