마스터 정리의 규칙성 조건과 관련된 증명의 명확화

Question

저는 Cormen et al의 알고리즘 소개 텍스트를 읽고 있었습니다.나는 마스터 정리의 세 번째 사례 증명에서 다음 진술을 발견했습니다.

(마스터 정리의 진술) $a \geqslant 1$ 그리고 $b > 1$ 상수가 되자 $f(n)$ 함수가 되어 보자 $티(n)$ 반복에 의해 음이 아닌 정수에 대해 정의됩니다(재귀는 크기 문제를 나눕니다. $n$ ~ 안으로 $a$ 크기의 문제 $n/b$ 각각 취하고 $f(n)$ 분할 및 결합의 경우)

$T(n) = aT(n/b)+ f(n)$ ;

우리가 해석하는 곳 $n/b$ 둘 중 하나를 의미하다 $\lceil b/n ceil$ 또는 $\lfloor b/n floor$.그 다음에 $T(n)$ 다음과 같은 점근적 경계를 가집니다.

1. 만약에 $f(n)=O (n^{\log_ba - \epsilon})$ 일정하게 $\엡실론 > 0$, 그 다음에 $T(n)=\세타(n^{\log_ba})$.

2. 만약에 $f(n)=\세타(n^{\log_ba})$, 그 다음에 $T(n)=\세타(n^{\log_ba}\lg n)$

3. 만약에 $f(n)=\오메가 (n^{\log_ba + \epsilon})$ 일정하게 $\엡실론 > 0$, 그리고 만약 $af(n/b) \leqslant cf(n)$ 일정하게 $c < 1$ 그리고 모두 충분히 큰 n이면 $T(n)=\세타(f(n))$.

을 위한 $n$ 정확한 힘으로 $b$ 우리는 T(n)의 영역을 다음과 같이 제한합니다:

$$T(n)= \세타(1), n=1$$ $$T(n)=aT(n/b)+f(n) ,n=b^i$$

이제 석사 정리의 증명에서 $n$ 정확한 힘으로 $b$ 에 대한 표현 $T(n)$ 다음과 같이 감소합니다:

$$T(n)= heta(n^{\log_ba})+\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

그러면 저자는 다음과 같이 가정합니다.

$$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

그런 다음 마스터 정리의 세 번째 경우의 증명을 위해 저자는 다음 정리를 증명합니다.

기본정리 1 :만약에 $a\cdot f(n/b)\leqslant c\cdot f(n)$ 일정하게 $c<1$ 그리고 모두를 위해 $n\geqslant b$ 그 다음에 $g(n)=\세타(f(n))$

그들은 이렇게 말합니다:

그들의 가정하에 $c<1$ 그리고 $n \geqslant b$,그들은 $a \cdot f(n/b)\leqslant c \cdot f(n) \는 f(n/b)\leqslant (c/a) \cdot f(n)$를 의미합니다.

그 다음에 반복 $j$ 타임스 수익률, $f(n/b^j)\leqslant (c/a)^j \cdot f(n)$

나는 뒤에 사용된 수학을 잘 이해할 수 없었다 반복 $j$ 타임스.

더욱이 나는 가정의 배후에 있는 논리를 완전히 이해할 수 없었다. $n\geqslant b$ 그 상황 때문에 $n$ 충분히 커야 합니다.(마스터 정리의 세 번째 사례에서 알 수 있듯이)

정리의 증명은 다음과 같이 계속됩니다.

$$f(n/b^j)\leqslant (c/a)^j\cdot f(n) \iff a^j\cdot f(n/b^j)\leqslant c^j\cdot f(n )$$그래서, $$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$ $$\leqslant \sum_{j=0}^{\log_bn -1} c^jf(n)$$ $$\leqslant f(n)\sum_{j=0}^{\infty} c^j,$$ ~처럼 $c<1$ 우리는 무한한 기하학적 급수를 가지고 있습니다$$= f(n) \left(\frac{1}{1-c} ight)$$ $$=O(f(n))$$ ~처럼 $c$ 상수입니다.(참고하세요 $T(n)=\오메가(f(n))$ 재귀 다이어그램에서.)

그런 다음 저자는 마스터 정리의 세 번째 사례를 증명합니다. $n$ 정확한 힘으로 $b$:

기본정리 2:허락하다 $a \geqslant 1$ 그리고 $b>1$, 만약에 $f(n)=\오메가 (n^{\log_ba + \epsilon})$ 일정하게 $\엡실론 > 0$, 그리고 만약 $af(n/b) \leqslant cf(n)$ 일정하게 $c < 1$ 그리고 모두 충분히 큰 n이면 $T(n)=\세타(f(n))$.

그래서 $$T(n) = heta(n^{\log_ba}) + g(n) = heta(n^{\log_ba}) + heta(f(n)) = heta(f(n) )$$ ~처럼 $f(n)=\오메가 (n^{\log_ba + \epsilon})$

더욱이 일반 마스터 정리의 세 번째 경우에 대한 유사한 증명에서(가정하지 않음) $n$ 정확한 힘으로 $b$) 여기서도 책은 다음과 같이 가정합니다. $n\geqslant b+b/(b-1)$ 충분히 큰 상황에 맞춰 $n$.

특정 값이 무엇을 해야 하는지, 왜 그 값이 충분히 큰 것으로 가정되는지 잘 이해하지 못합니다. $n$

(두 번째 상황에 대해서는 첫 번째 상황과 비슷할 것 같아서 자세한 내용은 밝히지 않았지만 찾아볼 수는 있습니다. 여기)

Answer 1

반복 문제부터 시작하겠습니다.함수가 있다고 가정하자 $f$ 만족하다$$ f(n/b) \leq (c/a)f(n).$$그럼 그것도 만족해$$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n).$$모든 정수에 대해 귀납법을 통해 증명할 수 있습니다. $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n).$$

두 번째 질문은 다음과 같이 가정하는 것입니다. $n$ 충분히 크다:증거가 엉성할 뿐입니다.당신은 그것을 가정할 수 없습니다 $f(n/b) \leq (c/a) f(n)$ 모두를 위해 보유 $n \geq b$.실제로, 알고리즘 소개(제3판)에서는 다음과 같은 경우에 대해 그러한 가정을 하지 않습니다. $n$ 의 힘이다 $b$.

그들은 일반적인 경우에 그런 가정을 하는 것 같습니다. $n$, 하지만 그들이 실제로 말하는 것은 불평등이 $f(\lceil n/b ceil) \leq (c/a) f(n)$ 오직 의미가 있습니다 $n \ge b + b/(b-1)$.특별한 경우의 증명이라는 아이디어를 이용하여 $n$ 의 힘이다 $b$, 일반 사건의 증명을 완료할 수 있습니다.그러나 나는 현재 그러한 전문적인 사항을 무시할 것을 강력히 제안합니다.마스터 정리는 본질적으로 계산이며, 그것이 작동한다고 저자를 신뢰할 수 있습니다.깔개 아래에는 흥미로운 것이 숨겨져 있지 않습니다.