Resolvendo a equação recursiva $T(n)=T(k)+T(n-k-1)+O(n)$

Question

A questão está clara no título. Estou tentando resolver esta recursão como parte de mostrar que o pior caso do algoritmo de classificação rápida ocorre quando$k=0$, mas não pode fazer isso. Eu poderia fazer os seguintes casos específicos (usando repetidamente a mesma recursão):

1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$

Alguém pode me ajudar a resolver este caso geral (ou pelo menos sugerir alguma outra maneira de provar que o pior caso é $k=0$)?

PS Não conheço o teorema do Mestre, então gostaria de encontrar uma solução sem usá-lo (caso seja aplicável aqui).

Answer 1

Considere a recorrência $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$que é uma formalização do pior caso de tempo de execução do quicksort. Vamos mostrar por indução que o máximo é atingido em$k = 0$ (ou $k = n$) Vamos mostrar isso e, ao mesmo tempo, mostrar que$T(n) = \frac{n(n+1)}{2}$.

O caso básico, $n=0$, está claro. Agora suponha que$T(m) = \frac{m(m+1)}{2}$ para todos $m \leq n$e considere $T(n+1)$. A função$T(k)$ é convexo no intervalo $[0,n]$ (nós o estendemos para valores reais usando a mesma fórmula), e assim o máximo de $T(k) + T(n-k)$ é alcançado em $k=0$ (ou $k=n$) Portanto$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$

Em vez de argumentar usando convexidade, também podemos argumentar diretamente: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ que é claramente maximizado (exclusivamente) quando $k = 0$ ou $k = n$.