algorithm - 算法中的递归求解

Question

我正在做练习，我被卡住了-.-。这是我必须完成的任务。

解决方案：我没有得到黄色的步骤。我试图理解，但我缺乏对数的知识。你能解释一下吗

谢谢你的解释！

标签： algorithm

Answer 1

请记住，log ab = log a + log b也log (1/a) = - log a

所以当你有2(n/2) log(n/2)你可以写成log(n/2)which log(1/2 x n)using log ab = log a + log bequalslog(n) + log(1/2)

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

也log (1/a) = - log a，因此log(1/2) = - log 2

这就是你得到的方式

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

= n(log n - log 2 ) + n

由于log 2 = 1在base 2中，您将拥有n(log n - log 2 ) + n = n(log n - 1) + n = n lg n