Notazione asintotica
Quale è il significato della costante "c" che compare nella definizione di "O grande".
Risposte
Ciao,
pensaci un attimo,
che significato ha la classe di complessità $O()$? (terminologia di algoritmica se conosci)
cosa rappresenta quell'insieme?
pensaci un attimo,
che significato ha la classe di complessità $O()$? (terminologia di algoritmica se conosci)
cosa rappresenta quell'insieme?
Senza la costante "\(\displaystyle c \)" direi che \(\displaystyle f(n) \) è in \(\displaystyle O(g(n)) \) se \(\displaystyle g(n) \) limita superiormente \(\displaystyle f(n) \) da un certo valore di n in poi.
Però nella definizione compare \(\displaystyle f(n) \leq cg(n) \) e non solamente \(\displaystyle f(n) \leq g(n) \). Che ruolo ha la costante "\(\displaystyle c \)"?
Però nella definizione compare \(\displaystyle f(n) \leq cg(n) \) e non solamente \(\displaystyle f(n) \leq g(n) \). Che ruolo ha la costante "\(\displaystyle c \)"?
la questione la si può vedere sotto diverse ottiche.
Prima enunciamo la tua definizione:
\[\exists m \ge 0\ :\ g(n) \leq f(n),\ \forall n \geq m\]
con questa, proviamo a dimostrare che $10n^3 + 2n^2 +7 in O(n^3)$ per induzione.
Dobbiamo provare che:
\[\exists m \ge 0\ :\ 10n^3 + 2n^2 + 7 \leq n^3,\ \forall n \geq m\]
$10n^3 + 2n^2 + 7 <= 10n3 + 2n^3 + n^3 = 13n^3\ \forall n>=2$
ora secondo la nostra ipotesi: $13n^3 <= n^3$ (*)
ma che non è vero per nessun valore di $n$.
_____
Ora definiamoci cosa è la notazione $O$.
Sia $f(n)$ una funzione di costo; indichiamo con $O(f(n))$ l’insieme delle funzioni $g(n)$ tali per cui: (**)
\[\exists c > 0,\ m \ge 0\ :\ g(n) \leq cf(n),\ \forall n \geq m\]
In altre parole:
- asintoticamente la funzione giace sotto $c*f(n)$
- $g(n)$ cresce al più come $f(n)$
- $f(n)$ e un limite asintotico superiore per $g(n)$.
Torniamo al nostro esempio (*)
arriavati al punto $13n^3 <= n^3$ si potrebbe dire che per $13n^3 <= 13*n^3$ è vera, cioè moltiplicando $f(n)$ per uno scalare può essere vera, se non lo fosse esisterebbero infinite classi $O()$ per ogni valore moliplicativo di $f(n)$ , cioè: $O(1n^3), ... O(13n^3), ...$, cosa insensata. Così si generalizza il tutto con una costante nascosta $c$ così di definire $O(cn^3)$, nel nostro caso l'esempio è vero per $c>=13$ e $m=2$
La visione "algoritmica" si può esprimere come, all'interesse della crescita delle funzioni in base al loro comportamento asintotico, ovvero al crescere del valore in input (dimensione del problema).
Una visione grafica secondo me ti chiarisce ancora di più le idee:
Più chiaro ora?
Prima enunciamo la tua definizione:
\[\exists m \ge 0\ :\ g(n) \leq f(n),\ \forall n \geq m\]
con questa, proviamo a dimostrare che $10n^3 + 2n^2 +7 in O(n^3)$ per induzione.
Dobbiamo provare che:
\[\exists m \ge 0\ :\ 10n^3 + 2n^2 + 7 \leq n^3,\ \forall n \geq m\]
$10n^3 + 2n^2 + 7 <= 10n3 + 2n^3 + n^3 = 13n^3\ \forall n>=2$
ora secondo la nostra ipotesi: $13n^3 <= n^3$ (*)
ma che non è vero per nessun valore di $n$.
_____
Ora definiamoci cosa è la notazione $O$.
Sia $f(n)$ una funzione di costo; indichiamo con $O(f(n))$ l’insieme delle funzioni $g(n)$ tali per cui: (**)
\[\exists c > 0,\ m \ge 0\ :\ g(n) \leq cf(n),\ \forall n \geq m\]
In altre parole:
- asintoticamente la funzione giace sotto $c*f(n)$
- $g(n)$ cresce al più come $f(n)$
- $f(n)$ e un limite asintotico superiore per $g(n)$.
Torniamo al nostro esempio (*)
arriavati al punto $13n^3 <= n^3$ si potrebbe dire che per $13n^3 <= 13*n^3$ è vera, cioè moltiplicando $f(n)$ per uno scalare può essere vera, se non lo fosse esisterebbero infinite classi $O()$ per ogni valore moliplicativo di $f(n)$ , cioè: $O(1n^3), ... O(13n^3), ...$, cosa insensata. Così si generalizza il tutto con una costante nascosta $c$ così di definire $O(cn^3)$, nel nostro caso l'esempio è vero per $c>=13$ e $m=2$
La visione "algoritmica" si può esprimere come, all'interesse della crescita delle funzioni in base al loro comportamento asintotico, ovvero al crescere del valore in input (dimensione del problema).
Una visione grafica secondo me ti chiarisce ancora di più le idee:
Più chiaro ora?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo