Я беру курс алгоритмов, и там я увидел, что временная сложность сортировки счета равна O (n + k), где k - диапазон чисел, а n - размер ввода. Мой вопрос в том, что, когда разница между k и n слишком велика, например, когда k = O (n) или O (n), можем ли мы сказать, что сложность O (n) или O (n)? Тогда в этом случае подсчет сортировки не является разумным подходом, и мы можем использовать сортировку слияния. Я прав?Временная сложность подсчета сортировки
Да, вы абсолютно правы по всем пунктам.
Кроме того, мы можем сделать более сильные утверждения: при к = O (N) или O (N), можно сказать, что сложность подсчета сортировки Θ (п) или Θ (n).
Вы все еще можете теоретически относиться к O (n) времени. Если диапазон значений составляет от 1 до n , то конвертировать в базу n и выполнять сортировку Radix. В базе n число имеет 3 цифры, поэтому ваше время выполнения - O (3n + 3n) + O (n) для базового преобразования. Общий O (n).
, что вы принимаете 'O (1)' операции над базовыми 'n' числами. Кажется, вряд ли будет в целом. – jfs
Спасибо за ответ, я просто хотел удостовериться, правильно ли я понял – 2013-03-24 14:25:08