Я не могу дать полный ответ, но это может быть подсказка в правильном направлении.
Основные идеи :
- Предположим, выВычислили среднее значение
n чисел a_1,...,a_n, тогда это среднее значение avg=(a_1+...+a_n)/n.Если мы теперь заменим a_n на b, мы можем пересчитать новое среднее значение следующим образом: avg'=(a_1+...+a_(n-1)+b)/n или - проще - avg'=((avg*n)-a_n+b)/n.Это означает, что если мы заменим один элемент, мы сможем пересчитать среднее значение, используя исходное среднее значение, с помощью простых быстрых операций, и не нужно повторять все элементы, участвующие в среднем.
Примечание: я предполагаю, что вы хотите иметь log n соседей с каждой стороны, то есть всего у нас есть 2 log(n) соседей.Вы можете просто адаптировать его, если хотите иметь log(n) соседей.Более того, поскольку log n в большинстве случаев не будет натуральным числом, я предполагаю, что вы говорите о floor(log n), но я просто напишу log n для простоты.
Главное, что яЯ рассматриваю тот факт, что вы должны сказать среднее значение вокруг элемента x в O (1).Таким образом, я полагаю, вы должны каким-то образом предварительно вычислить это среднее значение и сохранить его.Итак, я бы сохранил в узле следующее:
- x value
- y value
- среднее значение вокруг
Обратите внимание, что update(x,y) работает строго в O (log n), если у вас есть такая структура: если вы обновляете элемент x до высоты y, вам нужно учитывать 2log(n) соседей, на среднее значение которых влияет это изменение.Вы можете пересчитать каждое из этих средних значений в O (1):
Предположим, что update(x,y) влияет на элемент b, среднее значение которого также необходимо обновить.Затем вы просто умножаете average(b) на количество соседей (2log(n), как указано выше).Затем мы вычитаем старый y-value элемента x и добавляем новое (обновленное) y -значение x.После этого мы делим на 2 log(n).Это гарантирует, что теперь у нас есть обновленное среднее для элемента b.Это включало только некоторые вычисления и, таким образом, может быть сделано в O (1).Поскольку у нас есть 2log n соседей, update работает в O(2log n)=O(log n).
Когда вы вставляете новый элемент e, вам необходимо обновить среднее значение всех элементов, затронутых этим новым элементом e,Это по существу сделано как в подпрограмме update.Однако вы должны быть осторожны, когда log n (или точно floor(log n)) меняет свое значение.Если floor(log n) остается тем же самым (что в большинстве случаев будет), тогда вы можете просто выполнить аналогичные действия, описанные в update, однако вам придется «удалить» высоту одного элемента и «добавить»высота вновь добавленного элемента.В этих «хороших» случаях время выполнения снова строго O(log n).
Теперь, когда меняется floor(log n) (с увеличением на 1), вы должны выполнить обновление для all элементы.То есть вы должны выполнить операцию O (1) для n элементов, что приведет к продолжительности работы O(n).Тем не менее, очень редко бывает, что floor(log n) увеличивается на 1 (вам нужно удвоить значение n, чтобы увеличить floor(log n) на 1 - при условии, что мы говорим о log для базы 2, что не является редкостьюв области компьютерных наук).Мы обозначаем это время как c*n или просто cn.
Таким образом, давайте рассмотрим последовательность вставок: первая вставка требует обновления: c*1, вторая вставка требует обновления: 2*c,В следующий раз, когда происходит дорогая вставка, это четвертая вставка: 4*c, затем восьмая вставка: 8c, шестая вставка: 16*c.Расстояние между двумя дорогостоящими вставками удваивается каждый раз:
insert # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ..
cost 1c 2c 1 4c 1 1 1 8c 1 1 1 1 1 1 1 16c 1 1 ..
Поскольку remove не требуется, мы можем продолжить наш анализ без каких-либо «особых случаев» и рассматривать только последовательность вставок.Вы видите, что большинство вставок стоят 1, в то время как немногие стоят дорого (1,2,4,8,16,32, ...).Таким образом, если мы имеем в общей сложности m вставок, у нас есть примерно 1093 * дорогих вставок и примерно 1094 * дешевых вставок.Для простоты мы предполагаем просто m дешевые вставки.
Затем мы можем вычислить стоимость для m вставок:
log m
----
\ i
m*1 + / 2
----
i=0
m*1 считает дешевые операции, сумму дорогих. Можно показать, что все это самое большее 4m (на самом деле вы можете даже лучше показать более точные оценки, но для нас этого достаточно).
Таким образом, мы видим, что m общая стоимость операций вставки не превышает 4m. Таким образом, стоимость одной операции вставки составляет самое большее 4m/m=4, то есть O(1) амортизируется.
Итак, осталось 2 вещи:
- Как сохранить все записи?
- Как инициализировать структуру данных в O (n)?
Я предлагаю сохранить все записи в пропущенном списке или в каком-либо дереве, которое гарантирует логарифмические операции поиска (в противном случае для вставки и обновления требуется более O (log n) для поиска правильной позиции). Обратите внимание, что структура данных должна быть встраиваемой в O (n) - что не должно быть большой проблемой, если элементы отсортированы по их x-координате.
Чтобы инициализировать структуру данных в O (n), я предлагаю начать с элемента с индекса log n и вычислить его среднее значение простым способом (суммируя соседей 2log n, делите на 2 log n).
Затем вы перемещаете индекс дальше и вычисляете average(index), используя average(index-1): average(index)=average(index-1)*log(n)-y(index-1-log(n))+y(index+log(n)).
То есть мы придерживаемся подхода, аналогичного обновлению. Это означает, что вычисление средних значений стоит O(log n + n*1)=O(n). Таким образом, мы можем вычислить средние значения в O (n).
Обратите внимание, что вы должны принять во внимание некоторые детали, которые я здесь не описал (например, пограничные случаи: элемент с индексом 1 не имеет log(n) соседей с обеих сторон - как вы поступите с этим?).