我只是想确保我朝着正确的方向前进.我想通过递归拆分找到数组的最大值,并找到每个单独数组的最大值.因为我分裂它,它将是2*T(n/2).因为我必须在最后为2个数组进行比较,所以我有T(1).那么我的复发关系是这样的:
当n> = 2时T = {2*T(n/2)+ 1;当n = 1时T(1);
因此我的复杂性将是Theta(nlgn)？
您编写的公式似乎是正确的，但您的分析并不完美。
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所说） = O(n) （就像@bdares所说）