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

Question

我已经实现了几种展开树算法。

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

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

我还实现了一个二叉搜索树，它跟踪每个节点的访问量。我写了一个optimize()创建最优二叉搜索树的方法。
如果我们不打算修改搜索树，并且我们确切地知道每个项目将被访问的频率，我们可以构建一个最优二叉搜索树，这是一个搜索树，其中查找一个项目的平均成本（预期搜索成本）最小化。
我怎样才能在比较伸展树时涉及到这个？

Answer 1

我喜欢经验主义的方法。

在这种方法中：

1. 创建一堆不同长度的随机典型数据集。
2. 运行每个实现并找出每个实现的执行时间。
3. 使用假设测试方法来确定一种实现是否比另一种更好。在这里，原假设(H ₀ ) 是“平均而言，两个实现应该花费相同的时间来执行。
4. 从第 3 步得出结论，一种实现比另一种更好，具有概率1-p（p您的p_value在哪里）。

PS Wilcoxon 测试被认为是一个很好的测试，并且在文献和研究中被大量用于比较两种算法。