递归关系:T(n) = 2T(n/2) + log(n) [英] Recurrence relation: T(n) = 2T(n/2) + log(n)

问题描述

我有一个递归关系，如下所示:

I have a recurrence relation which is like the following:

T(n) = 2T(n/2) + log₂ n

T(n) = 2T(n/2) + log₂ n

我正在使用递归树方法来解决这个问题.最后，我想出了以下等式:

I am using recursion tree method to solve this. And at the end, i came up with the following equation:

T(n)=(2log₂n)(n-1)-(1*2 + 2*2² + ... + k*2^k) 其中 k=log₂n.

T(n)=(2log₂n)(n-1)-(1*2 + 2*2² + ... + k*2^k) where k=log₂n.

推荐答案

这些重复问题可以通过 masters 解决定理.在您的情况下 a = 2, b = 2 因此 c = logb(a) = 1.

These recurrence can be solved with a masters theorem. In your case a = 2, b = 2 and therefore c = logb(a) = 1.

你的 f(n) = log n 并且因为 n^c 比你的 f 增长得更快，它在解决方案中占主导地位，你跌倒在第一种情况下.所以复杂度是O(n).

Your f(n) = log n and because n^c grows faster than your f, it dominates the solution and you fall in the first case. So the complexity is O(n).

这篇关于递归关系:T(n) = 2T(n/2) + log(n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！