Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

5:52a

отсортировать n чисел от 1 до n^2 за O(n) Здравствуйте. В книжке Александра Шеня «Программирование: теоремы и задачи» задание 4.4.6:
Даны n целых чисел в диапазоне от 1 до n^2. Как отсортировать их, сделав порядка n действий?

У меня такое впечатление, что за O(n) решить задачу невозможно, но я не могу это доказать. Есть идеи?

upd.: Есть такая штука: radix sort. И ведь даже знал о ней, а в голову не пришло.
upd.: я конкретно запутался. radix sort все-таки не подходит. Ждем развития событий.
upd.: все-таки radix sort рулит.
Проблема была в том, что там O(kn), k зависит от n: k=log(n^2). Но можно взять основание, равное n, для сортировки подсчетом, тогда k=2log_n{n}=2. И тогда задача решена. Всем спасибо.