Dimostrazione Ordine di grandezza Omega
Salve, ho un problema sulla dimostrazione di un esercizio, l'argomento sarebbe la complessità e gli ordini di grandezza
Questo è il testo:
1. Si mostri che, per stabilire se una funzione $g(n) in \Omega(f(n))$ , si può calcolare $\lim_{n \to \infty}(g(n)/f(n)) $ ed affermare che se il limite esiste ed è una costante $c>0$ oppure $\infty$, allora $g(n) in \Omega(f(n))$.
2. Come si può inoltre stabilire se $g(n) in \Theta(f(n))$?
1. Pensavo di utilizzare le proprietà di Omega e dimostrare per induzione o parallelamente riflessività e transitività (come si risolvono gli esercizi base di questo tipo), ma con la dimostrazione che coinvolge il limite nel caso generale proprio mi ha messo un po' in crisi.
2. proprietà base, penso sia facile.
Non è che potreste darmi uno spunto corretto, solo per partire.
Devo utilizzare la disuguaglianza di Omega o le proprietà dei limiti?
PS: (spero che sia la sezione giusta, se no chiedo scusa, è pur sempre una branca delle matematica)
Questo è il testo:
1. Si mostri che, per stabilire se una funzione $g(n) in \Omega(f(n))$ , si può calcolare $\lim_{n \to \infty}(g(n)/f(n)) $ ed affermare che se il limite esiste ed è una costante $c>0$ oppure $\infty$, allora $g(n) in \Omega(f(n))$.
2. Come si può inoltre stabilire se $g(n) in \Theta(f(n))$?
1. Pensavo di utilizzare le proprietà di Omega e dimostrare per induzione o parallelamente riflessività e transitività (come si risolvono gli esercizi base di questo tipo), ma con la dimostrazione che coinvolge il limite nel caso generale proprio mi ha messo un po' in crisi.
2. proprietà base, penso sia facile.
Non è che potreste darmi uno spunto corretto, solo per partire.
Devo utilizzare la disuguaglianza di Omega o le proprietà dei limiti?
PS: (spero che sia la sezione giusta, se no chiedo scusa, è pur sempre una branca delle matematica)
Risposte
[mod="Martino"]Non so cosa intendi con Omega, ma mi sembra comunque che il tuo problema riguardi l'analisi. Sposto.[/mod]
Uhm, non capisco molto bene cosa intendi con omega. Però mi è venuta in mente questa cosa che ho visto in teoria della computabilità e complessità e in analisi numerica.
<<
Siano $f(n)$ e $g(n)$ due funzioni parziali definite $\forall n>=n_0$; si dice che $f(n)=O(g(n))$ sse esiste $ c>0$ t.c. $f(n)\le cg(n)$.
>>
Con questa definizione, si creava inoltre una relazione d'ordine.
Poi, in seguito c'era un teorema (dimostrato nel corso di teoria della computabilità e complessità) che diceva:
<<
Siano $f,g$ due funzioni definite come sopra, allora:
1) $\lim_{n\to +\infty} \frac{f(n)}{g(n)} = l>0
allora si ha che $f=O(g)$ e $g=O(f)$.
2) $\lim_{n\to +\infty} \frac{f(n)}{g(n)}=0
allora si ha che $f=O(g)$ ma $g\ne O(f)$.
>>
Forse che sia la stessa cosa con $\Omega$ invece di $O$???
<<
Siano $f(n)$ e $g(n)$ due funzioni parziali definite $\forall n>=n_0$; si dice che $f(n)=O(g(n))$ sse esiste $ c>0$ t.c. $f(n)\le cg(n)$.
>>
Con questa definizione, si creava inoltre una relazione d'ordine.
Poi, in seguito c'era un teorema (dimostrato nel corso di teoria della computabilità e complessità) che diceva:
<<
Siano $f,g$ due funzioni definite come sopra, allora:
1) $\lim_{n\to +\infty} \frac{f(n)}{g(n)} = l>0
allora si ha che $f=O(g)$ e $g=O(f)$.
2) $\lim_{n\to +\infty} \frac{f(n)}{g(n)}=0
allora si ha che $f=O(g)$ ma $g\ne O(f)$.
>>
Forse che sia la stessa cosa con $\Omega$ invece di $O$???
Grazie delle risposte.
Scusate, pensavo conosceste l'argomento.
L'argomento sarebbe la complessità, si utilizza per il calcolo della complessità degli algoritmi in Informatica.
Omega sarebbe un limite asintotico inferiore della complessità di un algoritmo.
Essendo una dimostrazione di un teorema con i limiti pensavo si potesse conllegare con la matematica. Se volete spostate pur il post in Informatica.
Cmq la risposta di Zero87 è il teorema ma per O-grande, se non sbaglio.
Io devo dimostrare esattamente quello, che è il teorema, ma per Omega.
Scusate, pensavo conosceste l'argomento.
L'argomento sarebbe la complessità, si utilizza per il calcolo della complessità degli algoritmi in Informatica.
Omega sarebbe un limite asintotico inferiore della complessità di un algoritmo.
Essendo una dimostrazione di un teorema con i limiti pensavo si potesse conllegare con la matematica. Se volete spostate pur il post in Informatica.
Cmq la risposta di Zero87 è il teorema ma per O-grande, se non sbaglio.
Io devo dimostrare esattamente quello, che è il teorema, ma per Omega.
Allora è proprio quello che ho detto, ma in questo caso credo che andasse nella sezione "informatica".
Alla fine, O-grande e omega sono la stessa cosa.
Alla fine, O-grande e omega sono la stessa cosa.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo