Интуиция за сплайсом (самобалансирующиеся деревья)

Question

Я читаю основы splay-деревьев.Амортизированная стоимость операции составляет O (log n) в течение n операций.Некоторая грубая основная идея заключается в том, что когда вы получаете доступ к узлу, вы выводите его на экран, т.е. вы берете его в корневой каталог, так что в следующий раз к нему быстро получат доступ, а также, если узел был глубоким, это улучшит баланс дерева.

Я не понимаю, как дерево может выполнить амортизированный O (log n) для этого примера ввода:

Скажем, дерево из n узлов уже построено.Мои следующие n операций - это n reads.Я получаю доступ к глубокому узлу, скажем, на глубине n.Это занимает O (N).Правда, что после такого доступа дерево станет сбалансированным.Но говорите каждый раз, когда я получаю доступ к самому последнему глубокому узлу.Это никогда не будет меньше, чем O (log n).тогда как мы можем когда-нибудь компенсировать первую дорогостоящую операцию O (n) и представить амортизированную стоимость каждого чтения как O (log n)?

Спасибо.

Answer 1

Предполагая, что ваш анализ правильный, и операции: O(log(n)) для доступа и O(n) в первый раз ...

Если вы всегда обращаетесь к самому нижнему элементу (используя своего рода оракул наихудшего случая)последовательность a обращений займет O(a*log(n) + n).И, таким образом, амортизированная стоимость на операцию составляет O((a*log(n) + n)/a) = O(log(n) + n/a) или просто O(log(n)), поскольку число обращений становится большим.

Это определение асимптотической производительности среднего времени / времени / пространства, а такженазывается «амортизированная производительность / время / пространство».Вы случайно думаете, что один O(n) шаг означает, что все шаги по крайней мере O(n);один такой шаг - это только постоянный объем работы в долгосрочной перспективе;O(...) скрывает то, что на самом деле происходит, и принимает предел [total amount of work] / [queries] = [average ("amortized") work per query].

Это никогда не будет меньше O (log n).

Это должно быть для получения O(log n) средней производительности.Для интуиции может пригодиться следующий веб-сайт: http://users.informatik.uni -halle.de / ~ jopsi / dinf504 / chap4.shtml , в частности, изображение http://users.informatik.uni -halle.de / ~ jopsi /dinf504 / splay_example.gif - кажется, что во время выполнения операций O(n) вы перемещаете путь, который вы искали, сужая его к вершине дерева.Вероятно, у вас есть только конечное число таких O(n) операций, которые нужно выполнить, пока все дерево не будет сбалансировано.

Вот еще один способ подумать об этом:

Рассмотрим несбалансированное двоичное дерево поиска.Вы можете потратить O(n) времени на его балансировку.Предполагая, что вы не добавляете к нему элементы *, для извлечения элемента требуется O(log(n)) амортизированное время для каждого запроса.Затраты на настройку балансировки включены в амортизированную стоимость, потому что она фактически является постоянной величиной, которая, как показано в уравнениях в ответе, исчезает (затмевается) из-за бесконечного объема работы, которую вы выполняете.(* если вы добавляете к нему элементы, вам нужно самобалансирующееся бинарное дерево поиска, одним из которых является дерево сплайнов)