algorithm - 比较 splay 树效率的最佳方法是什么？

Question

我已经实现了几个 splay tree算法。

比较它们的最佳方式是什么？

添加随机节点时比较执行时间是否是一个好的开始？

我还实现了一个二叉搜索树，用于跟踪每个节点的访问量。我编写了一个 optimize() 方法来创建最佳二叉搜索树。
如果我们不打算修改搜索树，并且我们确切地知道每个项目将被访问的频率，我们可以构造一个最优二叉搜索树，这是一个搜索树，其中查找一个项目的平均成本(预期搜索成本)被最小化。
我怎样才能将其纳入八字树的比较中？

Answer 1

我喜欢实证方法。

在这种方法中:

1. 创建一组不同长度的随机典型数据集。
2. 运行每个实现并找出每个的执行时间。
3. 使用Hypothesis testing找出一种实现是否比另一种更好的方法。在这里，null hypothesis (H₀) 是“平均来说，这两个实现应该花费相同的时间来执行。
4. 从第 3 步得出结论，一种实现方式优于另一种实现方式，概率为 1-p(其中 p 是您的 p_value )。

附言Wilcoxon test被认为是一个很好的算法，并且在文献和研究中大量使用来比较两种算法。