Алгоритм для сортировки списка в Θ (n) времени

Question

Задача состоит в сортировке списка, содержащего n различных целых чисел, которые варьируются от 1 до kn включительно, где k - фиксированное положительное целое число. Разработайте алгоритм для решения проблемы в Θ (n) времени.

Я не просто хочу получить ответ. Объяснение помогло бы, или если бы кто-то мог заставить меня указать в правильном направлении.

Я знаю, что время Θ (n) означает, что время алгоритма прямо пропорционально количеству элементов. Не уверен, куда идти оттуда.

Answer 1

Легко фиксируется k: Создайте массив счетчиков кол-во. Установите их все на ноль. Перейдем через массив, увеличивая счетчик i на единицу, если элемент массива равен i. Используйте массив счетчиков для повторного создания отсортированного массива.

Очевидно, что это неэффективно, если k> log n.

Answer 2

Ключ в том, что целые числа варьируются от 1 до kn, поэтому их длина ограничена. Это немного сложно:

Общее предположение, когда мы говорим, что алгоритм сортировки - это O (N), состоит в том, что число N вписывается в постоянное число машинных слов, так что мы можем делать математику на числах этого размера в постоянное время. Следуя этому предположению, kN также вписывается в постоянное число машинных слов, так как k является фиксированным положительным целым числом. Поэтому ваш вход - это слова O (N), а каждое слово - фиксированное количество бит, поэтому ваш вход - O (N) бит.

Следовательно, любой алгоритм, который принимает время, пропорциональное количеству бит на входе, считается O (N).

Есть на самом деле много вариантов, но когда этот конкретный вопрос задаются именно таким образом, люди с просьбой, как правило, хочет, чтобы вы придумали поразрядную сортировку:

https://en.wikipedia.org/wiki/Radix_sort

Старший бит первого radix sort просто разбивает целые числа на 2^W-ведра в соответствии со значениями их верхних W-бит, а затем разбивает каждый ковш в соответствии со следующими W-битами и т. д. до тех пор, пока все биты не будут обработаны.

Время, затраченное на это O (N * (word_size/W)), но, как мы сказали, размер слова постоянный, а W постоянна, поэтому это O (N).