递归求最大值的时间复杂度是多少
我只是想确保我正朝着正确的方向前进。我想通过递归拆分数组来找到数组的最大值，并找到每个单独数组的最大值。因为我要分割它，所以它将是 2*T(n/2)。因为我必须在最后对 2 个数组进行比较，所以我有 T(1)。 那么我的递归关系会是这样的：
T = { 2*T(n/2) + 1，当 n>=2 时；T(1)，当 n = 1 时；
因此我的复杂度是 Theta(nlgn)？
I just wanted to make sure I'm going in the right direction. I want to find a max value of an array by recursively splitting it and find the max of each separate array. Because I am splitting it, it would be 2*T(n/2). And because I have to make a comparison at the end for the 2 arrays, I have T(1).
So would my recurrence relation be like this:
T = { 2*T(n/2) + 1, when n>=2 ;T(1), when n = 1;
and and therefore my complexity would be Theta(nlgn)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您编写的公式似乎是正确的，但您的分析并不完美。
对于第 i 次迭代，您将得到：
现在您想知道 i 的 n/2^i 等于 1 （或者几乎任何常数，如果您愿意），这样您就达到了 n=1 的最终条件。
这将是 n/2^I = 1 -> 的解I = Log2(n)。将其代入 Ti 的方程中，您将得到：
T(n) = O(n + log2(n) （就像 @bdares 所说）= O(n) （就像 @bdares 所说）
The formula you composed seems about right, but your analysis isn't perfect.
For the i-th iteration you'll get:
now what you want to know for which i does n/2^i equals 1 (or just about any constant, if you like) so you reach the end-condition of n=1.
That would be the solution to n/2^I = 1 -> I = Log2(n). Plant it in the equation for Ti and you get:
and you get T(n) = O(n + log2(n) (just like @bdares said) = O(n) (just like @bdares said)
不，不...每次递归都花费 O(1) 时间。
有多少人？
有 N 个叶子，所以你知道它至少是 O(N)。
您需要比较多少个才能找到绝对最大值？那是 O(log(N))。
将它们加在一起，不要相乘。 O(N+log(N)) 是你的时间复杂度。
No, no... you are taking O(1) time for each recursion.
How many are there?
There are N leaves, so you know it's at least O(N).
How many do you need to compare to find the absolute maximum? That's O(log(N)).
Add them together, don't multiply. O(N+log(N)) is your time complexity.