Radix Sort Анализ временных затрат в лучшем и худшем случае

Когда сортировка по основанию используется со стабильной сортировкой (в частности, сортировкой по счету), временные затраты в лучшем и наихудшем случае для сортировки по основанию обычно задаются как Theta(d(n+k)), где d — количество цифр для каждой сортировки. число для сортировки, а k — количество значений, которые может принимать каждая цифра (обычно 10 (из-за 0-9)).

Несмотря на мои исследования, я до сих пор не смог найти хорошего объяснения разницы между «лучшими» и «худшими» случаями для сортировки по основанию. Может кто-нибудь объяснить, что представляет собой «лучший» случай и «худший» случай в контексте использования сортировки по основанию? Если да, то можете ли вы доказать, что они оба находятся в тета (d (n + k))?


sorting algorithm time-complexity counting-sort radix-sort
person jippyjoe4    schedule 17.03.2018    source источник
comment
Количество операций чтения и записи обычно одинаково для лучшего и худшего случаев. Время может отличаться из-за шаблона данных. Случайные данные приведут к случайной записи, что не является дружественным к кэшу, в то время как сортировка по основанию уже отсортированных данных будет выполнять последовательную запись, что дружественно к кэшу.   -  person rcgldr    schedule 17.03.2018
comment
@rcgldr Я так и думал; поэтому я не совсем уверен, в чем разница между лучшим и худшим случаем. Хотя вы упоминаете кеши, я думаю, что я должен анализировать алгоритм на более теоретическом уровне, в частности, как исходный список ввода может повлиять на время выполнения сортировки подсчетом. Но я не уверен.   -  person jippyjoe4    schedule 17.03.2018
comment
Кажется, есть конфликт с формулировкой проблемы. Если время наилучшего и наихудшего случая имеет одинаковую Theta, а такие проблемы, как кеш, следует игнорировать, то может показаться, что на самом деле это не лучший и наихудший случай. Постановка задачи не разъясняет, как определяются наилучший и наихудший случай.   -  person rcgldr    schedule 17.03.2018
comment
Я думаю, что мы видим ту же проблему здесь; Я тоже не понимаю. Но это то, что он спрашивает.   -  person jippyjoe4    schedule 17.03.2018
comment
Все случаи являются как лучшими, так и худшими. Так же, как min(5,5,5,5) == max(5,5,5,5) == 5.   -  person user202729    schedule 19.03.2018
comment
Я мог видеть, что если все элементы на входе имеют одинаковый максимальный уровень, тогда это потребует сложности O (n). Например, в этом случае [99,12,14,15]. Но я не уверен, будет ли наихудший сценарий из-за таких входных данных, как [1, 1000,12,13,777,1000000]. Кроме того, в последнем случае массив сортируется за 6 проходов. Так что я не совсем уверен, что это худший случай. Может кто-нибудь, пожалуйста, подтвердите. Если это не так, пожалуйста, дайте мне знать, какой ввод приведет к наихудшему случаю.   -  person srinivas    schedule 07.07.2019

Ответы (1)


arrow_upward
0
arrow_downward

Поразрядная сортировка сортирует числа, начиная с последней цифры, двигаясь вперед (сортирует цифры единиц, затем цифр десятков, затем сотен и т. д.), и, благодаря этому, выполняет сортировку d (количество цифр). Теперь, глядя на то, как он сортирует каждый набор цифр, это делается с помощью алгоритма сортировки ведра, где каждое целое число в диапазоне (обычно 0-9) имеет свое собственное «ядро», затем каждое число помещается в соответствующее ему ведро на основе значение текущей цифры (5 с 5, 8 с 8 и т. д.). Хотя обычно говорят, что это θ(n), на самом деле это θ(n+k), где n — количество элементов, а k — количество сегментов, что, по сути, является диапазоном данных (0–9 — это 10 ведер).

Самая сложная часть сортировки ведра заключается в том, что отображение из списка в ведро должно быть θ(1), что делает отображение n элементов θ(n). Оттуда самая трудоемкая часть связана с необходимостью пройтись по каждому ведру по порядку (k ведер) и вытащить элементы внутри них (n элементов). Из-за этого алгоритм сортировки ведра становится θ (n + k).

В целом, d сортировок ведра выполняются с работой n+k каждый раз, что делает общую сложность θ(d(n+k)).

person Cullan Bedwell    schedule 20.04.2019