Significato di O grande
Ho difficoltà ad apprendere il concetto di O-grande applicato al concerto di complessità di un algoritmo, dove si afferma che :
date due funzioni$ f,g : N \to N$
si dice che $g(n)$ è di ordine $O(f(n))$ che equivale a $g(n)$ è $O(f(n)$,
se esistono un intero $n_0$ ed una costante $c > 0$ , tali che per ogni $n >= n_0$, $g(n) ≤ cf(n)$.
La definizione mi è chiara ma leggevo altrove che si potrebbe anche scrivere:
$\lim_{x \to x_0} g(x)/f(x)=l in RR$
ma in questo caso si introduce un intorno di $x_0$ mentre nella prima definizione no, ma allora quale prendere in considerazione?
Per fare un esempio per capire meglio: $(n+1)^2$ è $O(n^2)$
Potrei interpretare il significato dell'espressione come il primo termine che è più grande di quello contenuto nella $O grande$ ?
date due funzioni$ f,g : N \to N$
si dice che $g(n)$ è di ordine $O(f(n))$ che equivale a $g(n)$ è $O(f(n)$,
se esistono un intero $n_0$ ed una costante $c > 0$ , tali che per ogni $n >= n_0$, $g(n) ≤ cf(n)$.
La definizione mi è chiara ma leggevo altrove che si potrebbe anche scrivere:
$\lim_{x \to x_0} g(x)/f(x)=l in RR$
ma in questo caso si introduce un intorno di $x_0$ mentre nella prima definizione no, ma allora quale prendere in considerazione?
Per fare un esempio per capire meglio: $(n+1)^2$ è $O(n^2)$
Potrei interpretare il significato dell'espressione come il primo termine che è più grande di quello contenuto nella $O grande$ ?
Risposte
La cosa con i limiti che hai scritto non è la definizione usuale di O grande. La definizione usuale è quella che hai dato sopra se \(n\to \infty\). Si può poi dire che \(f(x)=O(g(x))\) per \(x\to x_0\) se esiste un intorno \(I\) di \(x_0\) e una costante \(C>0\) tali che
\[
|f(x)|\le C g(x), \qquad \forall x\in I.\]
Quanto all'esempio, devi specificare che \(n\to \infty\). O grande da solo non significa niente, bisogna sempre specificare a cosa tende la variabile. Comunque, è vero che
\[
(n+1)^2=O(n^2), \qquad n\to\infty.\]
Infatti,
\[
(n+1)^2=n^2+2n+1\le 3n^2, \]
se \(n\ge 2\), perché in tal caso \(2n\le n^2\) e \(1\le n^2\).
\[
|f(x)|\le C g(x), \qquad \forall x\in I.\]
Quanto all'esempio, devi specificare che \(n\to \infty\). O grande da solo non significa niente, bisogna sempre specificare a cosa tende la variabile. Comunque, è vero che
\[
(n+1)^2=O(n^2), \qquad n\to\infty.\]
Infatti,
\[
(n+1)^2=n^2+2n+1\le 3n^2, \]
se \(n\ge 2\), perché in tal caso \(2n\le n^2\) e \(1\le n^2\).
Mi spiego in modo poco matematico e ne sono pienamente consapevole ma, supposto che $n \to \infty$ quando viene chiamato in causa $O\ text{grande}$, ho sempre due termini:
uno a sinistra della $O\ text{grande}$ ed uno dentro la mia $O\ text{grande}$ , nell'esempio rispettivamente $(n+1)^2$ e $n^2$ vorrei capire bene come si interpretano, inizialmente pensavo a quanto velocemente tendono ad infinito ma forse sbaglio...
A sinistra vedo un termine che cresce più velocemente rispetto a quello di destra.
Noto anche che esiste una costante $c$ ed un valore di $n$ per cui il termine di destra è maggiore di quello di sinistra, applicando la definizione. All'atto pratico però non riesco a cogliere il significato di tutto ciò ...
Cioè se dico che $f(x)$ è $O(g(x))$ significa che esiste sempre un valore di $c$ che mi rende vero la relazione $cg(x)>=f(x)$ ? Non riesco a capire il senso di tutto ciò e quale possa essere la necessità di introdurre $O$ grande.
uno a sinistra della $O\ text{grande}$ ed uno dentro la mia $O\ text{grande}$ , nell'esempio rispettivamente $(n+1)^2$ e $n^2$ vorrei capire bene come si interpretano, inizialmente pensavo a quanto velocemente tendono ad infinito ma forse sbaglio...
A sinistra vedo un termine che cresce più velocemente rispetto a quello di destra.
Noto anche che esiste una costante $c$ ed un valore di $n$ per cui il termine di destra è maggiore di quello di sinistra, applicando la definizione. All'atto pratico però non riesco a cogliere il significato di tutto ciò ...
Cioè se dico che $f(x)$ è $O(g(x))$ significa che esiste sempre un valore di $c$ che mi rende vero la relazione $cg(x)>=f(x)$ ? Non riesco a capire il senso di tutto ciò e quale possa essere la necessità di introdurre $O$ grande.
La definizione è quella e c'è poco da discutere. L'idea intuitiva che hai è grosso modo giusta: per dirla un pochino meglio, nella relazione \(f(x)=O(g(x))\), il termine \(f\) ha ordine di grandezza al più uguale a quello di \(g\).
La necessità la capirai con l'uso (come disse qualcuno "la matematica non si capisce, alla matematica ci si abitua").
La necessità la capirai con l'uso (come disse qualcuno "la matematica non si capisce, alla matematica ci si abitua").
Grazie 1000!
Capito che $g(n)$ è $O(f(n))$ cioè esiste un intero $n>=n_0$ ed una costante $c>0$ tale che $cf(n)>=g(n)$
mi trovo in difficoltà ad interpretare la regola dei fattori costanti che dice:
per ogni costante positiva $k$, $O(f(n))\ =\ O(k\ f(n))$
Poi viene citato questo esempio:
$2n^2 in O(n^2)$ dove $n_0=0$ , $c=2$
$2^(n+10) in O(2^n)$ dove $n_0=0$ , $c=2^10$
$n^2 in O(1/1000n^2)$ dove $n_0=0$ , $c=1000$
Non mi è chiaro.
La prima cosa che guardo è il simbolo di appartenenza $in$ quindi mi riconduco alla funzione $g(n)$ e $f(n)$ e
associo $2n^2$ a $g(n)$ mentre $n^2$ a $f(n)$, sbaglio?
Mi sfugge di mano la relazione $O(f(n))\ =\ O(k\ f(n))$ perchè vedo solo un $O(n^2)$
di nuovo grazie
mi trovo in difficoltà ad interpretare la regola dei fattori costanti che dice:
per ogni costante positiva $k$, $O(f(n))\ =\ O(k\ f(n))$
Poi viene citato questo esempio:
$2n^2 in O(n^2)$ dove $n_0=0$ , $c=2$
$2^(n+10) in O(2^n)$ dove $n_0=0$ , $c=2^10$
$n^2 in O(1/1000n^2)$ dove $n_0=0$ , $c=1000$
Non mi è chiaro.
La prima cosa che guardo è il simbolo di appartenenza $in$ quindi mi riconduco alla funzione $g(n)$ e $f(n)$ e
associo $2n^2$ a $g(n)$ mentre $n^2$ a $f(n)$, sbaglio?
Mi sfugge di mano la relazione $O(f(n))\ =\ O(k\ f(n))$ perchè vedo solo un $O(n^2)$
di nuovo grazie
C'è un topic in alto, di Gugo, proprio su queste cose. Hai provato a dargli un'occhiata? Si chiama "tutorial: i simboli di Landau"
no non l'ho visto ora ci guardo
"dissonance":
C'è un topic in alto, di Gugo, proprio su queste cose. Hai provato a dargli un'occhiata? Si chiama "tutorial: i simboli di Landau"
Credo che in analogia ci si possa riferire alle regola che @gugo definisce come iii, tralascio intenzionalmente $x_0$ ed inverto $f(n)$ e $g(n)$ on accordo con ciò che ho scritto prima:
Se $g(n)=O(f(n))$ e $α∈R$ , allora $αg(n)=O(f(n))$
non mi pare proprio la stessa cosa rispetto a:
$\alpha , O(f(n)) = O(\alpha f(n))$
un aiutino?
$ \alpha , O(f(n)) = O(\alpha f(n)) $ che significa?
La virgola mi pare “inquietante”… Probabilmente intendi $ AA alpha != 0,\ O(f(n)) = O(\alpha f(n)) $?
Ad ogni buon conto, dando per buona la mia interpretazione, come ogni relazione contenente i simboli di Landau la $ O(f(n)) = O(\alpha f(n)) $ va interpretata. L’interpretazione canonica è la seguente: comunque scegli $g(n)$ nella classe $O(f(n))$, la funzione $ g(n)$ è nella classe $O(alpha f(n))$ e viceversa.
Stante la definizione del simbolo, questa cosa mi pare di un’evidenza poco meno luminosa del sole… Insomma, c’è davvero poco da interpretare.
La virgola mi pare “inquietante”… Probabilmente intendi $ AA alpha != 0,\ O(f(n)) = O(\alpha f(n)) $?
Ad ogni buon conto, dando per buona la mia interpretazione, come ogni relazione contenente i simboli di Landau la $ O(f(n)) = O(\alpha f(n)) $ va interpretata. L’interpretazione canonica è la seguente: comunque scegli $g(n)$ nella classe $O(f(n))$, la funzione $ g(n)$ è nella classe $O(alpha f(n))$ e viceversa.
Stante la definizione del simbolo, questa cosa mi pare di un’evidenza poco meno luminosa del sole… Insomma, c’è davvero poco da interpretare.
Ma si, in fondo è lo stesso, ora sono da cellulare e mi è difficile scrivere, ma devi semplicemente dimostrare che \[f(n) =O(\alpha g(n)) \] se e solo se \[f(n) = O(g(n)), \] e non ti scordare che alpha deve essere diverso da zero.
(scrivevo contemporaneamente a Gugo)
(scrivevo contemporaneamente a Gugo)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo