我想尝试在 Splay 树上执行最坏情况的序列。
但是 Splay-trees 的最坏情况序列是什么？考虑到插入树的键，有什么方法可以轻松计算这个序列？
任何人都可以帮助我吗？
问问题
468 次
1 回答
0
除非有人纠正我，否则我会选择“没有人真正知道展开树上的最坏情况系列操作是什么，或者这种情况下的复杂性是什么”。
虽然我们确实知道许多关于伸展树效率的结果，但我们实际上对如何限制伸展树的时间复杂度知之甚少。有一个称为动态最优性猜想的猜想，它说在最坏的情况下，展开树上任何足够长的操作系列所花费的时间不会超过该系列上可能的最佳自调整二叉搜索树的恒定时间的操作。我们在试图证明这一点时遇到的挑战之一是，没有人真正知道如何确定所有输入的最佳 BST 的成本。另一个是很难找到展开树的各种输入组合的运行时间上限——到目前为止，没有人知道将展开树视为双端队列是否需要时间 O(n)！
希望这可以帮助！
于 2015-07-30T16:11:58.943 回答