Résolution de l'équation récursive $T(n)=T(k)+T(n-k-1)+O(n)$

Dec 31 2020

La question est claire dans le titre. J'essaie de résoudre cette récursivité pour montrer que le pire des cas d'algorithme de tri rapide se produit lorsque$k=0$, mais je ne peux pas le faire. Je pourrais faire les cas spécifiques suivants (en utilisant à plusieurs reprises la même récursivité):

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

Quelqu'un peut-il m'aider à résoudre ce cas général (ou au moins suggérer un autre moyen de prouver que le pire des cas est $k=0$)?

PS Je ne connais pas le théorème du Maître, donc j'apprécierais une solution sans utiliser cela (au cas où cela serait applicable ici).

Réponses

2 YuvalFilmus Dec 31 2020 at 21:11

Considérez la récurrence $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$qui est une formalisation du pire des cas d'exécution du tri rapide. Montrons par récurrence que le maximum est atteint à$k = 0$ (ou alors $k = n$). Nous allons montrer cela tout en montrant que$T(n) = \frac{n(n+1)}{2}$.

Le cas de base, $n=0$, est clair. Supposons maintenant que$T(m) = \frac{m(m+1)}{2}$ pour tous $m \leq n$, et considérez $T(n+1)$. La fonction$T(k)$ est convexe sur l'intervalle $[0,n]$ (nous l'étendons aux valeurs réelles en utilisant la même formule), et donc le maximum de $T(k) + T(n-k)$ est atteint à $k=0$ (ou alors $k=n$). Par conséquent$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$

Au lieu d'argumenter en utilisant la convexité, nous pouvons également argumenter directement: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ qui est clairement maximisé (uniquement) lorsque $k = 0$ ou alors $k = n$.