Должен ли счетный диапазон сортировки всегда быть в [0, k]?

Question

Могу ли я выполнить подсчет по небольшому диапазону чисел, скажем, A = [7,9,12,15] из огромного пула чисел, который, как я знаю, будет состоять только из чисел в небольшом массиве?Или маленький диапазон всегда должен быть [0..k].

Я могу сделать сортировку по массиву A, сказав [0..15], но это не имеет смысла.А что, если A = [100,750,452]

Так что я думаю, что это возможно.Я хотел бы, чтобы некоторые входные данные, пожалуйста.

Answer 1

Ваш вопрос не очень понятен, но здесь он идет. Из вашего примера A = [7,9,12,15] диапазон будет [0..15] и потребует дополнительного пространства размера k = 15 (и другого результирующего массива A [длина]. Так как n (A [длина] ]) равен 4, общее время выполнения будет равно тета (k + n). Подсчет сортировки является алгоритмом «пространственно-временного компромисса», но если использовать его в вашем случае, он не будет иметь никакого смысла. компромисс. Счетная сортировка должна использоваться, когда у вас есть k = Big-O (n), что означает, что максимальное значение в вашем A [] меньше размера A []. Кстати, я думаю, что алгоритм все равно будет сортировать ваш пример правильно.