递归寻找最大值的时间复杂度是多少？
递归寻找最大值的时间复杂度是多少？
提问于 2011-04-26 08:26:32
我只是想确定我走的方向是对的。我希望通过递归地分割数组来找到数组的最大值，并找到每个单独数组的最大值。因为我要分裂它，所以它是2*T(n/2)。因为我必须在两个数组的末尾进行比较，所以我得到了T(1)。我的复发关系会是这样吗？
T={ 2*T(n/2) + 1，当n>=2时，T(1)，n= 1；
因此我的复杂性将是Theta(nlgn)？
回答 2
Stack Overflow用户
回答已采纳
发布于 2011-04-26 09:15:20
你写的公式似乎是对的，但你的分析并不完美。
T = 2*T(n/2) + 1 = 2*(2*T(n/4) + 1) + 1 = ...在第一次迭代中，您将得到：
Ti(n) = 2^i*T(n/2^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 said) = O(n) (就像@bdares said)
Stack Overflow用户
发布于 2011-04-26 08:51:11
不，不..。每次递归都要花费O(1)时间。
一共有多少个？
有N个叶子，所以你知道它至少是O(N)。
您需要比较多少才能找到绝对最大值？这是O(log(N))。
把它们加在一起，不要乘以。O(N+log(N))是你的时间复杂度。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5787752
复制相关文章
相似问题
腾讯云开发者
