Блог

Главная - Вопросы по программированию - Сортировка массива из n целых чисел в диапазоне [1, n ^ α], когда α является положительным целым числом

Сортировка массива из n целых чисел в диапазоне [1, n ^ α], когда α является положительным целым числом

#arrays #sorting

#массивы #сортировка

Вопрос:

Я пытаюсь подумать об алгоритме, который сортирует массив из n целых чисел в диапазоне диапазонпо временной сложностиO(n), где альфа— положительное целое число.

Я не могу использовать подсчет сортировки, поскольку временная сложность будет.

Как я могу использовать информацию о диапазоне чисел и сортировать массив, когда перебор по диапазону невозможен?