Theta grande, O grande
Ho un problema a capire una questione legata a informatica teorica, più precisamente è un dubbio legato al calcolo delle complessità spaziali e temporali di un programma.
In teoria $f(n) = O(g(n))$ quando esistono 2 costanti $c > 0 e x>=0$ tale che:
$f(n)<=c*g(n)$ per ogni $n>=x$
Quindi, come mai è possibile scrivere che una complessità di un valore costante k è O(1) ?
quando teoricamente pur considerando k=1, potrebbe esistere un c<1 sempre minore e mai maggiore di 1?ad esempio $c=\frac{1}{2}$,
-per caso, è possibile usare solo valori interi di c?perchè se non fosse così, mi pare si possa scrivere theta-grande(1), come mai invece si parla di O grande?
In teoria $f(n) = O(g(n))$ quando esistono 2 costanti $c > 0 e x>=0$ tale che:
$f(n)<=c*g(n)$ per ogni $n>=x$
Quindi, come mai è possibile scrivere che una complessità di un valore costante k è O(1) ?
quando teoricamente pur considerando k=1, potrebbe esistere un c<1 sempre minore e mai maggiore di 1?ad esempio $c=\frac{1}{2}$,
-per caso, è possibile usare solo valori interi di c?perchè se non fosse così, mi pare si possa scrivere theta-grande(1), come mai invece si parla di O grande?
Risposte
Allora vedo se posso esserti utile...
La notazione \( O \) viene utilizzata per indicare un limite superiore ad una funzione, a meno di una costante moltiplicativa. In complessità computazionale questo torna utile per stabilire un "upper bound" alla complessità di un problema. Spesso non si è interessati a trovare, o non si riesce a trovare, un "lower bound" quindi le notazioni \( \Omega \) e \( \Theta \) sono meno utilizzate.
Nel tuo caso effettivamente non sbagli dicendo che una costante è \( \Theta(1) \). Ricorda che se una funzione \( f(n) \in \Theta(g(n)) \) allora la stessa \( f(n) \in O(g(n)) \), non vale il viceversa.
Inoltre si dovrebbe scrivere \( O(n^0) \) al posto di \( O(1) \) per indicare che è dell'ordine di una costante (una costante è un polinomio di grado zero). Comunque, per comodità e chiarezza, si utilizza la seconda.
Per avere un'altra prova del fatto che una costante è \( O(1) \), guarda la definizione in un altro modo. Dire che \( f(n) \in O(g(n)) \) significa che:
\( \lim_{n \to +\infty} \frac{f(n)}{g(n)} < \infty \)
Nel caso specifico il limite diventa:
\( \lim_{n \to +\infty} \frac{n^0}{n^0} = 1 \)
e di conseguenza una costante è \( O(n^0) \), che indichiamo con \( O(1) \)...
La notazione \( O \) viene utilizzata per indicare un limite superiore ad una funzione, a meno di una costante moltiplicativa. In complessità computazionale questo torna utile per stabilire un "upper bound" alla complessità di un problema. Spesso non si è interessati a trovare, o non si riesce a trovare, un "lower bound" quindi le notazioni \( \Omega \) e \( \Theta \) sono meno utilizzate.
Nel tuo caso effettivamente non sbagli dicendo che una costante è \( \Theta(1) \). Ricorda che se una funzione \( f(n) \in \Theta(g(n)) \) allora la stessa \( f(n) \in O(g(n)) \), non vale il viceversa.
Inoltre si dovrebbe scrivere \( O(n^0) \) al posto di \( O(1) \) per indicare che è dell'ordine di una costante (una costante è un polinomio di grado zero). Comunque, per comodità e chiarezza, si utilizza la seconda.
Per avere un'altra prova del fatto che una costante è \( O(1) \), guarda la definizione in un altro modo. Dire che \( f(n) \in O(g(n)) \) significa che:
\( \lim_{n \to +\infty} \frac{f(n)}{g(n)} < \infty \)
Nel caso specifico il limite diventa:
\( \lim_{n \to +\infty} \frac{n^0}{n^0} = 1 \)
e di conseguenza una costante è \( O(n^0) \), che indichiamo con \( O(1) \)...
Sinceramente non vedo perché \(1\) vada pensata come \(n^0\): la funzione costante \(1\) è ben definita, continua e persino analitica. Inoltre ha la rimarchevole caratteristica di essere l'identità nell'algebra delle funzioni con la moltiplicazione definita punto per punto.
Non voglio mancare di rispetto alla funzione costane \( 1 \) ma in questo caso è "più corretto" utilizzare \( n^0 \) perché specifica quale sia la variabile che tende all'infinito nel limite. Inoltre penso che aiuti nel capire il concetto.
Aggiungo solo un piccolo commento. Sembra che tu non abbia del tutto compreso l'ordine con cui le varie costanti vanno scelte e la differenza tra "esiste" e "per ogni". Date le tue due funzioni \(f(n)\) e \(g(n)\), tu devi trovare due costanti per cui valga la relazione. Se non è possibile trovare queste costanti allora non è vero che \(f(n) \in O(n)\). Nel tuo caso hai \(f(n) = k\) e \(g(n) = 1\). Puoi quindi prendere per esempio \(c = k\) e \(x = 0\) ottenendo la relazione (vera per ogni \(n \geq 0\)) \( k \leq k \times 1. \) In effetti potevi prendere qualsiasi \( c \geq k \) e qualsiasi \(x\).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo