递归查找最大值的时间复杂度是多少？

Question

我只想确认我走在正确的方向上。我想通过递归地拆分数组并找到每个单独数组的最大值来找到数组的最大值。因为我正在拆分它，所以复杂度是2*T(n/2)。并且因为我必须在结束时比较这两个数组，所以有T(1)。那么我的递归关系应该像这样：

T = { 2*T(n/2) + 1, 当 n>=2 ; T(1), 当 n=1;

因此，我的时间复杂度为Theta(nlgn)。

- Dan

Answer 1

你所写的公式似乎差不多正确，但你的分析并不完美。

T = 2*T(n/2) + 1 = 2*(2*T(n/4) + 1) + 1 = ...

对于第 i 次迭代，您将获得以下内容：

Ti(n) = 2^i*T(n/2^i) + i

现在你想知道哪个i使得n/2^i等于1（或者其他常数，如果你喜欢），以便到达n=1的终止条件。 这将是n/2^I = 1的解答-> I = Log2(n)。把它放进Ti的公式中，你将得到：

TI(n) = 2^log2(n)*T(n/2^log2(n)) + log2(n) = n*1+log2(n) = n + log2(n)

当你得到T(n) = O(n + log2(n))时（就像@bdares所说的那样），你可以得到T(n) = O(n)（就像@bdares所说的那样）。

- Neowizard

---

写O(n + log(n))是正常的吗？似乎在每个事件中，O(n)就足够了。实际上，为什么要这样软化它呢？我觉得写O(n + log(n))虽然不是错的，但很傻。我们不会为Bubblesort写O(n^2 + n)。我有什么遗漏的吗？如果你只是用它来说明，那好吧；我想我有点奇怪，没有看到最后一步被执行...所以如果是这种情况，就把它看作是对风格而不是内容的批评。 - Patrick87

@bdares 你说得对。我应该加上最后一步。我在解释这个问题时避免跳过 (n + log(n)) 部分以避免混淆，但我应该确保也加上最后一部分。 - Neowizard

Answer 2

不，你每次递归都需要O(1)时间。

有多少个叶子节点？

有N个叶子节点，所以至少需要O(N)的时间。

要找到绝对最大值，需要比较多少个叶子节点？这是O(log(N))的。

将它们加在一起，不要相乘。你的时间复杂度是O(N+log(N))。

- user684934

---

哦，我明白了。我有点困惑，因为它看起来很像归并排序。那么递归关系是正确的还是错误的？ - Dan

嗯...我对此有些模糊，但看起来是正确的。每个级别将增加1、2、4、8等等...所以我错了。每个步骤需要1+2+4+8+...+2^log(n)的时间，因此需要O(2*n)的时间，即O(n)的时间。顺便说一下，O(N+log(N))也是O(n)，但第一个解释是错误的。 - user684934