[Algoritmi] - Verificare ordine di grandezza di due funzioni
Salve a tutti,
ho dei problemi a risolvere un esercizio, e mi chiedevo se qualcuno potesse darmi una mano.
Siano date due funzioni, $f(n)$ e $g(n)$. Dimostrare che $ f(n) = O( g(n) )$ e calcolare la costante $c$ ed il valore di $n_0$ per cui vale questa relazione.
Nel mio caso $ f(n) = 3^n + 4^n + n^10 $ e $ g(n) = 4^n $.
La mia tesi è che $ f(n) <= c * g(n) $ per una data costante $ c > 0 $ e $ n > n0 $.
Ho provato a maggiorare $f(n)$:
$ 3^n + 4^n + n^10 <= 4^n + 4^n + n^10 $
Ora dovrei maggiorare $n^10$. Facendo un grafico al pc ho trovato che $4^n > n^10$ per $n>=23$ quindi il problema è di per se risolto.
Ma è possibile calcolare il valore preciso di $n$ per cui $ 4^n > n^10 $ senza utilizzare il metodo grafico?
ho dei problemi a risolvere un esercizio, e mi chiedevo se qualcuno potesse darmi una mano.
Siano date due funzioni, $f(n)$ e $g(n)$. Dimostrare che $ f(n) = O( g(n) )$ e calcolare la costante $c$ ed il valore di $n_0$ per cui vale questa relazione.
Nel mio caso $ f(n) = 3^n + 4^n + n^10 $ e $ g(n) = 4^n $.
La mia tesi è che $ f(n) <= c * g(n) $ per una data costante $ c > 0 $ e $ n > n0 $.
Ho provato a maggiorare $f(n)$:
$ 3^n + 4^n + n^10 <= 4^n + 4^n + n^10 $
Ora dovrei maggiorare $n^10$. Facendo un grafico al pc ho trovato che $4^n > n^10$ per $n>=23$ quindi il problema è di per se risolto.
Ma è possibile calcolare il valore preciso di $n$ per cui $ 4^n > n^10 $ senza utilizzare il metodo grafico?
Risposte
Devi calcolare
$\lim_{n \to \infty}f(n)/g(n)$
Se risulta che $f(n)$ è un infinitesimo di ordine superiore, allora $f(n) = O(g(n))$.
$\lim_{n \to \infty}f(n)/g(n)$
Se risulta che $f(n)$ è un infinitesimo di ordine superiore, allora $f(n) = O(g(n))$.
"xsl":
Devi calcolare
$\lim_{n \to \infty}f(n)/g(n)$
Se risulta che $f(n)$ è un infinitesimo di ordine superiore, allora $f(n) = O(g(n))$.
non è proprio così, c'è una sottigliezza in mezzo:
se il limite è $0$ allora $f(n) in o(g(n))$
ma se $f(n) in o(g(n)) rArr f(n) in O(g(n))$
studiando il limite non è immediata l'appartenenza ad una limitazione superiore, ma ad una limitazione superiore stretta, piccolezze ma c'è differenza.
"ham_burst":
piccolezze
Il famoso ago nel pagliaio...
"xsl":
[quote="ham_burst"]piccolezze
Il famoso ago nel pagliaio...
[/quote]dicasi pignoleria
PS: se posso invece dare un altro cosiglio sia a te che all'autore del post: se una funzione appartiene ad una determinata classe di complessità, il simbolo corretto da usare è $in$ non $=$, come ho scritto sopra io.
Come si è scritto in altri post, tantissimi docenti e anche autori di libri utilizzano $=$, ma è formalmente sbagliato, tranne se inteso come ho scritto nel post linkato. una funzione appartine ad un insieme non è uguale, due mondi diversi...
Grazie a entrambi, purtroppo sono stato forse io poco preciso ad esporre il problema (modificherò il post iniziale).
L'esercizio consisteva nel calcolare la costante $c$, una volta appurato che $f(n) = O( g(n) )$
Avevo calcolato anche io il limite (e trovato che $f(n) = o( g(n) )$, però ho trovato difficoltà nel fare appunto quella maggiorazione.
Grazie a ham_burst per la pignoleria
Ho utilizzato con cognizione di causa la simbologia $ = $, al posto di $in$ (non dovrebbe essere $sube$?), dopo aver letto le motivazioni che danno Graham, Knuth, Patashnik nel volume "Matematica discreta", quando parlano della notazione asintotica.
Comunque grazie per averlo puntualizzato.
L'esercizio consisteva nel calcolare la costante $c$, una volta appurato che $f(n) = O( g(n) )$
Avevo calcolato anche io il limite (e trovato che $f(n) = o( g(n) )$, però ho trovato difficoltà nel fare appunto quella maggiorazione.
Grazie a ham_burst per la pignoleria
Ho utilizzato con cognizione di causa la simbologia $ = $, al posto di $in$ (non dovrebbe essere $sube$?), dopo aver letto le motivazioni che danno Graham, Knuth, Patashnik nel volume "Matematica discreta", quando parlano della notazione asintotica.
Comunque grazie per averlo puntualizzato.
"jubstuff":
(non dovrebbe essere $sube$?)
è no. Si utilizza il simbolo di sottoinsieme tra classi di complessità (insiemi di funzioni) es: $O(n) sub O(n^2)$
per il resto, se non ti risponderà nessuno, riprendo il messaggio sta sera, quando sarò più lucido
Visto che vogliamo fare i pignoli... 
Il significato attualmente in vigore nell'ambiente informatico dei simboli di Landau si deve a Knuth. Nonostante $O(f(n))$ rappresenti un insieme di funzioni, come si può leggere nell'articolo, usare l'uguaglianza al posto del simbolo di appartenenza o del simbolo di inclusione non è considerato un errore, purché si tenga bene a mente che l'uguaglianza in questo contesto vale, generalmente, solo in un senso. D'altronde si tratta solo di una notazione: basta accordarsi su che notazione utilizzare. E la notazione attualmente in vigore è proprio quella proposta da Knuth. Quindi utilizzare il simbolo di uguaglianza è corretto (tale notazione credo sia stata preservata perchè è quella utilizzata in analisi).
EDIT: tra l'altro, se si utilizzasse esclusivamente la tua notazione non si potrebbero scrivere cose del genere:
$T(n) = T(n-1) + O(1)$
ma bisognerebbe scrivere per forza
$T(n) = T(n-1) + c$ con $c in RR, c > 0$
e questo sarebbe secondo me un handicap: immaginate di avere molte altre di queste costanti...
La notazione non dev'essere una mera formalità, ma, dopo averla definita precisamente, uno strumento per farsi comprendere, non solamente per rendere le cose inutilmente più "pesanti".
Il significato attualmente in vigore nell'ambiente informatico dei simboli di Landau si deve a Knuth. Nonostante $O(f(n))$ rappresenti un insieme di funzioni, come si può leggere nell'articolo, usare l'uguaglianza al posto del simbolo di appartenenza o del simbolo di inclusione non è considerato un errore, purché si tenga bene a mente che l'uguaglianza in questo contesto vale, generalmente, solo in un senso. D'altronde si tratta solo di una notazione: basta accordarsi su che notazione utilizzare. E la notazione attualmente in vigore è proprio quella proposta da Knuth. Quindi utilizzare il simbolo di uguaglianza è corretto (tale notazione credo sia stata preservata perchè è quella utilizzata in analisi).
EDIT: tra l'altro, se si utilizzasse esclusivamente la tua notazione non si potrebbero scrivere cose del genere:
$T(n) = T(n-1) + O(1)$
ma bisognerebbe scrivere per forza
$T(n) = T(n-1) + c$ con $c in RR, c > 0$
e questo sarebbe secondo me un handicap: immaginate di avere molte altre di queste costanti...
La notazione non dev'essere una mera formalità, ma, dopo averla definita precisamente, uno strumento per farsi comprendere, non solamente per rendere le cose inutilmente più "pesanti".
@jubstuff: sono un po' in ritardo, ma ti rispondo comunque.
sei in induzione, vai di casi base...
Se no, alternativa al grafico, scrivi due righe di codice (di numero) e calcoli quando la maggioranza è vera. Ovviamente puoi calcolare un limitato numero di casi base, ma basta che trovi almeno un numero vero, e puoi verificare a mano altri valori (e il passo induttivo).
Ma oltre a questo (sottoproblema) attento che devi valutare anche una costante che renda vera anche la limitazione asintotica.
@Deckard:
ti devo ringraziare, non sapevo proprio che Knuth in persona introdusse questo "errore". Che errore non è. Si scopre sempre qualcosa di nuovo
Come dici bene basta accordarsi, ma tutti, a parere mio, all'inizio faranno un errore. Poi ci si fa il callo...
Poi il resto, è abuso di notazione, ma che semplifica la vita. Come è scrito pure nel Cormen che non avevo letto finora quella parte, questa notazione è segnata come "abuso" ma è un accordo tra le interpretazioni e l'utilizzo da parte dei matematici.
"jubstuff":
Ma è possibile calcolare il valore preciso di $n$ per cui $ 4^n > n^10 $ senza utilizzare il metodo grafico?
sei in induzione, vai di casi base...
Se no, alternativa al grafico, scrivi due righe di codice (di numero) e calcoli quando la maggioranza è vera. Ovviamente puoi calcolare un limitato numero di casi base, ma basta che trovi almeno un numero vero, e puoi verificare a mano altri valori (e il passo induttivo).
Ma oltre a questo (sottoproblema) attento che devi valutare anche una costante che renda vera anche la limitazione asintotica.
@Deckard:
ti devo ringraziare, non sapevo proprio che Knuth in persona introdusse questo "errore". Che errore non è. Si scopre sempre qualcosa di nuovo
Come dici bene basta accordarsi, ma tutti, a parere mio, all'inizio faranno un errore. Poi ci si fa il callo...
Poi il resto, è abuso di notazione, ma che semplifica la vita. Come è scrito pure nel Cormen che non avevo letto finora quella parte, questa notazione è segnata come "abuso" ma è un accordo tra le interpretazioni e l'utilizzo da parte dei matematici.
"xsl":
Devi calcolare
$\lim_{n \to \infty}f(n)/g(n)$
Se risulta che $f(n)$ è un infinitesimo di ordine superiore, allora $f(n) = O(g(n))$.
Quindi bisogna calcolare
$\lim_{n \to \infty}(3^n + 4^n + n^10)/4^n$
giusto?
Lo stesso discorso vale per esercizi del genere?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo