재발을 해결하는 방법.t (n).= T (N-1) + T (n / 2) + n?

Question

재귀 트리 메소드로 실행 시간을 얻으려면 트리를 그릴 필요가 있으며 찾아야합니다.

a) 나무 수준의 수.

나무의 왼쪽면이 크기가 1만큼 감소하기 때문에 뿌리에서 가장 긴 경로입니다. SubProblem Level I의 크기는 n-i입니다. n - i= 1 설정 1의 크기가 히지면 레벨 수를 얻습니다. i= n - 1.

b) 트리에서 노드 당 비용 : cn

c) 레벨 I 노드의 수 : 이것은 내가 붙어있는 곳입니다. 왼쪽 측면이 1, 오른쪽으로 반으로 감소하기 때문에 레벨에서 노드를 찾을 수 없습니다. 당연히 나무는 왼쪽에 더 밀도가 있습니다. 모든 노드가 두 자녀가있는 것은 아닙니다.

C에 대한 답변을 얻을 수 있다면 T (n)= 레벨 1 + 레벨 1 + 비용의 비용을 계산할 수 있습니다. 레벨 2 + 비용은 N-1의 비용입니다. y1이 레벨 1에서 노드 수, 레벨 2 등의 노드 수는 ... 그런 다음
=> t (n)= cn + y1 * cn + y2 * cn + y3 * cn + .... yn-1 * cn 총 비용을 얻으려면.

누구든지 나를 데려 오는 접근 방식으로 인도 할 수 있습니까? 정확합니까? 충분히 큰 n을 위해 우리는 T (n / 2)를 무시할 수 있고 다음을 진행할 수 있다는 가정을 할 수 있습니까? ...에

온라인 검색을 혼란스럽게합니다. 문제는 CLRS에서 4.4-5입니다.

를 참조하십시오.

이 솔루션은 T (n)= O (2 ^ N) 및 T (n)= 오메가 (n ^ 2)을 말하고 어떻게 설명하지 않는다고 설명하지는 않는다.

또한 여기

이 솔루션은 T (n)= O (n ^ 2)를 말한다. 그러나 위의 해결책과 모순됩니다

Answer 1

$ s (n)= t (n) - 2N - 2 $ 을 보자. $ s (n)= s (n-1) + s (n / 2) $ ( $ N / 2 $ 은 정수가 필요하지 않습니다). 이것은 첨가제 $ n $ 용어가 큰 차이를 만들지 않습니다.

대형 $ n $ , 우리는 대략 $ s (n) - s (n-1) \ 약 s '(n) $ 이므로 우리는 차동 방정식을 해결하게됩니다. $$ s '(n)= s (n / 2). $$ $ f (n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) $ 을 고려하십시오. 그때 $$ f '(n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) \ cdot \ frac {(\ ln 4) n}, $$ 이므로 $$ f (n / 2)=exp (\ tfrac {1} {2} (\ log_2 n - 1) ^ 2) \ 약 \ exp (\ tfrac {1} {2} \ log ^ 2 n) \ exp ( - \ log n)=exp (\ tfrac {1} {2} \ log ^ 2 n) \ cdot \ frac {1} {n}. $$ 이렇게하면 최소한 $ \ ln s (n)= θ / span>

여기서 어디에서 왔습니까? $ S (n) $ (적절한 기본 경우와 함께!)을 $ \ log_2n $ 많은 작업을 포함합니다. $ \ theta (n) $ $ \ binom {\ theta (n) {\ log_2 n} $ $ \ exp \ theta (\ log ^ 2 n) $ .

---

$ s (n) $ 의 다음과 같은 정확한 정의를 다음과 같은 정확한 정의를 고려하십시오. 기본 경우는 $ s (0 )= 1 $ 및 $ n> 0 $ , $$ s (n)= s (n-1) + s (\ lfloor n / 2 \ rfloor). $$ 이것은 a000123 입니다. Knuth, 거의 선형 재발 가 나타났습니다. $$ \ log_4 s (n) \ sim \ log_4 ^ 2 n, $$ 즉, 두 용어의 비율은 $ n \ infty $ 으로 1로 경향이 있습니다. OEIS 항목에는 더욱 정확한 점근증이 포함됩니다.

Answer 2

나는 Fibonacci 최면에 동의하지 않지만, 나는 내 대답을 100 % 확신하지 않아

당신이 보았습니다 $ T (n)= T (n-1) + C * n= o (n ^ 2) $

$ T (n)= T (n / 2) + c * n= o (n log n) $

그러나 u는 엑스트라 첨가에 의해 UR T (n)를 얻지 못합니다.

재귀에서 하나의 레벨을 가면 (트리를 그릴 수 있음)

T (n)= T (N-2) + T ((n-1) / 2) + T (n / 2-1) + T (n / 4) + [n + (n-1) + (n-1) / 2 + (n / 2-1) + n / 4]

이것은 u를 보여줄 것입니다. $ o (n ^ 2) $

나는 그것을 완성해야하지만, $ o ((n ^ 2) * log n) $ 또는 $ o ((n ^ 2) * n ^ {log n})= o (n ^ 3) $

{log n 단계에서 붕괴되는 용어 n (1 + 1 / 2 + 1 / 4 + .. 1 / n), 다시 확인해야합니다}