最近递归找到max的时间复杂度是多少

我只是想确保我正朝着正确的方向前进。我想通过递归分割找到数组的最大值，并找到每个单独数组的最大值。因为我分裂它，它会是2 * T（n/2）。而且因为我必须对2个数组做最后的比较，所以我有T（1）。所以将我的递推关系是这样的：最近递归找到max的时间复杂度是多少

T = {2 * T（N/2）+ 1，当n> = 2; T（1），当n = 1;

因此，我的复杂性是Theta（nlgn）？

来源

2011-04-26 Dan

您编写的公式似乎是正确的，但您的分析并不完美。

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

对于第i次迭代，你会得到：

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

现在你想知道我做N/2^i等于1（或几乎任何恒定的，如果有什么你喜欢），所以你达到n = 1的最终条件。这将是解决方案n/2^I = 1 - > I = Log2（n）。植物它方程钛在，你会得到：

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

，你会得到T（N）= O（N + LOG 2（N）（就像@bdares说）= O（N）（就像@ bdares说）

来源

2011-04-26 09:15:20 Neowizard

感谢您的澄清 – Dan 2011-04-26 09:31:28

写O（n + log（n））是否正常？看起来像O（n）就足够了，在* every *事件中。事实上，为什么要像这样软球呢？我觉得写O（n + log（n）），虽然没有错，但很愚蠢。我们不为Bubblesort写O（n^2 + n）。我错过了什么吗？如果你只是用于说明目的，那么确定;我想对我来说有点不可思议，因为我没有看到最后一步......所以如果是这样的话，只要把它当作批评风格而不是内容。 – Patrick87 2011-10-21 16:11:40

@bdares你说得对。我应该添加最后一步。为避免混淆，我避免跳过（n + log（n））部分，但我应该确保添加最后一部分。 – Neowizard 2011-10-22 06:39:11

不，不...您每次递归都需要O（1）次。

有几个？

有N片叶子，所以你知道它至少是O（N）。

你需要比较几个才能找到绝对最大值？那是O（log（N））。

把它们加在一起，不要繁殖。 O（N + log（N））是你的时间复杂度。

来源

2011-04-26 08:51:11 bdares

哦，我看到了，我有点困惑，因为它看起来类似于合并排序，所以是复发关系对还是错？ – Dan 2011-04-26 08:57:28

呃..我真的很模糊，但它看起来是正确的。水平将加1，然后2，然后4，然后8，等等...所以我错了，每步需要1 + 2 + 4 + 8 + ... + 2^log（n）时间，因此将花费O（2 * n）时间，这是O（n）时间。顺便说一句，与O（N + log（N））相同也是O（n），但第一种解释是错误的。 – bdares 2011-04-26 09:12:29

最近递归找到max的时间复杂度是多少

回答

相关问题