分而治之

Question

一直在学习分而治之，我正在努力去理解一个概念。如果我们有一个排序的数组，并希望做一些任务....我们得到的公式

T(n) = a (n/b) * O(n) 

如果我们使用b = 2（二叉树），这意味着每个子阵列制作成两个子阵......我们得到

T(n) = 2 (n/2) * O(n) - >和掌握规则running time = O(n * logn)

现在，如果我们使用b = 3（三进制树），这意味着每个子阵列制作成三个子阵，我们得到

T(n) = 3 (n/3) * O(n) - >这意味着running time = O(n * logn)

问题：

如果运行时间更长，如果我们让更多的分裂？

无论我的树有多大，为什么我会一直保持相同的运行时间？

Answer 1

想想这样。你有一个长度为n的数组。在树的每个级别，您都细分该数组。但是总的来说，无论你如何细分，它仍然有其他元素。

在家长一级你做n工作。在你做的每个孩子n/X工作，但你做它X次，所以再次它的n工作。

Answer 2

这很简单。无论树的程度如何，下一级进程的总和都是一样的。如你所知，树的程度越大，子节点的处理越小。和下一级过程相同。但它只适用于闲置状态。在实际中，由于递归函数调用，更多树的运行时间比树的更小程度慢。