Алгоритм линейного времени нахождения сдвинутого максимума

11

Предположим, что нам дан массив содержащий неотрицательные целые числа (не обязательно различающиеся).A[1..n]

Пусть будет отсортированным в неубывающем порядке. Мы хотим вычислить BA

m=maxi[n]B[i]+i.

Очевидным решением является сортировка A а затем вычисление m . Это дает алгоритм, который работает во времени O(nlgn) в худшем случае.

Можно ли сделать лучше? Можем ли мы вычислить m за линейное время?


Мой главный вопрос - тот, что выше. Но было бы интересно узнать о следующем обобщении проблемы.

Пусть B будет A отсортированным согласно некоторому оракулу сравнения а f - функция, заданная оракулом. Учитывая A и оракулы для и f , что мы можем сказать о времени, необходимом для вычисления m=maxi[n]f(B[i],i) ?

Мы все еще можем вычислить m за O(nlgn) времени. Но можем ли мы доказать суперлинейную нижнюю оценку для этого обобщенного случая?

Если ответ «да», имеет ли место нижняя граница, если предположить, что - это обычный порядок на целых числах, а - «хорошая» функция (монотонная, полиномиальная, линейная и т. Д.)?f

Кава
источник

Ответы:

10

Мы можем вычислить за линейное время.m

Для простоты предположим, что массивы основаны на 0: , . Мы хотим вычислить .A[0..n1]B[0..n1]m=maxiB[i]+i

Пусть . Очевидно, .max=maxiA[i]maxm

Пусть будет после сортировки. Если то A[j]B[k]A[j]maxn

B[k]+kB[k]+(n1)=A[j]+(n1)(maxn)+(n1)=max1<maxm.

Поэтому мы можем игнорировать когда . Нам нужно только рассмотреть числа в диапазоне .A[j]A[j]maxn[maxn,max]

Мы можем использовать счетную сортировку, чтобы отсортировать числа в которые находятся в диапазоне за линейное время, и использовать отсортированный список для вычисления .A[maxn,max]m

Марцио де Биаси
источник
... ммм ... но какова стоимость C [x] = C [x] +1?!?
Марцио Де Биаси
1
есть ли проблема с вашим ответом? потому что мне это кажется подходящим: вы говорите, что мы заботимся только об элементах массива со значениями в , поэтому мы можем использовать счетную сортировку. Это работает для общей задачи всякий раз, когда для всех . [Mn,M]|f(B[i],i)B[i]|=O(n)i
Сашо Николов
Спасибо @Marzio. :) Я слегка отредактировал твой ответ для ясности. Не стесняйтесь откатить мое редактирование или редактировать дальше.
Каве
1
Это решение, кажется, работает и для любого где для всех и , . f(x,i)xin|f(x,i)x|=O(n)
Каве
@Kaveh: редактировать в порядке! Я написал ответ быстро, и я даже не был уверен в его правильности: -S
Марцио Де Биаси
-1

Если массив состоит из различных целых чисел, то , поскольку расстояние между соседними элементами в не менее ; ситуация более интересна, когда они не должны быть отчетливыми.Am=max(A)+1B1

Для более общего вопроса, представьте ситуацию, в которой «интересна» только тогда, когда . Кажется возможным построить аргумент противника, который заставляет вас запрашивать для всех прежде чем вы сможете узнать , поэтому вам нужно отсортировать , чтобы найти ответ, который берет сравнений. (Есть некоторые сложности, так как это может быть случай, когда мы можем проверить, является ли в постоянном, а не линейном времени, путем запроса .) Это имеет место, даже если - многочлен (высокой степени).f(B[i],j)i=jf(B[i],i)imaxif(B[i],i)AΩ(nlogn)A[i]=B[j]f(A[i],j)f

Юваль Фильмус
источник
1
Что, если A имеет n - 1 ноль и один ноль? Тогда ответ будет n, а не 1.
Григорий Ярославцев
Привет юваль Там может быть повторен номер в . Как сказал Григорий, решение, похоже, не работает. A
Каве
Я думаю, что вижу вашу идею для аргумента нижней границы: учитывая мы можем быстро вычислить используя пары запросов, составленные для алгоритмом, решающим задачу за время . Мы можем убедиться, что алгоритм запрашивает для всех но мы не можем убедиться, что он не запрашивает другие пары. Однако мы можем установить для других пар как различимое значение, чтобы мы могли отбросить эти пары. ABfo(nlgn)f(B[i],i)f
Каве