与F（N）主定理=日志N [英] Master's theorem with f(n)=log n

问题描述

对于主定理T（N）= A * T（N / B）+ F（N），我使用3个情况：

For master's theorem T(n) = a*T(n/b) + f(n) I am using 3 cases:

1. 如果一个* F（N / B）= C * F（N）的一些常数c> 1，则T（N）=（N ^日志（二）一）
2. 如果一个* F（N / B）= F（N），则T（N）=（F（N）日志（二）N）
3. 如果一个* F（N / B）= C * F（N）的一些常数c＆LT; 1，则T（N）=（F（N））

但是，当F（N）=日志n或n *日志N，C的值取决于n的值。我该如何解决这个递归函数使用主定理？

But when f(n) = log n or n*log n, the value of c is dependent on value of n. How do I solve the recursive function using master's theorem?

任何帮助将AP preciated

Any help will be appreciated

推荐答案

您可能会发现这三种情况下，从的在主定理维基百科的文章多一点有用的：

You might find these three cases from the Wikipedia article on the Master theorem a bit more useful:

• 案例1：F（N）=西塔（N ^C ），其中C＆LT;日志<子> B A
• 案例2：F（N）=西塔（N ^C 登录 ^K N），其中c =登录<子> B A
• 案例3：F（N）=西塔（N ^C ），其中c>日志<子> B A

• Case 1: f(n) = Θ(n^c), where c < log_b a
• Case 2: f(n) = Θ(n^c log^k n), where c = log_b a
• Case 3: f(n) = Θ(n^c), where c > log_b a

现在有n的选择没有直接的相关性了 - 所有重要的是F的长期增长速度，以及它如何涉及常数a和b。没有看到你正在试图解决特定的复发更多的细节，我不能提供任何更具体的建议。

Now there is no direct dependence on the choice of n anymore - all that matters is the long-term growth rate of f and how it relates to the constants a and b. Without seeing more specifics of the particular recurrence you're trying to solve, I can't offer any more specific advice.

希望这有助于！

这篇关于与F（N）主定理=日志N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！