Я попытался понять амортизированную сложность и сделал несколько поисков в сети, но пока не нашел хорошего ресурса.Что такое амортизированная сложность в splay tree?
Так может ли кто-нибудь объяснить, что такое амортизированная сложность и как она становится O (lg n) в дереве splay за операцию?
Любая операция, выполняемая на деревьях, вставляет ли вставлять delete..etc в стоимость доминирует операция воспроизведения. следовательно, учитывается стоимость только операции воспроизведения, которая представляет собой поворот, выполняемый на узле, который должен быть воспроизведен.
The amortized function is given by a=c+3Rfinal(v)-3Rinitial(v)
где а амортизированная стоимость, с является фактической стоимостью и Rfinal есть ранг после операции скошенной и Rinitial есть ранг узла перед вращением. (Ранг любого узла задается высотой его поддерево, т. е. log | S |, где S - число узлов, внедренных под него)
Теперь рассмотрим наихудший случай, когда узел, который должен быть разнесен, является листом, поэтому его начальный ранг задается равным 0. После того, верхний, т. е. в качестве корневого узла его ранг становится log n, где n - общее число узлов в дереве.
a<= 2+3logn-0
O(logn).
[Амортизированный анализ] (http://en.wikipedia.org/wiki/Amortized_analysis). [Анализ эффективности дерева splay] (http://en.wikipedia.org/wiki/Splay_tree#Analysis). После того, как вы переварили это, вернитесь и задайте * конкретные * вопросы. –