[Algoritmi] Metodo di sostituzione help!!!
Salve a tutti,questo è il mio primo intervento nel forum.Come da titolo sto preparando l'esame di algoritmi e strutture dati e devo per prima cosa cercare di capire i metodi per risolvere le ricorrenze.Ho deciso di iniziare dal metodo di sostituzione perchè leggendo sul libro risulta essere il più facile.Ho capito di tale metodo che bisogna innanzitutto ipotizzare la soluzione della ricorrenza e poi dimostrare tale ipotesi con l'induzione matematica.Ci sono però delle cose che non ho capito riguardo il procedimento del metodo di sostituzione.Per capirci meglio è utile iniziare con un esempio del tipo:
\begin{cases}O(1) \mbox{ se } n=1\\ 2T(n/2)+n \mbox{ se } n>1\end{cases}.
Innanzitutto ho ipotizzato che la soluzione della ricorrenza fosse O(nlog(n)).Quindi bisogna dimostrare che T(n) <=cnlog(n).Ho ipotizzato che il limite sia valido per n=n/2 quindi T(n/2) <= c[(n/2)log(n/2)].Sono andato a sostituire questo valore nella ricorrenza ottenendo:
cnlog(n/2)+n
e facendo i dovuti calcoli,per le proprietà dei logaritmi ho ottenuto
cnlog(n)-cnlog(2)+n
Da qui in poi non sono riuscito più ad andare avanti,come faccio a dimostrare che la soluzione della mia ricorrenza è proprio O(nlog(n)) ?Che calcoli bisogna fare per arrivare a tale soluzione? Ringrazio in anticipo tutti coloro che mi aiuteranno!!!
\begin{cases}O(1) \mbox{ se } n=1\\ 2T(n/2)+n \mbox{ se } n>1\end{cases}.
Innanzitutto ho ipotizzato che la soluzione della ricorrenza fosse O(nlog(n)).Quindi bisogna dimostrare che T(n) <=cnlog(n).Ho ipotizzato che il limite sia valido per n=n/2 quindi T(n/2) <= c[(n/2)log(n/2)].Sono andato a sostituire questo valore nella ricorrenza ottenendo:
cnlog(n/2)+n
e facendo i dovuti calcoli,per le proprietà dei logaritmi ho ottenuto
cnlog(n)-cnlog(2)+n
Da qui in poi non sono riuscito più ad andare avanti,come faccio a dimostrare che la soluzione della mia ricorrenza è proprio O(nlog(n)) ?Che calcoli bisogna fare per arrivare a tale soluzione? Ringrazio in anticipo tutti coloro che mi aiuteranno!!!
Risposte
Ciao Raider991!
Il tuo procedimento è corretto, ti manca solo l'ultima parte di ragionamento su quanto ottenuto alla fine: $cn\log(n) - cn\log(2) + n$. Per $n$ arbitrariamente grande hai (idealmente) che $c\log(2)$ (costante) è trascurabile e pertanto puoi considerare che $-cn\log(2) \rightarrow -n$. Questo $-n$ si "semplifica" (sempre idealmente) con il $+n$ posto di seguito in ciò che ottieni inizialmente dalla ricorrenza e pertanto ti rimane solo $n\log(n)$
.
Essendoci passato capisco come non sia sempre immediato ragionare in questo modo quando si muovono i primi passi con le ricorrenze.
Spero di esserti stato d'aiuto.
Il tuo procedimento è corretto, ti manca solo l'ultima parte di ragionamento su quanto ottenuto alla fine: $cn\log(n) - cn\log(2) + n$. Per $n$ arbitrariamente grande hai (idealmente) che $c\log(2)$ (costante) è trascurabile e pertanto puoi considerare che $-cn\log(2) \rightarrow -n$. Questo $-n$ si "semplifica" (sempre idealmente) con il $+n$ posto di seguito in ciò che ottieni inizialmente dalla ricorrenza e pertanto ti rimane solo $n\log(n)$
.Essendoci passato capisco come non sia sempre immediato ragionare in questo modo quando si muovono i primi passi con le ricorrenze.
Spero di esserti stato d'aiuto.
"onlyReferee":
Ciao Raider991!
Il tuo procedimento è corretto, ti manca solo l'ultima parte di ragionamento su quanto ottenuto alla fine: $cn\log(n) - cn\log(2) + n$. Per $n$ arbitrariamente grande hai (idealmente) che $c\log(2)$ (costante) è trascurabile e pertanto puoi considerare che $-cn\log(2) \rightarrow -n$. Questo $-n$ si "semplifica" (sempre idealmente) con il $+n$ posto di seguito in ciò che ottieni inizialmente dalla ricorrenza e pertanto ti rimane solo $n\log(n)$
Essendoci passato capisco come non sia sempre immediato ragionare in questo modo quando si muovono i primi passi con le ricorrenze.
Spero di esserti stato d'aiuto.
si,mi sei stato estremamente d'aiuto,sopratutto perchè questo il libro non lo dice.Non ho capito bene una cosa però,possiamo trascurare il valore di clog2 poichè è una costante o perchè è un valore estremamente piccola da poterlo trascurare?Grazie ancora per la tua risposta.
Prima di tutto vorrei osservare che in informatica, quando si scrive \(\log,\) si intende nel \(99\%\) delle volte \(\log_2\). Anche se di fatto la base del logaritmo non è in questo caso particolarmente significativa, direi che si può semplificare la formula usando \( \log_2(2) = 1 \). Inoltre, siccome vogliamo semplicemente dimostrare la relazione \( T(n) \leq k\,n\,\log(n) \) per un qualche \(k\) e per \(n\) sufficientemente grande, è in realtà sufficiente osservare che possiamo prendere \( k \geq 1. \) Facendo queste semplificazioni si ottiene che la formula finale è \( T(n) \leq k\,n\,\log(n) - (k - 1)\,n \leq k\,n\,\log(n). \) L'ultimo passaggio è possibile perché sia \(k - 1\) che \(n\) sono positivi per ipotesi.
"Raider991":
si,mi sei stato estremamente d'aiuto,sopratutto perchè questo il libro non lo dice.Non ho capito bene una cosa però,possiamo trascurare il valore di clog2 poichè è una costante o perchè è un valore estremamente piccola da poterlo trascurare?Grazie ancora per la tua risposta.
In realtà la motivazione esatta è che, trattandosi di una costante (sempre parlando rispetto ad $n$) e poiché eseguiamo un'analisi asintotica su $O$ (con $o, \theta$ la situazione comunque non cambia), questa non influisce minimamente sul comportamento della funzione $n\log(n)$. Difatti se noti proprio nel mio post precedente "semplifica" l'ho scritto appositamente tra virgolette per rendere il senso ma non perché i due valori si annullino (questo accade soltanto a livello algebrico non asintotico).
Di nulla, sempre un piacere essere d'aiuto.
"onlyReferee":
[quote="Raider991"]
si,mi sei stato estremamente d'aiuto,sopratutto perchè questo il libro non lo dice.Non ho capito bene una cosa però,possiamo trascurare il valore di clog2 poichè è una costante o perchè è un valore estremamente piccola da poterlo trascurare?Grazie ancora per la tua risposta.
In realtà la motivazione esatta è che, trattandosi di una costante (sempre parlando rispetto ad $n$) e poiché eseguiamo un'analisi asintotica su $O$ (con $o, \theta$ la situazione comunque non cambia), questa non influisce minimamente sul comportamento della funzione $n\log(n)$. Difatti se noti proprio nel mio post precedente "semplifica" l'ho scritto appositamente tra virgolette per rendere il senso ma non perché i due valori si annullino (questo accade soltanto a livello algebrico non asintotico).
Di nulla, sempre un piacere essere d'aiuto.[/quote]
Ecco allora qui ho dei dubbi,mi spiego meglio.Nel mio caso è stato facile ipotizzare clog2 come trascurabile (poichè è una costante) e in questo modo ho potuto "semplificare" semplicemente -n con +n avendo che T(n)=cnlogn che è vera per ogni c>=1.Il mio dubbio è: e se avessi avuto un valore diverso da +n?Cioè se io mi fossi trovato in questa situazione T(n)=cnlogn-cnlog2+1 come avrei potuto eliminare il -n che rimaneva al secondo termine?Per quanto detto prima infatti avrei potuto considerare clog2 e +1 come costanti e quindi ininfluenti sul comportamento della funzione,avendo così che T(n)=cnlogn-n.A questo punto come avrei dovuto fare?
Il mio consiglio, soprattutto all'inizio è di cercare di essere il più formali possibili perché cercare di richiamare "idee intuitive" quando ancora questa intuizione non si è formata può essere deleterio.
Se la relazione fosse stata \( T(n) \leq c\,n\,\log(n) - c\,n\,\log(2) + 1 \) sarebbe stato sufficiente osservare che \( c\,\log(2)\,n \) è certamente maggiore di \(1\) per un \(n\) sufficientemente grande. \( - c\,n\,\log(2) + 1 \) è allora un numero negativo e quindi \( T(n) \leq c\,n\,\log(n) \).
Se la relazione fosse stata \( T(n) \leq c\,n\,\log(n) - c\,n\,\log(2) + 1 \) sarebbe stato sufficiente osservare che \( c\,\log(2)\,n \) è certamente maggiore di \(1\) per un \(n\) sufficientemente grande. \( - c\,n\,\log(2) + 1 \) è allora un numero negativo e quindi \( T(n) \leq c\,n\,\log(n) \).
"apatriarca":
. \( - c\,n\,\log(2) + 1 \) è allora un numero negativo e quindi \( T(n) \leq c\,n\,\log(n) \).
Non ho capito bene questa parte me la puoi spiegare meglio.Cosa centra che è un numero negativo?E perchè hai detto che dato che -cnlog2+1 è un numero negativo allora T(n)<=cnlogn? Scusate se chiedo sempre approfondimenti e che non sono molto sicuro di padroneggiare al meglio questi concetti e visto che il prof. ha detto che sono metodologie fondamentali per la risoluzione degli esercizi,ho a cuore imparare tutto bene.Grazie ancora per l'aiuto che mi state dando!!!
Tu stai cercando di dimostrare che \(T(n/2) \leq c\,(n/2)\,\log(n/2)\) implica che \(T(n) \leq c\,n\,\log(n).\) Per dimostrarlo riscrivi per prima cosa la definizione di \(T(n)\) in funzione di \(T(n/2)\) e poi sostituisci a quest'ultimo la parte destra della relazione assunta come ipotesi. A questo punto sono leciti tutti i passaggi algebrici e le approssimazioni che, incrementando o mantenendo uguale il valore ti portano al risultato voluto. Eliminando una parte della tua espressione che sai essere negativa è quindi in questo senso utile. Spero sia più chiaro ora, nel caso cerco di approfondire meglio più tardi scrivendo su un pc invece che sul tablet.
ho capito ora,grazie ancora per l'aiuto alla prossima
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo