math - 分而治之

Question

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

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

如果我们使用b = 2(二叉树) ，这意味着每个子数组又被分成两个子数组......我们得到

T(n) = 2 (n/2) * O(n)--> 并通过主规则running time = O(n * logn)

现在如果我们使用b = 3(tri-nary tree) ，这意味着每个子数组都被分成三个子数组，我们得到

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

问题：

如果我们进行更多拆分，运行时间是否应该更长？

为什么不管我的树有多大，我的运行时间都一样？

Answer 1

这样想吧。你有一个长度n数组。在树的每个级别，您都细分该数组。但是总体上还是有n元素的，不管怎么细分。

在父母级别，您确实n工作。在每个孩子身上，你都在n/X工作，但你做X的次数，所以这又是n工作。

Answer 2

很简单。无论树的程度如何，下一级过程的总和都是相同的。如您所知，树的度数越大，子节点处的进程越小。并且下一级过程的总和是相同的。但它仅在空闲条件下有效。实际上，由于递归函数调用，多级树的运行时间比少级树慢。