Dimostrazione Complessità
Salve, chiedo una mano nello svolgimento di un eserzio.
L'esercizio è su delle dimstrazioni di affermazioni, ma che lo svolgimento discosta dalle normali dimstrazioni di appartenenza della classi di complessità.
Io non capisco che diavolo fare, visto che non sono i canonici esercizi:
esercizio:
Per ognuna delle seguenti coppie di funzioni $f(n)$ e $g(n)$, proporre un costante $c$ appriata tale per cui $f(n) <= c * g(n)$ per tutti gli $n > 1$.
1.$ f(n) = n^2 + n + 1$ , $g(n) = 2n^3$
2. $f(n) = n*sqrt(n) + n^2$ , $g(n) = n^2$
3. $f(n) = n^2 - n + 1$ , $g(n) = n^2/2$
Ho abbozzato una possibile risoluzione dell'esercizio 1. basandomi su una dimostrazione di appartenenza di una determinata classe O-grande, ma l'esercizio dice di trovare la costante $c$ per ogni $n>1$ e questo mi crea problemi:
Soluzione abbozzata:
1. $n^2 +n + 1 <= n^2 + n^2 +1 <= n^2 + n^2 + n^2$ (per un qualche $n$) $ = 3n^2 <= c*2n^3 $
$c >= 3/2n$
cosa che è false, perchè l'affermazione è vera.
perpiacere fatemi vedere una dimstrazione rigorosa, cosa che non riesco a fare con esercizi non canonici.
grazie a chi aiuta
L'esercizio è su delle dimstrazioni di affermazioni, ma che lo svolgimento discosta dalle normali dimstrazioni di appartenenza della classi di complessità.
Io non capisco che diavolo fare, visto che non sono i canonici esercizi:
esercizio:
Per ognuna delle seguenti coppie di funzioni $f(n)$ e $g(n)$, proporre un costante $c$ appriata tale per cui $f(n) <= c * g(n)$ per tutti gli $n > 1$.
1.$ f(n) = n^2 + n + 1$ , $g(n) = 2n^3$
2. $f(n) = n*sqrt(n) + n^2$ , $g(n) = n^2$
3. $f(n) = n^2 - n + 1$ , $g(n) = n^2/2$
Ho abbozzato una possibile risoluzione dell'esercizio 1. basandomi su una dimostrazione di appartenenza di una determinata classe O-grande, ma l'esercizio dice di trovare la costante $c$ per ogni $n>1$ e questo mi crea problemi:
Soluzione abbozzata:
1. $n^2 +n + 1 <= n^2 + n^2 +1 <= n^2 + n^2 + n^2$ (per un qualche $n$) $ = 3n^2 <= c*2n^3 $
$c >= 3/2n$
cosa che è false, perchè l'affermazione è vera.
perpiacere fatemi vedere una dimstrazione rigorosa, cosa che non riesco a fare con esercizi non canonici.
grazie a chi aiuta
Risposte
Magari non è il metodo migliore, ma io ragionerei così (mi riferisco all'esercizio 1)
[tex]f(1)=3>g(1)=2[/tex] e [tex]f(2)=7f(n)[/tex], quindi va già bene così, basta scegliere [tex]c=1[/tex], oppure il più piccolo [tex]c[/tex] che soddisfa la disuguaglianza [tex]c=7/16[/tex].
[tex]f(1)=3>g(1)=2[/tex] e [tex]f(2)=7
ma dai...hai ragione.
Hai applicato un caso base, e tanto basta per risolvere l'esercizio, bastava trovare c e non dimostrare se appartiene o meno alla classe di complessità $O(n^3)$
perciò $EE c>=7/16,m>=2$ $f(n) <= g(n)$ ($f(n) in O(n^3)$)
non so mai quando applicare un metodo matematico banale o uno "coplesso" e sbagliato.
Provo gli altri, ma penso siano simili x risoluzione...grazie mille
Hai applicato un caso base, e tanto basta per risolvere l'esercizio, bastava trovare c e non dimostrare se appartiene o meno alla classe di complessità $O(n^3)$
perciò $EE c>=7/16,m>=2$ $f(n) <= g(n)$ ($f(n) in O(n^3)$)
non so mai quando applicare un metodo matematico banale o uno "coplesso" e sbagliato.
Provo gli altri, ma penso siano simili x risoluzione...grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo