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

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)) амортизированное время на запрос для извлечения элемента. Стоимость установки балансировки включена в амортизированную стоимость, потому что она фактически является постоянной величиной, которая, как показано в уравнениях в ответе, исчезает (затмевается) из-за бесконечного объема работы, которую вы выполняете. (* если вы добавляете к нему элементы, вам нужно самобалансирующееся двоичное дерево поиска, одним из которых является дерево сплайнов)