Prova rigorosa da validade da suposição ao usar o teorema do mestre

O teorema do mestre é uma ferramenta bonita para resolver certos tipos de recorrências . No entanto, geralmente encobrimos uma parte integrante ao aplicá-la. Por exemplo, durante a análise do Mergesort, passamos felizes de

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

para

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

considerando apenas $n=2^k$ . Asseguramos a nós mesmos que esta etapa é válida - ou seja, $T \in \Theta(T')$ - porque $T$ se comporta "bem". Em geral, assumimos $n=b^k$ para $b$ o denominador comum.

É fácil construir recorrências que não permitam essa simplificação usando vicioso $f$ . Por exemplo, a recorrência acima para $T\,$ / $\,T'$ com

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

produzirá $\Theta(n)$ usando o teorema mestre da maneira usual, mas há claramente uma subsequência que cresce como $\Theta(n \log n)$ . Veja aqui outro exemplo mais artificial.

Como podemos tornar isso "bem" rigoroso? Estou certo de que a monotonicidade é suficiente, mas nem mesmo a simples recorrência do Mergesort é monótona; existe um componente periódico (que é dominado assintoticamente). Isso é suficiente para investigar $f$ , e quais são as condições necessárias e suficientes sobre $f$ que garantir as obras Teorema Mestre?

asymptotics proof-techniques recurrence-relation master-theorem Rafael
fonte

Outra abordagem sobre os mesmos resultados é o teorema de Akra-Bazzi "Sobre a solução de equações de recorrência linear", Otimização e aplicações computacionais, 10 (2), 195-210 (1998), ou Drmota e Szpankowski "Um teorema mestre para a divisão discreta e conquistar recorrências ", SODA'11 < dl.acm.org/citation.cfm?id=2133036.2133064 >.

7133 vonbrand

Aqui está um link para o documento acima, que não está atrás de um paywall.

Parev

IIRC isso é discutido em CLRS capítulo 4.

Kaveh

@ Kaveh Obrigado pelo ponteiro. Na maioria das vezes, eles chamam de "negligência tolerável"; isso é bom no contexto deles, porque eles assumem que você deriva apenas de uma hipótese, mais tarde provada correta por indução. Eles mencionam os perigos (4.6). Na 4.6.2, eles dão uma prova, mas é de alto nível e não explicitamente dizem quais restrições em devem existir. Portanto, parece ser algo como " tal como a matemática passa", que eu acho que exige principalmente que tenha uma classe "agradável" .

T

$T$

T

$T$

f

$f$

Θ

$\Theta$

Raphael

Em geral, quando você não possui tamanhos semelhantes, pode usar o método Akra – Bazzi, que é a generalização do teorema mestre, com certeza como alterar uma função específica para algo que funciona nesse teorema precisa de um pequeno truque e, para algo como classificação por mesclagem, isso é o que normalmente as pessoas estão usando para provar a complexidade do tempo.

Ao longo desta resposta, assumimos que e não são negativos. Nossa prova funciona sempre que para algum monótono . Isso inclui o exemplo do Mergesort, no qual e qualquer função com taxa de crescimento polinomial (ou mesmo ). $f$ $T$ $f = \Theta(g)$ $g$ $f=\Theta(n)$ $\Theta(n^a \log^b n)$

Vamos considerar primeiro o caso em que é monótono e não diminui (relaxaremos essa suposição mais tarde). Nós nos concentramos na recorrência da amostra Essa recorrência precisa de dois casos base, e . Assumimos que , que também relaxamos mais tarde. $f$

T (n) = T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) .

$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n).$

T (0)

$T(0)$

T (1)

$T(1)$

T (0) \leq T (1)

$T(0) \leq T(1)$

Afirmo que é monótono e não diminui. Provamos por indução completa que . Isso é dado para , então deixe . Temos Isso implica que Portanto, se , terminamos. Este é sempre o caso se a solução para potências de dois tiver a forma . $T(n)$ $T(n+1) \geq T(n)$ $n = 0$ $n \geq 1$

\begin{aligned} T (n + 1) & = T (⌊ (n + 1) / 2 ⌋) + T (⌈ (n + 1) / 2 ⌉) + f (n + 1) \\ \geq T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) = T (n) . \end{aligned}

$\begin{align*} T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\ &\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n). \end{align*}$

T (2^{⌊ \log_{2} n ⌋}) \leq T (n) \leq T (2^{⌈ \log_{2} n ⌋}) .

$T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rfloor}).$

T (2^{m}) = Θ (T (2^{m + 1}))

$T(2^m) = \Theta(T(2^{m+1}))$

T (n) = Θ (n^{a} \log^{b} n)

$T(n) = \Theta(n^a \log^b n)$

Agora vamos relaxar a suposição de que . Considere uma nova recorrência definida exatamente da mesma maneira, apenas . Podemos provar por indução que . Da mesma forma, podemos definir uma nova recorrência satisfazendo e depois . Invocando o teorema do Mestre, vemos que e para a mesma função , e também . $T(0) \leq T(1)$ $T'$ $T'(0) = T'(1) = \min(T(0),T(1))$ $T'(n) \leq T(n)$ $T''$ $T''(0) = T''(1) = \max(T(0),T(1))$ $T(n) \leq T''(n)$ $T'=\Theta(h)$ $T''=\Theta(h)$ $h$ $T = \Theta(h)$

Agora vamos relaxar a suposição de que é monótono. Suponha que para alguma função monótona . Assim por algum e suficientemente grande. Assumimos por simplicidade que ; o caso geral pode ser tratado como no parágrafo anterior. Novamente, definimos duas recorrências substituindo por (respectivamente). Mais uma vez, o teorema do mestre dará o mesmo resultado (até múltiplos constantes), que também é idêntico (até múltiplos constantes) ao que obteríamos ao resolver a recorrência original apenas com potências de dois. $f$ $f = \Theta(g)$ $g$ $cg(n) \leq f(n) \leq Cg(n)$ $c,C>0$ $n$ $n=0$ $T',T''$ $f$ $cg,Cg$

Yuval Filmus
fonte

Finalmente consegui ler isso mais de perto. Bom obrigado! Pensei em anotar isso para futuros leitores (porque me deparei com isso): não é uma restrição, pois é apenas falso para o super polinômio e o teorema do mestre não se aplicam a isso.

T (2^{m}) \in Θ (T (2^{m + 1}))

$T(2^m) \in \Theta(T(2^{m+1}))$

T

$T$

Raphael

Tentei escrever sua prova com mais detalhes e fiquei preso ao provar sua última frase ", que também é idêntica (...) ao que obteríamos resolvendo a recorrência original apenas com potências de dois". Em particular, temos que mostrar que acabamos no mesmo caso do teorema do mestre para , e . Isso não é problema para os casos 1 e 2, mas não posso mostrar a existência de para o caso 3 (consulte a versão no CLRS, p94 na 3ª edição). Você pensou nisso ou trabalhou com uma versão semelhante à da Wikipedia ?

c g

$cg$

f

$f$

C g

$Cg$

c < 1

$c < 1$

Raphael

Isso é um detalhe técnico. Se , o problema desaparecer, consulte, por exemplo, users.encs.concordia.ca/~chvatal/notes/master.pdf . A função satisfaz automaticamente as condições. Eu imagino que a mesma coisa funcione para e assim por diante. Como alternativa, apenas declare essa condição diretamente em e não em : deve existir algum "regular" que satisfaça .

f = Θ (n^{α})

$f = \Theta(n^\alpha)$

g

$g$

f = Θ (n^{α} \log^{β} n)

$f = \Theta(n^\alpha \log^\beta n)$

g

$g$

f

$f$

g

$g$

f = Θ (g)

$f = \Theta(g)$

Yuval Filmus

Bem, você afirmou que " monótono" era uma condição suficiente (e eu acreditava em você), então tentei trabalhar com isso. O teorema do mestre, dado em CLRS, por exemplo, aplica-se a , se não me engano, portanto, uma restrição às funções polilogarítmicas ou algo assim não é "técnica", mas enfraquece adequadamente o resultado. Levantar a "regularidade" para não ajuda, a propósito: já o tenho no caso crucial via regularidade de / (por suposição). Então, estou de volta ao meu comentário anterior, infelizmente. Se isso é realmente apenas técnico, não o vejo. Desigualdades demais.

g

$g$

f : n \mapsto 2^{n}

$f : n \mapsto 2^n$

g

$g$

c g

$cg$

C g

$Cg$

Raphael

Eu ainda acho que é um detalhe técnico. A condição com que você está preocupado é uma condição técnica. Para a maioria das funções que aparecem na prática, a condição será mantida. Você está solicitando a condição mais geral sob a qual o esboço de prova acima passa. Essa é uma pergunta interessante que tenho preguiça de responder.

Yuval Filmus

Prova rigorosa da validade da suposição ao usar o teorema do mestre

Respostas: