significato di O grande

[zio_mangrovia]

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$ ?

[dissonance]

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\).

[zio_mangrovia]

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.

[dissonance]

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").

[zio_mangrovia]

Grazie 1000!

[zio_mangrovia]

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

[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"

[zio_mangrovia]

no non l'ho visto ora ci guardo

[zio_mangrovia]

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))$

[zio_mangrovia]

un aiutino?