Как отсортировать массив из N элементов, где каждое целое число принадлежит множеству {1,2,3,,,k}, используя оракул, который отвечает да и нет?
Массив состоит из n элементов, и каждый элемент является целым числом из набора {1,2,3,,,,k}. Существует оракул, который отвечает на все, что касается массива, да или нет. У вас есть доступ только к оракулу, а не к массиву. Покажите, что массив можно отсортировать не более чем по O(klog(n)) запросам.
Когда сортировка массив, мы должны сдача его (скажем, поменять местами элементы); как мы можем это сделать, если у нас нет доступа к массиву, но к оракулу, который может только вопросы отвечать?
Знаете ли вы, что k стоит в начале проблемы?
Ответы 1
Поскольку вы знаете все возможные значения в массиве, достаточно найти частоту каждого возможного значения. Затем выведите правильное количество единиц, правильное количество двоек и т. д.
Вы можете добиться этого в запросах Theta(k log n), во всех формах:
- «Частота элемента
xбольше, чемc?»
Это равносильно выполнению бинарного поиска для каждой из k частот. Поскольку частота каждого элемента является целым числом в [0, n], вы можете выполнить этот бинарный поиск не более чем с log_2(n+1)+1 запросами.
Определите «что-нибудь о массиве». Что, если я спрошу: «Сколько элементов в массиве имеют значение 1?»? Ответит да или нет?