반복없이 되풀이 관계 풀기

어떻게 해결할 수 있습니까?반복없이 되풀이 관계 풀기

T (N) = T (N/4) + T (3N/4) + CN

된 AN \ 세타 (nLogn)이 응답이 마스터 정리하거나을 사용하여 달성 할 수있는 방법

인 다른 효과적인 방법?

출처

2016-10-13 Rohit Roy

예, 있습니다. 기능을 알아내는 것. [너무] 광범위합니다. Google 위키피디아에서. 그것은 주제에 대한 아주 좋은 소개를 제공합니다. – xenteros

여기서 마스터 정리를 사용할 수 있습니까? –

@RohitRoy 아니요, 마스터 정리는 여기에서 사용할 수 없습니다. 여기에서 재귀 트리를 사용하는 것이 좋습니다. –

과 같이 표시됩니다 주어진 재귀에 대한 재귀 트리 : N-> 3N/4 것 잎에 뿌리에서

       Size      Cost 

           n       n 
          / \ 
          n/4 3n/4      n 
         / \ / \ 
         n/16 3n/16 3n/16 9n/16    n 

         and so on till size of input becomes 1

longes에게 간단한 경로를 -> (3/4)^2 N .. 이제 1

Therefore let us assume the height of tree = k 

      ((3/4)^k)*n = 1 meaning k = log to the base 4/3 of n 

In worst case we expect that every level gives a cost of n and hence 

     Total Cost = n * (log to the base 4/3 of n) 

However we must keep one thing in mind that ,our tree is not complete and therefore 

some levels near the bottom would be partially complete. 

But in asymptotic analysis we ignore such intricate details. 

Hence in worst Case Cost = n * (log to the base 4/3 of n) 

      which is O(n * log n)

까지, 우리가이 사용하는 대체 방법을 확인하자 :

는

T(n) = O(n * log n) iff T(n) < = dnlog(n) for some d>0 

Assuming this to be true: 

T(n) = T(n/4) + T(3n/4) + n 

     <= d(n/4)log(n/4) + d(3n/4)log(3n/4) + n 

     = d*n/4(log n - log 4) + d*3n/4(log n - log 4/3) + n 

     = dnlog n - d(n/4)log 4 - d(3n/4)log 4/3 + n 

     = dnlog n - dn(1/4(log 4) - 3/4(log 4/3)) + n 

     <= dnlog n 

     as long as d >= 1/(1/4(log 4) - 3/4(log 4/3))

출처

2016-10-13 08:06:57

좋은 설명,하지만 왜 여기서 마스터를 사용할 수 없습니까? 최악의 시간 복잡도의 경우에 T (n) = 2T (3n/4) + cn으로 다시 쓸 수있다. 그리고 나서 우리는 master를 사용할 수 있습니다. –

@MohitKumar 주어진 재발을 세 가지 경우 중 어떤 것으로 변형시킬 것입니까? 그게 왜. –

그렇지 않을 수도 있습니다. –

답변

관련 문제