Relazioni di ricorrenza
Salve ragazzi avrei bisogno di risolvere il seguente esercizio, in cui si chiede prima di determinare e poi risolvere una relazione di ricorrenza.
Ecco il testo.
Considera la seguente variante di MergeSort in cui una delle due chiamate ricorsive è sostituita da una chiamata a InsertionSort:
algortimo MergeInsertionSort ( array A di elementi , interi i e j )
if (i
MergeInsertionSort (A,i,m)
InsertionSort (A,m+1,j)
Merge (A[i,m],A[m+1,j])
Sia T(n) il tempo di esecuzione dell'algoritmo MergeInsertionSort nel caso peggiore in funzione della dimensione n dell'array A .Determina e risolvi una relazione di ricorrenza per T(n). Qual'è il tempo di esecuzione di MergeInsertionSort nel caso migliore?Perchè?
Ecco il testo.
Considera la seguente variante di MergeSort in cui una delle due chiamate ricorsive è sostituita da una chiamata a InsertionSort:
algortimo MergeInsertionSort ( array A di elementi , interi i e j )
if (i
MergeInsertionSort (A,i,m)
InsertionSort (A,m+1,j)
Merge (A[i,m],A[m+1,j])
Sia T(n) il tempo di esecuzione dell'algoritmo MergeInsertionSort nel caso peggiore in funzione della dimensione n dell'array A .Determina e risolvi una relazione di ricorrenza per T(n). Qual'è il tempo di esecuzione di MergeInsertionSort nel caso migliore?Perchè?
Risposte
Quali sono le tue considerazioni sul problema? Dove trovi difficolta'?
a scrivere la relazione di ricorrenza innanzitutto
Allora ti scrivo quale penso sia la risposta e vediamo se puoi aiutarmi.
Il tempo di esecuzione è espresso mediante la seguente relazione di ricorrenza:
T(n) = T(n/2) + O(n^2 / 4) + O(n-1)
Io l'ho pensata così:
supponendo che n sia pari alla dimensione dell'array (ovvero i+j)
T(n/2) è il tempo speso per effettuare la prima chiamata ricorsiva
mentre il selection ordina in O(n^2) quindi richiamando solo n/2 elementi allora sono arrivato a O(n^2 / 4)
mentre la Merge impiega esattamente il numero di elementi costituenti le due sottosequenze da fondere meno uno
Ora come la risolvo sempre che sia corretta
Ho tre modi di risolverla ,Teorema Master ,Iterazione e Sostituzione
prima vorrei essere certo però che la relazione di ricorrenza sia corretta ,in particolare ho dei dubbi sulla seconda chiamata
Il tempo di esecuzione è espresso mediante la seguente relazione di ricorrenza:
T(n) = T(n/2) + O(n^2 / 4) + O(n-1)
Io l'ho pensata così:
supponendo che n sia pari alla dimensione dell'array (ovvero i+j)
T(n/2) è il tempo speso per effettuare la prima chiamata ricorsiva
mentre il selection ordina in O(n^2) quindi richiamando solo n/2 elementi allora sono arrivato a O(n^2 / 4)
mentre la Merge impiega esattamente il numero di elementi costituenti le due sottosequenze da fondere meno uno
Ora come la risolvo sempre che sia corretta
Ho tre modi di risolverla ,Teorema Master ,Iterazione e Sostituzione
prima vorrei essere certo però che la relazione di ricorrenza sia corretta ,in particolare ho dei dubbi sulla seconda chiamata
Ciao,
ok sul ragionamento della ricorrenza (è un algoritmo divide-et-impera dimezzato su un solo ramo); ti consiglio di non considerare le costanti, ti complichi la vita. Calcola la ricorrenza:
$T(n/2) + O(n^2) + O(n)$
per trattare questi particolari casi hai più possibilità, da quelle più precise a quelle più "valutative".
Es. per dare una complessità velocemente considera solo la complessità dominante sulle funzioni libere:
$T(n/2) + O(n^2) + O(n) >= T(n/2) + O(n^2)$
(anche se facendo ciò trovarai una complessità inferiore sull'algoritmo diciamo un $\Omega()$ o meglio $\omega()$ stretto, ma son discorsi cha hanno il tempo che trovano...)
oppure vedi questo post, dove io ed apatriarca ci siamo un po' dilungati per trovare un metodo più preciso possibile su queste particolari ricorrenze.
PS: questo è un argomento di Informatica.
ok sul ragionamento della ricorrenza (è un algoritmo divide-et-impera dimezzato su un solo ramo); ti consiglio di non considerare le costanti, ti complichi la vita. Calcola la ricorrenza:
$T(n/2) + O(n^2) + O(n)$
per trattare questi particolari casi hai più possibilità, da quelle più precise a quelle più "valutative".
Es. per dare una complessità velocemente considera solo la complessità dominante sulle funzioni libere:
$T(n/2) + O(n^2) + O(n) >= T(n/2) + O(n^2)$
(anche se facendo ciò trovarai una complessità inferiore sull'algoritmo diciamo un $\Omega()$ o meglio $\omega()$ stretto, ma son discorsi cha hanno il tempo che trovano...)
oppure vedi questo post, dove io ed apatriarca ci siamo un po' dilungati per trovare un metodo più preciso possibile su queste particolari ricorrenze.
PS: questo è un argomento di Informatica.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo