如何找到递归关系的 运行 时间？
How can i find a running time of a recurrence relation?
这个递归关系的运行时间是O(nlogn)。由于我是算法的新手，我该如何用数学来证明它？
T(n) = 2⋅T(n/2) + O(n)
T(n) = 2 ( 2⋅T(n/4) + O(n) ) + O(n) // since T(n/2) = 2⋅T(n/4) + O(n)
到目前为止我可以看到，如果我假设 n 是 2 的幂，例如 n = 2<sup>m</sup> ，那么也许我可以证明这一点，但我没有得到清晰的画面。谁能帮帮我？
如果你使用主定理，你会得到你期望的结果。
如果你想证明这个 "by hand"，你可以很容易地通过假设 n = 2<sup>m</sup> 来证明这一点2 的幂（正如你已经说过的）。这会将您带到
T(n) = 2⋅T(n/2) + O(n)
= 2⋅(2⋅T(n/4) + O(n/2)) + O(n)
= 4⋅T(n/4) + 2⋅O(n/2) + O(n)
= 4⋅(2⋅T(n/8) + O(n/4)) + 2⋅O(n/2) + O(n)
= Σk=1,...,m 2k⋅O(n/2k)
= Σk=1,...,m O(n)
= m⋅O(n)
从m = log₂(n)开始，你可以写成O(n log n)。
最后 n 是否是 2 的幂并不重要。
要看到这一点，您可以这样想：您有一个输入 n（它不是 2 的幂），您向输入添加更多元素，直到它包含 n' = 2<sup>m</sup> 有m ∈ ℕ和log(n) ≤ m ≤ log(n) + 1的元素，即n'是大于n的2的最小次方.显然 T(n) ≤ T(n') 成立并且我们知道 T(n') 在
O(n'⋅log(n')) = O(c⋅n⋅log(c⋅n)) = O(n⋅log(n) + n⋅log(c)) = O(n⋅log(n))
其中 c 是 1 和 2 之间的常数。
你可以用小于n的2的最大次方来做同样的事情。这将引导您到 T(n) ≥ T(n'')，我们知道 T(n'') 在
O(n''⋅log(n'')) = O(c⋅n⋅log(c⋅n)) = O(n⋅log(n))
其中 c 是 1/2 和 1 之间的常数。
总的来说，T(n) 的复杂度受限于 T(n'') 和 T(n') 的复杂度，它们都是 O(n⋅log(n))，所以 T(n)也在O(n⋅log(n))，即使不是2的幂
这个递归关系的运行时间是O(nlogn)。由于我是算法的新手，我该如何用数学来证明它？
T(n) = 2⋅T(n/2) + O(n)
T(n) = 2 ( 2⋅T(n/4) + O(n) ) + O(n) // since T(n/2) = 2⋅T(n/4) + O(n)
到目前为止我可以看到，如果我假设 n 是 2 的幂，例如 n = 2<sup>m</sup> ，那么也许我可以证明这一点，但我没有得到清晰的画面。谁能帮帮我？
如果你使用主定理，你会得到你期望的结果。
如果你想证明这个 "by hand"，你可以很容易地通过假设 n = 2<sup>m</sup> 来证明这一点2 的幂（正如你已经说过的）。这会将您带到
T(n) = 2⋅T(n/2) + O(n)
= 2⋅(2⋅T(n/4) + O(n/2)) + O(n)
= 4⋅T(n/4) + 2⋅O(n/2) + O(n)
= 4⋅(2⋅T(n/8) + O(n/4)) + 2⋅O(n/2) + O(n)
= Σk=1,...,m 2k⋅O(n/2k)
= Σk=1,...,m O(n)
= m⋅O(n)
从m = log₂(n)开始，你可以写成O(n log n)。
最后 n 是否是 2 的幂并不重要。
要看到这一点，您可以这样想：您有一个输入 n（它不是 2 的幂），您向输入添加更多元素，直到它包含 n' = 2<sup>m</sup> 有m ∈ ℕ和log(n) ≤ m ≤ log(n) + 1的元素，即n'是大于n的2的最小次方.显然 T(n) ≤ T(n') 成立并且我们知道 T(n') 在
O(n'⋅log(n')) = O(c⋅n⋅log(c⋅n)) = O(n⋅log(n) + n⋅log(c)) = O(n⋅log(n))
其中 c 是 1 和 2 之间的常数。
你可以用小于n的2的最大次方来做同样的事情。这将引导您到 T(n) ≥ T(n'')，我们知道 T(n'') 在
O(n''⋅log(n'')) = O(c⋅n⋅log(c⋅n)) = O(n⋅log(n))
其中 c 是 1/2 和 1 之间的常数。
总的来说，T(n) 的复杂度受限于 T(n'') 和 T(n') 的复杂度，它们都是 O(n⋅log(n))，所以 T(n)也在O(n⋅log(n))，即使不是2的幂