Предположим, что нам дан массив содержащий неотрицательные целые числа (не обязательно различающиеся).
Пусть будет отсортированным в неубывающем порядке. Мы хотим вычислить
Очевидным решением является сортировка а затем вычисление . Это дает алгоритм, который работает во времени в худшем случае.
Можно ли сделать лучше? Можем ли мы вычислить за линейное время?
Мой главный вопрос - тот, что выше. Но было бы интересно узнать о следующем обобщении проблемы.
Пусть будет отсортированным согласно некоторому оракулу сравнения а - функция, заданная оракулом. Учитывая и оракулы для и , что мы можем сказать о времени, необходимом для вычисления ?
Мы все еще можем вычислить за времени. Но можем ли мы доказать суперлинейную нижнюю оценку для этого обобщенного случая?
Если ответ «да», имеет ли место нижняя граница, если предположить, что - это обычный порядок на целых числах, а - «хорошая» функция (монотонная, полиномиальная, линейная и т. Д.)?
Если массив состоит из различных целых чисел, то , поскольку расстояние между соседними элементами в не менее ; ситуация более интересна, когда они не должны быть отчетливыми.A m=max(A)+1 B 1
Для более общего вопроса, представьте ситуацию, в которой «интересна» только тогда, когда . Кажется возможным построить аргумент противника, который заставляет вас запрашивать для всех прежде чем вы сможете узнать , поэтому вам нужно отсортировать , чтобы найти ответ, который берет сравнений. (Есть некоторые сложности, так как это может быть случай, когда мы можем проверить, является ли в постоянном, а не линейном времени, путем запроса .) Это имеет место, даже если - многочлен (высокой степени).f(B[i],j) i=j f(B[i],i) i maxif(B[i],i) A Ω(nlogn) A[i]=B[j] f(A[i],j) f
источник