递归：T(n) = (2+1/log n)T(n/2)

Question

3

我需要用树形法解决这个递归关系，因为主定理不适用。

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

- tanee

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Salvador Dali · Accepted Answer

经过一些思考，我无法提出一个确切的解决方案。主定理在这里不起作用，展开树也没有给我任何合理的东西。因此，我将按以下方式估计复杂度。

对于任何足够大的n，您可以估计0 < 1 / log n < 1。因此，您可以得到：

T1(n) = 2 * T1(n/2)
T2(n) = 3 * T2(n/2)

并且 O(T1) < O(T) < O(T2)。您可以使用主定理找到两个递归的复杂度。其中，T1 的复杂度为 O(n)，而T2的复杂度为 O(n^log2(3))。

因此，您可以确信您的递归复杂度大于 O(n) 且小于 O(n^1.58)，因此小于二次方。