 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[HELP] dimostrare complessità quicksort
Clicca QUI per vedere il messaggio nel forum |
| The external |
Sul libro di testo c'è scritto: "In effetti è semplice applicare il _metodo di sostituzione_ per dimostrare che la ricorrenza T(n) = T(n-1) + teta(n) ha soluzione T(n) = teta(n2).
Io ho proceduto così:
Esiste d, n0 t.c T(n) <= dn2 T(n) >= dn2
Per dimostrare la prima:
Per ogni m < n T(m) <= dm2 m = n-1 che è < n
T(n-1) <= d(n-1)2 sostituzione
T(m) <= d(n-1)2 + teta(n) = d(n-1)2 + cn = d(n2 -2n + 1) + cn = dn2 - 2dn + d + cn
T(m) <= dn2 + (-2d + c)n + d
Non so se ho fatto bene a raccogliere in quel modo però sono arrivato alla conclusione che -2d + c <= 0 ---> d >= c/2
Il problema è quella benedetta costante d isolata lì a destra. Ora è vero che vale per ogni n >= n0 e quindi per valori di n da un certo valore in poi è vero essendo d costante... quindi posso concludere così o c'è una soluzione migliore?
So che si può usare una sommatoria per dimostrare ma il libro dice usando il metodo di sostituzione.
Grazie |
|
|
|
|
