Risolvere l'equazione ricorsiva $T(n)=T(k)+T(n-k-1)+O(n)$
La domanda è chiara nel titolo. Sto cercando di risolvere questa ricorsione come parte della dimostrazione che il caso peggiore dell'algoritmo Quicksort si verifica quando$k=0$, ma non posso farlo. Potrei fare i seguenti casi specifici (usando ripetutamente la stessa ricorsione):
1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$
Qualcuno può aiutarmi a risolvere questo caso generale (o almeno suggerire qualche altro modo per dimostrare che il caso peggiore è $k=0$)?
PS Non conosco il teorema del Maestro, quindi apprezzerei una soluzione senza usarlo (nel caso in cui sia applicabile qui).
Risposte
Considera la ricorrenza $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$che è una formalizzazione del tempo di esecuzione nel caso peggiore di quicksort. Dimostriamo per induzione che si raggiunge il massimo$k = 0$ (o $k = n$). Lo mostreremo mentre allo stesso tempo lo mostreremo$T(n) = \frac{n(n+1)}{2}$.
Il case base, $n=0$, è chiaro. Supponiamo ora$T(m) = \frac{m(m+1)}{2}$ per tutti $m \leq n$e considera $T(n+1)$. La funzione$T(k)$ è convesso sull'intervallo $[0,n]$ (lo estendiamo a valori reali usando la stessa formula), quindi il massimo di $T(k) + T(n-k)$ è raggiunto a $k=0$ (o $k=n$). Perciò$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$
Invece di discutere usando la convessità, possiamo anche argomentare direttamente: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ che è chiaramente massimizzato (in modo univoco) quando $k = 0$ o $k = n$.