我正在阅读八字树的基础知识。一个操作的摊销成本是 n 个操作的 O(log 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)；从长远来看，一个这样的步骤只是一个恒定的工作量； O(...) 隐藏了真正发生的事情，它正在限制 [total amount of work]/[queries]=[每个查询的平均(“摊销”)工作量]。
This will never be less than 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)) 摊销时间。平衡设置成本包含在摊余成本中，因为它实际上是一个常数，正如答案中的方程式所示，它会随着您所做的无限工作量而消失(相形见绌)。 (*如果你确实要往里面加元素，你需要一个自平衡的二叉搜索树，其中一个是splay树)
关于algorithm - splay 树(自平衡树)背后的直觉，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5853958/