Часто, когда люди говорят о сложности алгоритмов сортировки, я вижу это объяснение:
Сложность сортировки по радиксу: O(nd), где n - длина
список и d это количество цифр
и
Сложность сортировки слиянием O(n log n), где n - длина
список
Это почти как если бы оправдать то, что радикальная сортировка почему-то часто медленнее, чем сортировка слиянием, даже если это не имеет никакого смысла.
Есть два случая:
Случай 1: Мы сортируем нормальные целые числа, которые имеют четыре байта.
Здесь сравнения занимают постоянное время, поэтому O(n log n) имеет смысл описать сортировку слиянием. Но при сортировке нормальных целых чисел d в O(nd) является константой (возможно, 4, для базы 16 - или 16, для базы 2. В любом случае, это константа, и число бинов в сортировке бинов называется radix сортировать весы, чтобы компенсировать это). Итак, не имеет ли смысла говорить, что радикальная сортировка равна O(n), а сортировка слиянием имеет объективно худшую сложность - O(nlogn)?
Случай 2: Мы сортируем строки, которые можно рассматривать как числа с любым количеством цифр в базовом ASCII.
Здесь сравнение занимает O(d) времени, потому что в худшем случае сравнение AAAAAAAAB с AAAAAAAAC может занять много времени.
В этом случае имеет смысл сказать, что радикальная сортировка имеет сложность O(nd), поскольку d изменяется в зависимости от ввода.
Однако разве из этого не следует, что сортировку слиянием в этом сценарии следует рассматривать как O(d*nlogn), поскольку время сравнения больше не является постоянным?
Мне кажется, что люди не верят, что радикальная сортировка достаточно быстра, чтобы использовать ее, и оправдывают ее большую постоянную времени, заставляя ее выглядеть хуже, чем сортировки, основанные на сравнении, из-за двусмысленности описания их сложности.
Я прошу прощения за плохое форматирование, но пока не уверен, как сделать так, чтобы он выглядел лучше в stackoverflow