我正在阅读伸展树的基础知识。一次操作的摊销成本是 O(log n) 超过 n 次操作。一些粗略的基本想法是，当您访问一个节点时，您将其展开，即您将其带到根目录，以便下次快速访问它，并且如果节点很深，它会增强树的平衡性。
我不明白树如何为此示例输入执行摊销 O(log n)：
假设已经构建了一个包含 n 个节点的树。我接下来的 n 次操作是 n 次读取。我访问深度为 n 的深度节点。这需要 O(n)。确实，在此访问之后，树将变得平衡。但是说每次我访问最新的深度节点。这永远不会小于 O(log n)。那么我们如何才能补偿第一次昂贵的 O(n) 操作并将每次读取的摊销成本变为 O(log n)？
谢谢。
假设您的分析是正确的并且操作是O(log(n))每次访问和O(n)第一次......
如果您总是访问最底部的元素（使用某种最坏情况的 oracle），则a访问序列将需要O(a*log(n) + n). 因此，每次操作的摊销成本为O((a*log(n) + n)/a)=O(log(n) + n/a)或O(log(n))随着访问次数的增加而增加。
这是渐近平均情况性能/时间/空间的定义，也称为“摊销性能/时间/空间”。您不小心认为一个O(n)步骤意味着所有步骤至少是O(n)；从长远来看，其中一个步骤只是恒定的工作量；theO(...)隐藏了真正发生的事情，这是限制[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))每次查询都需要分摊时间来获取元素。平衡设置成本包含在摊销成本中，因为它实际上是一个常数，正如答案中的方程式所示，由于您正在做的无限量的工作而消失（相形见绌）。（*如果你确实添加了元素，你需要一个自平衡二叉搜索树，其中之一是展开树）
