[Algoritmi] Equazione di ricorrenza
Mi sto preparando all'esame di Algoritmi e Strutture Dati ma non avendo potuto seguire le lezioni sto avendo un po' di difficoltà con le equazioni di ricorrenza.
Premetto che ho già letto alcune discussioni sul forum e svariati pdf al riguardo.
In un tema d'esame degli anni precedenti era presente il seguente esercizio:
2) La soluzione all'equazione di riccorenza $ T(n)=2T(n/2) + n/2 $ è (risposta multipla):
□ $ O(logn) $ □ $ O(n) $ □ $ O(nlogn) $ □ $ O(n^2) $ □ $ O(n^2/logn) $
Io ho ragionato nel seguente modo applicando il teorema Master:
$ a=2 $, $ b=2 $ e $ f(n)=n/2 $
calcolo $ n^(\log_b a) $: $ n $
Confrontando asintoticamente $ f(n) $ e $ n^(\log_b a) $ siamo nel 2° caso del Teorema Master quindi la soluzione è:
$ Theta (nlogn) $
Dovrebbe essere corretta ma come mai non è presente tra le soluzioni dell'esercizio?? Come si risolve?
Grazie!
Premetto che ho già letto alcune discussioni sul forum e svariati pdf al riguardo.
In un tema d'esame degli anni precedenti era presente il seguente esercizio:
2) La soluzione all'equazione di riccorenza $ T(n)=2T(n/2) + n/2 $ è (risposta multipla):
□ $ O(logn) $ □ $ O(n) $ □ $ O(nlogn) $ □ $ O(n^2) $ □ $ O(n^2/logn) $
Io ho ragionato nel seguente modo applicando il teorema Master:
$ a=2 $, $ b=2 $ e $ f(n)=n/2 $
calcolo $ n^(\log_b a) $: $ n $
Confrontando asintoticamente $ f(n) $ e $ n^(\log_b a) $ siamo nel 2° caso del Teorema Master quindi la soluzione è:
$ Theta (nlogn) $
Dovrebbe essere corretta ma come mai non è presente tra le soluzioni dell'esercizio?? Come si risolve?
Grazie!
Risposte
In che senso non c'è? È la terza risposta..
"apatriarca":
In che senso non c'è? È la terza risposta..
Non c'è nel senso che la terza risposta non è in notazione $ Theta $ ma in notazione $ O $. E' valida comunque?
Forse la mia confusione deriva dal fatto che nella correzione dell'esercizio che ho trovato (senza passaggi) vengono marcate le risposte 3, 4 e 5 come corrette. Come mai? Come può avere più soluzioni?
Quale sono le definizioni di \(O\) e \(\Theta\)? Nel tuo caso hai che \(\Theta(n\,\log\,n)\) allora sarà necessariamente anche \(O(n\,\log\,n).\) Ma siccome \(O\) si riferisce semplicemente ad una limitazione superiore e non viene richiesto che questa limitazione sia "minima", allora anche la quarta e quinta risposta hanno senso.
Ti consiglio di leggere questa slide che ho utilizzato il primo anno per la notazione asintotica. Poi studiando gli algoritmi di sorting, arriva l'illuminazione vera e propria sui vari limiti asintotici.
http://twiki.di.uniroma1.it/pub/Infogen ... tolo_2.pdf
http://twiki.di.uniroma1.it/pub/Infogen ... tolo_2.pdf
Grazie ad entrambi per le risposte. Ho letto anche il pdf allegato e ho compreso meglio le tre notazioni.
Quello che non capisco ancora è il motivo per cui sono valide anche la riposta 4 e 5. E' in base al comportamento asintotico della funzione? Come si determina se anche le altre risposte sono comprese in $ Theta (nlogn) $ ?
Quello che non capisco ancora è il motivo per cui sono valide anche la riposta 4 e 5. E' in base al comportamento asintotico della funzione? Come si determina se anche le altre risposte sono comprese in $ Theta (nlogn) $ ?
\(O(n\,\log\,n)\), \(O(n)\), \(\Theta(n\,\log\,n),\) .. sono insiemi di funzioni che rispettano una qualche proprietà definita nella loro definizione. Nel caso delle O grandi, c'è una relazione di inclusione tra questi insiemi: se qualcosa è superiormente limitato da \(n^2\) sarà infatti limitato superiormente anche da \(n^3\) o \(n^2\,\log\,n\). Abbiamo quindi che
\[ O(\log\,n) \subset O(n) \subset O(n\,\log\,n) \subset O(n^2/\log\,n) \subset O(n^2). \]
Trovato quindi l'insieme che limita più strettamente la funzione, devi anche scegliere come risposte corrette tutti gli altri insiemi più grandi.
Anche se formalmente la soluzione è effettivamente questa, credo che il problema sia in qualche modo "a trabocchetto". Nell'uso comunque si è in effetti solo interessati all'insieme che limita più strettamente la funzione (in questo caso \(n\,\log\,n\)) e si ignorano le altre.
Nota inoltre che la relazione di inclusione non vale per \(\Theta\) e funziona in modo inverso per \(\Omega\).
\[ O(\log\,n) \subset O(n) \subset O(n\,\log\,n) \subset O(n^2/\log\,n) \subset O(n^2). \]
Trovato quindi l'insieme che limita più strettamente la funzione, devi anche scegliere come risposte corrette tutti gli altri insiemi più grandi.
Anche se formalmente la soluzione è effettivamente questa, credo che il problema sia in qualche modo "a trabocchetto". Nell'uso comunque si è in effetti solo interessati all'insieme che limita più strettamente la funzione (in questo caso \(n\,\log\,n\)) e si ignorano le altre.
Nota inoltre che la relazione di inclusione non vale per \(\Theta\) e funziona in modo inverso per \(\Omega\).
Forse ho capito il tuo dubbio.
Allora abbiamo che la nostra equazione di ricorrenza ha un tempo di esecuzione pari a $\Theta(nlogn)$, quindi sta a significare che il nostro algoritmo cresce esattamente con un tempo pseudolineare ed ha limite superiore uguale al limite inferiore.
$\Omega(f(x)) = $il tempo del nostro algoritmo è almeno $f(x)$ e non può essere eseguito con un tempo minore.
$\O(f(x)) =$il tempo del nostro algoritmo cresce al massimo $f(x)$ e quindi l'esecuzione del nostro algoritmo con input x, non oltrepasserà mai questo limite.
Le altre due risposte sono vere perchè, se è vero che il tuo algoritmo avrà tempo di esecuzione al massimo in $nlogn$, allora sarà anche vero, facendo una stima molto lasca, che avrà tempo di esecuzione anche minore a $n^2$ e $n^2/logn$.
$O(nlogn) < O(n^2/logn) < O(n^2)$
Prendi per esempio il merge sort, ha una complessità temporale pari a $\Theta(nlogn)$. Se dicessimo che è limitata superiormente da un $O(n^2)$ abbiamo comunque ragione dato che non potrà mai superare questo limite, ma lo stiamo dicendo in modo poco raffinato e preciso perchè è un $\Theta(nlogn)$.
Spero di non averti confuso.
Allora abbiamo che la nostra equazione di ricorrenza ha un tempo di esecuzione pari a $\Theta(nlogn)$, quindi sta a significare che il nostro algoritmo cresce esattamente con un tempo pseudolineare ed ha limite superiore uguale al limite inferiore.
$\Omega(f(x)) = $il tempo del nostro algoritmo è almeno $f(x)$ e non può essere eseguito con un tempo minore.
$\O(f(x)) =$il tempo del nostro algoritmo cresce al massimo $f(x)$ e quindi l'esecuzione del nostro algoritmo con input x, non oltrepasserà mai questo limite.
Le altre due risposte sono vere perchè, se è vero che il tuo algoritmo avrà tempo di esecuzione al massimo in $nlogn$, allora sarà anche vero, facendo una stima molto lasca, che avrà tempo di esecuzione anche minore a $n^2$ e $n^2/logn$.
$O(nlogn) < O(n^2/logn) < O(n^2)$
Prendi per esempio il merge sort, ha una complessità temporale pari a $\Theta(nlogn)$. Se dicessimo che è limitata superiormente da un $O(n^2)$ abbiamo comunque ragione dato che non potrà mai superare questo limite, ma lo stiamo dicendo in modo poco raffinato e preciso perchè è un $\Theta(nlogn)$.
Spero di non averti confuso.
Grazie ad entrambi! Il mio dubbio era proprio quello.. mi sembra di aver capito meglio ora!
Vediamo quest'altro esercizio..
2) La soluzione all'equazione di riccorenza $ T(n)=8T(n/2) + n^2/2 $ è (risposta multipla):
□ $ O(logn) $ □ $ Omega(nlog^2n) $ □ $ O(n^2logn) $ □ $ O(n^3) $ □ $ Theta(5n^3) $
Applico il Teorema Master:
$ a=8 $, $ b=2 $ e $ f(n)=n^2/2 $
calcolo $ n^(\log_b a) $: $ n^3 $
Confrontando asintoticamente $ f(n) $ e $ n^(\log_b a) $ siamo nel 1° caso del Teorema Master quindi la soluzione è:
$ Theta (n^3) $
Quindi le soluzioni sono:
□ $ O(n^3) $
□ $ Theta(5n^3) $
anche $ Omega(nlog^2n) $ ?
Vediamo quest'altro esercizio..
2) La soluzione all'equazione di riccorenza $ T(n)=8T(n/2) + n^2/2 $ è (risposta multipla):
□ $ O(logn) $ □ $ Omega(nlog^2n) $ □ $ O(n^2logn) $ □ $ O(n^3) $ □ $ Theta(5n^3) $
Applico il Teorema Master:
$ a=8 $, $ b=2 $ e $ f(n)=n^2/2 $
calcolo $ n^(\log_b a) $: $ n^3 $
Confrontando asintoticamente $ f(n) $ e $ n^(\log_b a) $ siamo nel 1° caso del Teorema Master quindi la soluzione è:
$ Theta (n^3) $
Quindi le soluzioni sono:
□ $ O(n^3) $
□ $ Theta(5n^3) $
anche $ Omega(nlog^2n) $ ?
Diccelo tu.. La tua equazione di ricorrenza rispetta la condizione nella definizione di \( \Omega(n\,\log^2\,n) \)?
"apatriarca":
Diccelo tu.. La tua equazione di ricorrenza rispetta la condizione nella definizione di \( \Omega(n\,\log^2\,n) \)?
Credo di si essendo la soluzione principale in notazione $ Theta $ ..
Sì, la soluzione è corretta.
Ma come? Se il nostro algoritmo è limitato inferiormente da un $\Omega(n^3)$ come lo potrebbe essere anche per un $\Omega(nlog^2n)$???
Del limite superiore si può dare un'approssimazione lasca, ma del limite inferiore no.
Mi sbaglio? Se si perchè?
Del limite superiore si può dare un'approssimazione lasca, ma del limite inferiore no.
Mi sbaglio? Se si perchè?
Se \(f \in \Omega(n^3)\) allora avrai che \( f(x) \geq k\,n^3 \) (condizioni solite.. non le sto a scrivere che tanto le conosciamo bene tutti). Ma \( n^3 > n\,\log^2\,n \) e quindi avremo certamente che vale anche \( f(x) > k\,n\,\log^2\,n \) e quindi \( f \in \Omega(n\,\log^2\,n)\). Non capisco il tuo dubbio sinceramente.
Ok stavo pensando a qualche caso reale. Es. Selection Sort ha una complessità pari a $\Theta(n^2)$ e quindi non potrebbe mai avere un limite inferiore pari a $\Omega(nlog^2n)$.
Ook capito.
Ook capito.
Quando si parla di limite superiore e inferiore si fa spesso riferimento ad un qualche oggetto che sia in qualche modo minimo o massimo tra gli oggetti con quella proprietà. Tuttavia, se si parla di essere limitata superiormente o inferiormente il discorso cambia e non stiamo necessariamente dicendo che la funzione considerata è il limite superiore o inferiore. Non è insomma necessariamente minimale o massimale. Non so se sono riuscito a trasmetterti l'idea.
Si chiaro 
Grazie
Grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo