반복 관계의 특수한 경우를 해결하는 방법

Question

T (n) = T (n-1) + T (n-2) + O (n)의 형태의 반복 관계를 푸는 방법에 대한 많은 예제와 튜토리얼이 있습니다. k) 또는 T (n) = a T (n/b) + O (n^k)이다.

이 두 형식의 혼합 된 되풀이 관계를 풀려고합니다. T (n) = T (n-2) + 2 T (n/2)) = 1, T (1) = 1

이 반복 관계를 해결하는 방법에 대한 정보는 요?

감사합니다.

Answer 1

대체 방법을 사용하십시오. 글쎄, 내가 조금만 백업하자. 대체 방법은 추측을 평가하기위한 것이지만 추측은 어딘가에서 온 것이어야합니다. 나는이 재발에 대해 많은 직관이 없으므로, 나는 나의 과정을 적어 보겠다. 시퀀스의 시작을 살펴 보는 것이 유용하다는 것을 알았습니다.

>>> def T(n): 
... if n==0: return 1 
... elif n==1: return 1 
... else: return T(n-2) + 2*T(n//2) 
... 
>>> [T(n) for n in range(50)] 
[1, 1, 3, 3, 9, 9, 15, 15, 33, 33, 51, 51, 81, 81, 111, 111, 177, 177, 243, 243, 345, 345, 447, 447, 609, 609, 771, 771, 993, 993, 1215, 1215, 1569, 1569, 1923, 1923, 2409, 2409, 2895, 2895, 3585, 3585, 4275, 4275, 5169, 5169, 6063, 6063, 7281, 7281] 

숫자 사이의 간격이 커져서 아마도 초 선형 적입니다. 다른 한편으로는 지수가되기에 충분히 빠르지는 않는 것처럼 보입니다. 아마 다항식 일 겁니다. 그렇다면 T(2*n)/T(n)은 경계해야하지만, 그런 일은 일어나지 않는 것 같습니다.

>>> T(20)/T(10) 
6.764705882352941 
>>> T(50)/T(25) 
13.955665024630543 
>>> T(100)/T(50) 
20.954112248499822 
>>> T(200)/T(100) 
35.791368360763435 

이것은 무엇이 발생 하는지를 알기 위해 교체하기 시작하는 지점입니다. 시도해 봅시다 2^n. n=2에 대한 제안은 2^0 + 2^2 <= 2^2 것을

T(0) = 1 <= 2^0 = 1: check 
T(1) = 1 <= 2^1 = 2: check 
T(n) = T(n-2) + 2*T(n/2) 
    <= 2^(n-2) + 2*2^(n/2) 
     = 2^(n-2) + 2^(1 + n/2): FAIL, 

을 의미하기 때문이다. 1 + n/2은 n이 작은 경우를 제외하고는 n에 근접하지 않기 때문에 이것은 나에게 "그냥 놓친"느낌을줍니다. 실제로 4^n이라는 경계가 작동합니다.

T(0) = 1 <= 4^0 = 1: check 
T(1) = 1 <= 4^1 = 4: check 
T(n) = T(n-2) + 2*T(n/2) 
    <= 4^(n-2) + 4^(1/2 + n/2) 
    <= 4^(n-2) + 4^(n - 1/2) [since n - 1/2 >= 1/2 + n/2 for n >= 2] 
    <= 4^n: check 

가 바운드를 "해결"섬세한 가지가 있지만 형태 c^n의 무엇이든은 여전히 ​​잘못된 생각입니다 : 그냥 4^(n/2 + O(1))에 대한 바운드로 4^(n + O(1))를 사용하는 낭비, 인 직감입니다 위의 실제 숫자로 백업됩니다.

다항식으로 묶으 려 할 때 어떤 일이 일어나는지 보여 드리겠습니다. 예를 들어 n^100입니다. n^100에 일정 이후

T(n) = T(n-2) + 2*T(n/2) 
    <= (n-2)^100 + 2*(n/2)^100 
     = n^100 + O(n^99) + 2^-99*n^100 + O(n^99): FAIL, 

약간 너무 큽니다. 이것은 경계가 작동하지 않는다는 표시입니다. 다항식과 지수 사이에서 얻을 수있는 간단한 방법

하나는 n^log(n) 또는 n^(log(n)^2) 같은 quasipolynomial 이다. 전자를 사용해 봅시다.

T(n) = T(n-2) + 2*T(n/2) 
    <= n^log(n-2) + 2*((n/2)^log(n/2)) 
     = n^(log(n) + log(1 - 2/n)) + 2*((n/2)^(log(n) - 1)) 
     = n^(log(n) + ln(1 - 2/n)/ln(2)) + 2*((n/2)^(log(n) - 1)) 
    <= n^(log(n) - 2/(n*ln(2))) + n^(log(n) - 1)/2^(log(n) - 2) 
     [by log(1 + x) <= x, often written 1 + x <= e^x] 
     = n^log(n)/n^(2/(n*ln(2))) + 4*n^log(n)/n^2 

이것은 유망 해 보입니다. c > 0의 경우 n -> infinity이 n^(c/n) = e^(c*ln(n)/n) 인 한계는 1이며 위부터 다가옵니다. 우리가해야 할 일은 바운드 n^(2/(n*ln(2))) >= 1/(1 - 4/n^2) = 1 + 4/n^2 + O(1/n^4)을 얻는 것뿐입니다.이 증거가 몇 가지 미해결 부분을 가지고 있지만 복잡, quasipolynomial 인 것처럼 그것은 보인다

n^(c/n) = e^(c*ln(n)/n) >= 1 + c*ln(n)/n >= 1 + 4/n^2 + O(1/n^4) for large n. 

작성합니다. 내가 상시 적으로 증명 한 진술은 모두 n을 제외하고는 보존 할 필요가 없으므로 상수에 패치를 적용해야합니다. 이러한 세부 정보는 지루하고 유익하지 못한 경향이 있습니다. 우리는 또한 일치하는 하한을 증명해야하지만, 위의 분석은 너무 단단하여 이것이 수행 될 수 있다고 확신합니다. 나는 여기서 멈출거야.