Я читаю введение в алгоритмы 2-го издания, и есть вопрос о том, что мы можем отсортировать n целых чисел, которые находятся между 0 и n3-1 за линейное время. Я думаю о подходе сортировки IBM по основанию. Я начинаю с младшей значащей цифры, разделяю числа по младшей значащей цифре, а затем сортирую, затем разделяю по следующей младшей значащей цифре и так далее. Каждое разделение занимает O(n) времени. Но у меня есть сомнения, например, если одно из чисел состоит из n цифр, то алгоритм принимает O(1*n+2*n+...+n*n)=O(n2) время, да? Можем ли мы гарантировать, что числа состоят менее чем из n цифр, или кто-нибудь может дать другую подсказку по этому вопросу? Спасибо
Сортировка в линейном времени
comment
Каждое число находится между 0 и n ^ 3 - 1. Таким образом, оно будет иметь не более 3 цифр базы n.
- person Ivaylo Strandjev schedule 10.03.2013
comment
спасибо, так что с этой информацией мое решение работает правильно?
- person yrazlik schedule 10.03.2013
comment
@IvayloStrandjev: По сути, это ответ в моей книге. Вы должны (повторно) опубликовать его, хотя вы можете дать некоторые подробности о том, как выполнить сортировку ровно за три прохода.
- person nneonneo schedule 10.03.2013
comment
связанные: Сортировка в линейном времени?
- person jfs schedule 11.03.2013
Ответы (2)
Сложность сортировки по основанию равна O(dn), где d — количество цифр в числе.
Алгоритм работает за линейное время только тогда, когда d является постоянным! В вашем случае d = 3log(n) и ваш алгоритм будет работать в O(nlog(n)).
Честно говоря, я не уверен, как решить эту проблему за линейное время. Есть ли какая-либо другая информация о природе чисел? Мне интересно, отсутствует ли какая-либо другая информация о природе чисел...
person
Marsellus Wallace
schedule
10.03.2013
спасибо за ответ, на самом деле я нашел ответ, мы рассматриваем числа как двузначные числа в системе счисления n, затем мы сортируем эти двузначные числа. Общее время O (n)
- person yrazlik; 10.03.2013
Если вы разбиваете число на двузначные «ключи», разве вы не получите «d = 3log(n)/2»? у вас есть ссылка на подробный разбор алгоритма? Спасибо
- person Marsellus Wallace; 10.03.2013
На самом деле, я нашел его в руководстве для инструктора по книге, и вот что там сказано: Рассматривайте числа как двузначные числа в системе счисления n. Каждая цифра находится в диапазоне от 0 до n-1. Отсортируйте эти двузначные числа с помощью сортировки по основанию. Есть 2 вызова сортировки подсчетом, каждый из которых занимает Θ(n + n) = Θ(n) времени, так что общее время равно Θ(n).
- person yrazlik; 11.03.2013
@bigO: 1.
n**3-1 требует 3 цифры в базе n. 2. Вы не можете ожидать, что манипулирование цифрой в базе n будет O(1) (постоянное время) для произвольно большого n.
- person jfs; 11.03.2013
Я бы проголосовал за это (если бы мог!). Вы (не)удобно смешиваете две модели вычислений... Если вы думаете, что размер ввода равен n, то вы неявно предполагаете модель оперативной памяти, в которой n соответствует O (1) словам, но затем вы переключаетесь на битовую сложность. ..
- person Knoothe; 11.03.2013
@ J.F.Sebastian: Какую модель вычислений вы используете? В обычной модели оперативной памяти Word разумно предположить, что n умещается в O (1) слов (иначе сам ваш размер ввода не равен O (n))
- person Knoothe; 11.03.2013
@Knoothe: Вы правы, если
n умещается в O (1) слов, тогда манипулирование цифрой в базе n будет O (1), а для ограничения n**3 проблема может быть решена за время O (n).
- person jfs; 11.03.2013
@Knoothe поздравляю с новой привилегией голосовать против! :) Что ты имеешь ввиду под переходом на разрядность?
- person Marsellus Wallace; 14.03.2013
@Gevorg: я не отрицал этот ответ, если вы это имеете в виду :-) Позвольте мне спросить вас об этом. Каков размер ввода? Тета(n) или тета(dn)? Что означает линейное время? Тета(n) или Тета(dn)? Если вы говорите, что размер ввода равен Theta(n), разве вы не игнорируете d?
- person Knoothe; 15.03.2013
Нельзя просто ответить на 1 вопрос еще 5! :) Время работы RadixSort зависит от
n (элементов) и d (ключей). Параметры d и n обычно независимы, а d постоянны и, желательно, малы. Точно так же сложность графовых алгоритмов, например, зависит от G и V. В этом случае d является функцией n и, таким образом, у нас есть время работы O(nlog(n)), что в этом не так?
- person Marsellus Wallace; 16.03.2013
@Gevorg: Позвольте мне попытаться уточнить: вы хотите принять во внимание количество битов в числе при вычислении времени выполнения сортировки по основанию. Это хорошо, но почему вы игнорируете это при подсчете размера ввода? Размер входных данных равен Theta(n log n), не так ли (у вас есть n целых чисел размера log n каждое)? В этом случае, по самому определению временной сложности, алгоритм Theta(n log n) является линейным!, потому что, если S = nlog n — размер входных данных, тогда Theta(S) алгоритм линейный.
- person Knoothe; 17.03.2013
@Knoothe нет, я никогда не упоминал биты, а просто рассматриваю количество ключей в элементе. В нашем случае ключами являются цифры! Например: если число равно 834, цифры/ключи равны 8,3,4, а d = 3. Если рассматривать объект даты как элемент, например, ключами будут месяц, день, год и d = 3. Время работы RadixSort зависит от ключей и количества элементов
O(dn) (он сортирует n элементов d раз). С d=3log(n) (в базе 10, учитывая, что максимальное число равно n^3 - 1), тогда время работы равно O(nlog(n)) (большой-O, а не тета).
- person Marsellus Wallace; 17.03.2013
@Gevorg: Вы все еще не понимаете, что я пытаюсь сказать. Если вы считаете количество цифр важным, то вам следует постоянно учитывать его на протяжении всего анализа во время выполнения: то есть при подсчете размера входных данных. Я утверждаю, что, чтобы быть последовательным (и правильным), вы должны принять размер ввода равным Theta(dn) (или Theta(n log n)). И если это так, по определению сортировка по основанию является линейной. Если вы берете размер ввода как Theta(n), то вы неявно предполагаете модель WORD RAM (целые числа вписываются в слово), и в этом случае ваш d практически постоянен!
- person Knoothe; 21.03.2013
(Примечание: я говорю о текущей проблеме, где каждое целое число находится в диапазоне n ^ 3 -1, при записи в базе-n количество цифр постоянно)
- person Knoothe; 21.03.2013
Я отсылаю вас к: stackoverflow.com/questions/4238460/. Кстати, извините за столько комментариев. Я не могу правильно выражаться (и эта система комментирования довольно болезненна). :-)
- person Knoothe; 21.03.2013
@Knoothe Я слишком поздно с этим моим последним комментарием, мой плохой. Давайте просто согласимся не согласиться! :) В качестве ссылки на мою точку зрения (считая количество цифр важным), пожалуйста, ознакомьтесь с главой «Сортировка в линейном времени» книги «Введение в алгоритмы» — CLR. Теперь пойдем спорить по другим вопросам! :)
- person Marsellus Wallace; 15.05.2013
Предполагая модель ОЗУ слов и то, что n помещается в O (1) слов, существует алгоритм линейного времени.
Запишите каждое число в базе n и выполните сортировку по основанию (со стабильной версией сортировки подсчетом в качестве базовой сортировки цифр).
Если вы хотите предположить неограниченное n, то размер входных данных на самом деле n log n, и в этом случае сортировка по основанию снова работает (за время O (n log n)), и с технической точки зрения это все еще алгоритм с линейным временем! (Конечно, я полагаю, что это все еще предполагает, что арифметика равна O (1)...)
person
Knoothe
schedule
11.03.2013
linearithmic на самом деле linear?
- person Marsellus Wallace; 16.03.2013
Просто чтобы продолжить, так как мы говорили некоторое время сейчас! :) Я не уверен, как вы пришли к
O(nlog(n)), но если вы примете это как линейное решение, проблема будет тривиально решена с хорошей реализацией QuickSort, MergeSort или других...
- person Marsellus Wallace; 17.03.2013
@Gevorg: Нет, сравнение целых чисел будет O (log n), а Quicksort и т. Д. Будет Theta (n (log n) ^ 2). Базовая вычислительная модель важна. В большинстве учебников по алгоритмам используется модель WORD RAM (и на практике большинство людей используют ее, не задумываясь, поскольку она наиболее близка к реальному компьютеру). В этом случае (т. е. в модели WORD RAM) размер ввода равен Theta (n), сортировка по основанию — O (n), а быстрая сортировка и т. д. — O (n log n).
- person Knoothe; 21.03.2013
(опять же: я говорю о текущей задаче, где целые числа равны ‹ n^3).
- person Knoothe; 21.03.2013
