这些基于树的算法的复杂性是什么？

Question

假设我们有一个平衡的二进制树，它代表了嵌套子集中一组$ n $点的递归分区。树的每个节点代表一个子集，具有以下属性：由同一父母的两个子节点表示的子集是不相交的，它们的联合等于父母代表的子集。根代表完整的点，每个叶子代表一个独特的点。因此，树上有$ log n $级别，树的每个级别代表将点分配为越来越高的粒度水平。

现在假设我们有两种算法，每种算法都在树的所有子集上运行。第一个在每个节点处的$ o（d^2）$操作，其中$ d $是该节点表示的子集的大小。第二个在每个节点上dis $ o（d log d）$ operations。这两种算法的最坏情况是什么？

我们可以轻松地将第一个算法绑定为$ o（n^2 log n）$，因为它可以在树的$ log n $级别上进行$ o（n^2）$工作。同样，通过类似的推理，我们可以将第二算法绑定为$ o（n log ^2 n）$。

问题是，这些界限是否紧密，还是我们可以做得更好？我们如何证明它？

Answer 1

应用 师父定理.

第一个算法需要$ o（n^2）$时间，因为您的基本复发是

[t（n）= 2t（n/2） + n^2

您提到的第二个算法采用$ n log^2n $时间。如果您的每个节点的工作如图所示（并且很紧），则此界限也很紧。

更新：正如评论者指出的那样，这里的假设是树是体重平衡的：每个孩子的父母有一半。这将暗示您指示的log n高度绑定，但并不暗示它。