[algoritmi] esercizi su notazione asintotica
Ciao a tutti, ho problemi nel risolvere questo esercizio
1.Siano f(n) e g(n) funzioni positive. Allora dire se la seguente affermazione è vera oppure falsa e dare una dimostrazione oppure un controesempio \(\displaystyle \max(f(n), g(n))\) è \(\Theta (f(n)+ g(n)) \)
2. Siano f(n) e g(n) funzioni positive. Allora dire se la seguente affermazione è vera oppure falsa e dare una dimostrazione oppure un controesempio \(\displaystyle \max(f(n), g(n))\) è \(\Theta (f(n)/2+ g(n)/2) \)
Vorrei capire tutto il procedimento, non mi serve il risultato, è una prova d'esame e dovrei riuscire a farla da sola...grazie a tutti in anticipo!
non è appartiene sulla traccia ce scritto proprio è
1.Siano f(n) e g(n) funzioni positive. Allora dire se la seguente affermazione è vera oppure falsa e dare una dimostrazione oppure un controesempio \(\displaystyle \max(f(n), g(n))\) è \(\Theta (f(n)+ g(n)) \)
2. Siano f(n) e g(n) funzioni positive. Allora dire se la seguente affermazione è vera oppure falsa e dare una dimostrazione oppure un controesempio \(\displaystyle \max(f(n), g(n))\) è \(\Theta (f(n)/2+ g(n)/2) \)
Vorrei capire tutto il procedimento, non mi serve il risultato, è una prova d'esame e dovrei riuscire a farla da sola...grazie a tutti in anticipo!
non è appartiene sulla traccia ce scritto proprio è
Risposte
Ho modificato le tue formule matematiche per renderle più leggibili. In particolare ho usato il comando per scrivere max nel modo opportuno, aggiunto una parentesi mancante, sostituito è con $\in$ e $\theta$ (che da quanto ne so non viene usato in questo contesto) con $\Theta$. Se ho cambiato in qualche modo il significato ti prego di scusarmi e sentiti libero di rimodificare il tuo post e aggiungere spiegazioni se necessario.
Per quanto riguarda gli esercizi, richiedono l'uso della definizione e dell'induzione. Che difficoltà incontri? Hai problemi a comprendere la definizione o il procedimento di induzione (qualche tempo fa mi ero sforzato di presentare l'induzione in dettaglio e appena trovo il post aggiungo il link). La definizione di $\Theta$ è invece la seguente:
\[ f(n) \in \Theta\bigl(g(n)\bigr) \Leftrightarrow \exists k_1 > 0 \; \exists k_2 > 0 \; \exists n_0 \; \forall n > n_0 \; k_1\,g(n) \le f(n) \le k_2\,g(n) \]
Per quanto riguarda gli esercizi, richiedono l'uso della definizione e dell'induzione. Che difficoltà incontri? Hai problemi a comprendere la definizione o il procedimento di induzione (qualche tempo fa mi ero sforzato di presentare l'induzione in dettaglio e appena trovo il post aggiungo il link). La definizione di $\Theta$ è invece la seguente:
\[ f(n) \in \Theta\bigl(g(n)\bigr) \Leftrightarrow \exists k_1 > 0 \; \exists k_2 > 0 \; \exists n_0 \; \forall n > n_0 \; k_1\,g(n) \le f(n) \le k_2\,g(n) \]
Ho trovato la discussione in cui mi ero un po' dilungato nel definire e mostrare un esempio dell'uso dell'induzione: post555494.html?hilit=induzione#p555494
piccolo indizio oltre quelli del buon apatriarca:
la somma tra complessità è così definita se non la ricordi: $f(n) + g(n) in O(\max{f(n),g(n)})$ (uguale per $\Theta$ e $\Omega$).
la somma tra complessità è così definita se non la ricordi: $f(n) + g(n) in O(\max{f(n),g(n)})$ (uguale per $\Theta$ e $\Omega$).
scusate ma non so proprio da dove partire, il prof non ha mai spiegato nulla! si limitava a leggere le slide!
"mena91":
non è appartiene sulla traccia ce scritto proprio è
$in$ vuol dire è, nel senso appartiene a tal insieme oppure leggilo come tal funzione è di complessità....
Comunque veniamo al problema.
Il primo passo, è utilizzare semplicemente la definizione di $\Theta$ che ti ha riproposto apatriarca (per il momento lasciamo un attimo il formalismo induttivo), basta che sostituisci.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo