Я недавно наткнулся на проблему C ++.Здесь идет.
Предположим, вы знаете, что все значения в целочисленном массиве попадают в диапазон от 0 до 9999. Покажите, что можно написать O (N) алгоритм для сортировки массивов с этим ограничением.
Насколько я понимаю, алгоритм O (N) - это алгоритм, в котором вы выполняете определенный набор операций O (1) N раз.Сейчас я не могу понять, как вы будете писать программу, которая сортирует массив чисел по O (N).Сортировка в ее самой основной форме состоит в сравнении чисел друг с другом, и нет алгоритма для того, чтобы сделать это за одну итерацию и получить отсортированный массив.
В этом вопросе подчеркивается, что элемент этогомассив может иметь значение только в диапазоне 0-9999.Из вопроса я могу понять, что это ограничение делает все это возможным, и я должен использовать его в своем Алгоритме, чтобы найти решение.Но я все еще никуда.Все известные мне алгоритмы сортировки (Selection, Insertion, Merge, Quick ...) имеют время выполнения больше, чем O (N), с минимальным значением O (log N).
Я могу понять, что некоторые из этих алгоритмов могут иметь время выполнения O (N), но только в своих лучших случаях.Но я не думаю, что вопрос задается в этом отношении.
Если кто-нибудь сможет пролить свет на эту проблему, я был бы признателен.