Сортировка по линейному времени

Я читаю введение в алгоритмы 2-го издания, и возникает вопрос, что мы можем сортировать n целых чисел, которые находятся между 0 и n -1 в линейном времени. Я думаю о подходе к подходу IBM к основанию. Я начинаю с наименьшей значащей цифры, отдельных чисел по отношению к наименьшей значащей цифре, а затем сортирую, затем отделяю ее относительно следующей наименее значащей цифры и т. Д. Каждое разделение занимает время O (n). Но у меня есть сомнения, например, если одно из чисел состоит из n цифр, тогда алгоритм принимает O (1 * n + 2 * n + ... + n * n) = O (n) время, правильно? Можем ли мы заверить, что числа состоят из менее чем n цифр, или кто-нибудь может дать еще один намек на вопрос? СпасибоСортировка по линейному времени

источник

2013-03-10 yrazlik

Каждое число находится между 0 и n^3 - 1. Таким образом, оно будет иметь не более 3-х цифр base n. –

спасибо, поэтому с этой информацией мое решение работает правильно? – yrazlik

да, я так считаю. –

Сложность сортировки Radix составляет O(dn) с d как число цифр в числе.

Алгоритм работает в линейном режиме только в том случае, когда d постоянно! В вашем случае d = 3log(n) и ваш алгоритм будет работать в O(nlog(n)).

Я честно не знаю, как решить эту проблему в линейном времени. Есть ли какая-либо другая информация о характере чисел, которые мне задают вопрос о том, есть ли какая-либо другая информация, пропавшая без вести о характере чисел ...

источник

2013-03-10 19:14:18 Gevorg

спасибо за ответ, я нашел ответ на самом деле, мы обрабатываем числа как 2- цифры в радиусе n, тогда мы сортируем эти двузначные числа. Общее время: O (n) – yrazlik

Если вы сломали число в 2-значных «ключах», не закончите ли вы «d = 3log (n)/2»? есть ли у вас ссылка на подробный анализ алгоритма? спасибо – Gevorg

В общем, я нашел его из руководства инструктора книги, и вот что он говорит: Рассматривайте числа как 2-значные числа в радиусе n. Каждая цифра колеблется от 0 до n -1. Отсортируйте эти 2-значные числа с сортировкой по основанию. Существует 2 вызова подсчета сортировки, каждый из которых принимает значение Θ (n + n) = Θ (n), так что общее время равно Θ (n). – yrazlik

Предполагая, что модель ОЗУ, и что n соответствует O (1), существует алгоритм линейного времени.

Напишите каждое число в базе n и выполните сортировку по основанию (со стабильной версией подсчета сортировки в качестве базовой сортировки цифр).

Если вы хотите принять неограниченное n, то размер ввода на самом деле n log n, и в этом случае сортировка radix снова работает (в O (n log n)), и технически говоря, это все еще линейный алгоритм времени! (Конечно, я предполагаю, что это все еще предполагает, что арифметика равна O (1) ...)

источник

2013-03-11 03:08:13 Knoothe

Является ли 'linearithmic' фактически' linear'? – Gevorg

Просто следить за тем, как мы разговаривали какое-то время! :) Я не уверен, как вы добрались до 'O (nlog (n))', но если вы примете это как линейное решение, тогда проблема будет тривиально решена с хорошей реализацией QuickSort, MergeSort или других ... – Gevorg

@Gevorg: Нет, сравнение целых чисел будет O (log n), а Quicksort и т. Д. Будет Theta (n (log n)^2). Основная вычислительная модель важна. Большинство учебников алгоритмов используют модель WORD RAM (и на практике большинство людей используют это, не задумываясь, так как оно ближе всего к реальному компьютеру). В этом случае (т. Е. В модели WORD RAM) размер ввода - Theta (n), сортировка по методу radix - это O (n) и quicksort и т. Д. O (n log n). – Knoothe

ответ

Смежные вопросы