2

我正在解决段树和四叉树相关的问题；虽然我注意到在段树中，我们将一维数组分成2 个（2^1）段并递归地执行此操作，直到基本情况到达。同样，在四叉树中，我们将 2D 网格细分为4 (2^2)同样，在四叉树中，我们在每一步所有这些分治机制都是为了实现对数时间复杂度。没有冒犯的意思！

但是为什么我们不将数组细分为4 (4^1) 个或更多部分而不是分段树中的 2 个部分呢？为什么我们不将网格分成16 (4^2) 个部分而不是 4 个？通过这样做，我们可以实现O(log(N))性能，但它会更好log，因为log(N)(base 4) 比log(N)(base 2) 更好。

我知道在这种情况下，实施会有点困难。是否存在内存开销问题？还是什么？

如果我在任何地方错了，请纠正我。谢谢！

4

2 回答 2

1

日志 4 (N) = 日志 2 (N) / 日志 2 (4) = 日志 2 (N) / 2

一般来说，时间复杂度都是 O(logn) ，而四段比两段更难维护。其实，（在acm/icpc中）两段代码很容易编码，工作就够了。

于 2014-08-04T13:48:06.420 回答
1

它实际上不会工作得更快。假设我们将其分为 4 个部分。然后我们必须在每个节点中合并 4 个值而不是 2 个值来回答查询。假设合并 4 个值需要 3 倍的时间（例如，要获得最多 2 个数字，我们需要 1 次调用 max 函数，但要获得最多 4 个值需要 3 次调用），我们有 log4(n) * 3 > log2(n) * 1。此外，它会更难实现（需要考虑更多的情况等等）。

于 2014-08-04T13:49:58.787 回答