我正在解决线段树和四叉树相关的问题；虽然我注意到，在线段树中，我们将一维数组分成 2 (2^1) 段，并递归地执行此操作，直到基本情况到达。类似地，在四叉树中，我们在每一步中将 2D 网格分割为 4 (2^2) 段。所有这些分治机制都是为了实现对数时间复杂度。无意冒犯!
但是为什么我们不将数组分割为 4 (4^1) 部分或更多部分，而不是线段树中的 2 部分呢？为什么我们不将网格分成 16 (4^2) 部分而不是 4 部分？通过这样做，我们可以实现 O(log(N)) 性能，但它会是更好的 log 作为 log(N)(以 4 为底)优于 log(N)(以 2 为底)。
我知道在这种情况下，实现起来会有点困难。是否存在内存开销问题？或者什么？
如果我有什么错误的地方，请纠正我。谢谢!
最佳答案
它实际上不会运行得更快。假设我们将其分为 4 部分。然后我们必须在每个节点中合并 4 个值而不是 2 个值来回答查询。假设合并 4 个值需要 3 倍的时间(例如，要获得 2 个数字的最大值，我们需要 1 次调用 max 函数，但要获得 4 个值的最大值，则需要 3 次调用)，我们有 log4(n) * 3 > log2(n) * 1。而且，实现起来会比较困难(要考虑更多的情况等等)。
关于algorithm - 优于 O(log(N)) 以 2 为底的情况，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25120083/