用log n求解主定理:T(n)= 2T(n/4)+ log n [英] Solving master theorem with log n: T(n) = 2T(n/4) + log n

问题描述

我目前正在尝试用主定理解决这种关系:

I'm currently trying to solve this relation with the master theorem:

T(n)= 2T(n/4)+对数n

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

我已经知道a = 2和b = 4，但是我对log n感到困惑.

I already figured out that a = 2 and b = 4, but I'm confused about the log n.

我的脚本说:c(n)(这里将为log n)是Big O(n ^ d)的元素.

My script say: c(n) (which would be log n here) is element of Big O(n^d).

如果我可以在这里找到d，则可以将a和b ^ d进行比较以找出我的主定理案例.

If I can figure out my d here, I would compare a and b^d to find out my master theorem case.

但是，由于它在此处登录为n，因此我不确定它的Big O表示法.

However, due to the fact that it's log n here, I'm not sure about its Big O notation.

我的意思是我可能会说它是O(n ^1/2 )的元素，这将导致情况二，其中a和b ^ d相同，但这也是O(n ¹ )，然后又是另一种情况.

I mean I could probably say it's element of O(n^1/2), which would then lead to case two, where a and b^d are the same, but it's also element of O(n¹), which would then be another case again.

推荐答案

一个有用的事实是，对于任何ε > 0，我们知道

One useful fact is that for any ε > 0, we know that

log n = O(n ^ε ).

我们也知道

log n =Ω(1)

log n = Ω(1)

让我们看看这是否告诉我们任何信息.我们知道，对于任何&epsilon ;，您的复发都受此限制. > 0:

Let's see if this tells us anything. We know that your recurrence is bounded from above by this one for any ε > 0:

S(n)= 2S(n/4)+ n ^ε

让我们在这里使用主定理.我们有a = 2，b = 4，和d =ε.我们需要推论log _b a = log ₄ 2 = 1/2以及与d =ε的关系.让我们做ε小-比方说，我们选择ε = 0.000001.然后我们有log _b a< d，因此主定理说运行时间将是

Let's use the Master Theorem here. We have a = 2, b = 4, and d = ε. We need to reason about log_b a = log₄ 2 = 1/2 and how that relates to d = ε. Let's make ε small - say, let's pick ε = 0.000001. Then we have log_b a < d, so the Master Theorem says that the runtime would be

O(n ^{log _b a} )= O(n ^1/2 ).

接下来，考虑以下重复关系:

Next, consider this recurrence relation:

R(n)= 2R(n/4)+1

R(n) = 2R(n / 4) + 1

此重复次数会降低您的重复次数.使用主定理可以告诉我们R(n)=Ω(n ^1/2 ).

This recurrence lower-bounds your recurrence. Using the Master Theorem tells us that R(n) = Ω(n^1/2) as well.

总的来说，通过上下限将您的复发定为O(n ^1/2 )和Ω(n ^1/2 )越来越大的复发.因此，即使Master Theorem在这里不适用，您仍然可以使用Master Theorem声明运行时将为Θ(n ^1/2 ).

Overall, we see that your recurrence is O(n^1/2) and Ω(n^1/2) by upper- and lower-bounding your recurrence by larger and smaller recurrences. Therefore, even though the Master Theorem doesn't apply here, you can still use the Master Theorem to claim that the runtime will be Θ(n^1/2).

希望这会有所帮助！

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