Как сложность сортировки сегментов может быть O (n + k)?

Question

Прежде чем сказать "об этом уже спрашивали" или "найти книгу по алгоритмам", пожалуйста, прочитайте и скажите, какая часть моих рассуждений пошла не так?

Скажем, у вас есть n промежуточных элементов, и вы разделили их на k лотков, это займет O (n) времени. Однако необходимо отсортировать каждый из k бинов, если для каждого бина используется быстрая сортировка, то это операция O ((n / k) log (n / k)), поэтому этот шаг потребует O (n *). 1004 * журнала (п / к) + к). Наконец, нужно собрать этот массив, для этого требуется O (n + k) (см. этот пост ), поэтому общая операция будет O (n + n log (n / k) + к). Теперь, как этот n log (n / k) исчез, я никак не мог понять. Я предполагаю, что существует некоторая математика, которая устраняет этот n * log (n / k). Кто-нибудь может помочь?

Answer 1

Ваше предположение:

• k - количество ведер - произвольно

не так.

Есть два варианта сортировки ведра, так что это довольно запутанно.

---

A

Количество сегментов равно количеству элементов на входе

См. Анализ здесь

---

B

Количество сегментов равно R - количество возможных значений для входных целых чисел

См. Анализ здесь и здесь

Answer 2

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

Если бы мне пришлось угадывать, вы могли бы взглянуть натипичный вариант, где выбирается k очень большой, так что n / k будет постоянной.В другом популярном варианте даже k >> n, поэтому вместо этого делится на k / n сегментов.

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

Answer 3

Ваш недостаток предполагает, что для сортировки ведер используется быстрая сортировка.Как правило, это не так, и именно так вы избегаете (n / k) log(n / k) терминов.