Я узнал о сортировке radix, но все еще не могу понять что-то.Изменение базы в сортировке radix
Предположим, что мое максимальное число n c (c постоянна). Могу ли я всегда менять базу чисел на n, и поэтому наихудшей сложностью будет O (n)?
И если да, то не лучший способ сортировки массива - найти максимальное значение O (n), а затем использовать сортировку radix?
Есть два независимых вопроса:
Если максимальное значение в массиве п с для фиксированной константы с, то делает базисное то в базе п всегда потребуется время O (N) ?
В чем заключается сложность нахождения наибольшего значения в массиве, а затем использование сортировки base-n radix?
На вопрос (1) вы правы, что время выполнения будет равно O (n). Стоимость сортировки по методу радикса равна O (n log b U), где b является базой сортировки оснований, а U является максимальным значением в массиве (это потому, что это число имеет Θ (журнал b U) base-b цифры в нем). Поэтому в этом случае время выполнения O (n log n n c) = O (nc) = O (n), считая, что c является фиксированной константой.
Обратите внимание, что в предыдущем анализе предполагается, что c является фиксированной константой , известной заранее. Если вам задан массив произвольных целочисленных значений и используется базовая сортировка base-n, то время выполнения будет O (n log U/log n), которое является только O (n), если вам гарантировано что максимальное значение не более n cдля фиксированной константы c. Так как это вообще не истинное утверждение, вы не можете сказать, что сортировка radix всегда выполняется во времени O (n).
Сложность для сортировки radix будет равна O (размер массива). Константа c определяет количество необходимых проходов, но поскольку это постоянный множитель, он игнорируется для целей сложности, который остается равным O (размер массива). – rcgldr