Come dimostrare o confutare quanto segue: f(n) = O(g(n)) implica lg f(n) = O(lg g(n))
Come posso provare o confutare quanto segue:
implica
?
Non mi è mai piaciuto usare l'uguaglianza insieme alla notazione big-O. È usata negli articoli del wiki, ma usare l'uguaglianza in situazioni come questa è fuorviante. Quando si dice che una cosa è in un insieme determinato dall'altra, non si dovrebbe dire che l'una è uguale all'insieme determinato dall'altra.
Cambiando la notazione, ora abbiamo la domanda
Come posso provare o confutare quanto segue: se [math]f[/math] è [math]o(g)[/math] allora [math]f[/math] è [math]\mathcal O(g)[/math]? Prendiamo la conclusione big-O. Assumiamo che entrambe le funzioni siano valutate positivamente, come è sempre il caso quando si guarda alla crescita delle funzioni. L'affermazione [math]f[/math] è [math]\mathcal O(g)[/math] dice informalmente che [math]f[/math] non è molto più grande di [math]g[/math]. Più precisamente, dice che per grandi valori di [math]x[/math], [math]f(x)[/math] è limitata da qualche multiplo di [math]g(x)[/math], cioè, c'è qualche numero [math]M[/math] in modo che
[math]\qquad f(x)\leq M g(x)[/math]
per valori sufficientemente grandi di [math]x[/math].
Prendiamo ora l'ipotesi little-o. Perché [math]f[/math] sia [math]o(g)[/math], [math]f[/math] deve essere molto più piccolo di [math]g[/math] nel seguente preciso senso: il rapporto [math]f(x)/g(x)[/math] si avvicina a 0 man mano che [math]x[/math] si avvicina all'infinito:
[math]\qquad\displaystyle\lim_{x\to\infty}frac{f(x)}{g(x)}=0[/math]
Ora, è vero che se questo rapporto si avvicina a 0 allora [math]f[/math] è alla fine limitato da un multiplo di [math]g[/math]? Sì. Ecco una prova.
Se il rapporto si avvicina a 0, ciò significa che per qualsiasi [math]\epsilon[/math] positivo esiste un certo [math]N[/math] in modo che per grandi valori di [math]x[/math]
[math]\qquad\dfrac{f(x)}{g(x)}<\epsilon[/math]
Prendiamo [math]\epsilon=1[/math]. Allora per grandi [math]x[/math]
[math]\qquad \dfrac{f(x)}{g(x)}<1[/math]
Quindi per grandi [math]x[/math], abbiamo [math]f(x)
Questo significa che essere little-o di una funzione è una condizione più forte che essere big-o di una funzione.
Articoli simili
- Quanto da vicino la serie televisiva "Outlander" segue i libri? Quali sono alcune deviazioni degne di nota?
- Gesù era druso? Un test del DNA del sangue della Sindone (eseguito per un documentario 'The Jesus Strand') lo implica.
- Come contrastare uno Sciacallo che ti segue
- Come dimostrare che non stavo messaggiando durante la guida