java - 检查java中splay树操作的复杂性

Question

我已经用 Java 实现了 splay 树(插入、搜索、删除操作)。现在我想检查算法的复杂度是否为 O(logn)。有没有办法通过改变输入值(节点数)并检查运行时间(以秒为单位)来检查这一点？比如，输入 1000、100000 之类的值并检查运行时间，或者还有其他方法吗？

Answer 1

严格来说，您无法通过针对 n 的某些值运行算法来找出算法的时间复杂度。 .假设您已针对值 n_1, n_2, ..., n_k 运行它.如果算法使n^2任何n <= max(n_1, ..., n_k)的操作正是10^100 n 的任何较大值的操作，它具有恒定的时间复杂度，即使从您所拥有的点来看它看起来像二次方。

但是，您可以评估在大小为 n 的输入上完成所需的操作数。 (我什至不会在这里称它为时间复杂度，因为后者有严格的形式定义)通过在 n 的某些值上运行并查看比率 T(n1) / T(n2)和 n1 / n2 .但即使是“真实”算法(从某种意义上说它不是第一段中描述的病态情况)，您也应该注意输入的“结构”(例如，采用作为枢轴的第一个元素对于随机输入平均在 O(n log n) 中运行，因此如果生成不同大小的随机数组，它看起来像 O(n log n)。但是，对于反向排序数组，它在 O(n^2) 中运行)。

总而言之，如果您需要从实际角度确定它是否足够快，并且您知道算法的典型输入是什么样子，您可以尝试生成不同大小的输入，看看效果如何执行时间增加。

但是，如果您需要数学意义上的运行时界限，则需要从数学上证明算法的某些属性和界限。

在你的情况下，我会说对随机输入进行测试可能是一个合理的想法(因为有一个数学证明，对于一个 splay 树，一个操作的时间复杂度是 O(log n))，所以你只需要检查您实现的树确实是一棵正确的拉伸(stretch)树。一个注意事项:我建议尝试不同的查询模式(比如按排序/倒序插入元素等等)，因为只要输入是“随机的”，即使是不平衡的树也可以工作得非常快。