Supponiamo di avere una funzione, f (n) = n + 10. Diciamo che f (n) ∈O (n), che significa O (n) rappresenta il limite superiore della funzione.
È anche vero che f (n) ∈O (n 2 ) o f (n) ∈O (n 3 ) e così via.
Quindi, come possiamo dire che O (n) è il limite superiore quando O (n 2 ) è relativamente più grande e O (n 3 ) è molto più grande bound?
Per favore perdonami se ho capito male il concetto.
È molto facile eliminare la tua confusione perché proviene da una singola parola:
O(n) represents the upper bound of the function.
Questo è sbagliato. L'affermazione corretta è:
O(n) represents an upper bound of the function.
La notazione Big-O non significa che la funzione chiamata nella notazione sia upper upper bound , solo che è un limite superiore .
Quando riscriviamo la tua domanda come:
How can we say that O(n) is an upper bound when O(n2) is comparatively bigger bound and O(n3) is much bigger bound?
la domanda diventa chiara. Non ci sono umani più alti di 100 metri; questo è un limite superiore all'altezza umana. 200 metri e 10000000 metri sono anche limiti superiori; l'esistenza di limiti superiori più grandi non significa che un limite superiore più piccolo non sia anche un limite superiore. Nessuno di questi è il minimo superiore .
Ora, nel tuo esempio O (n) capita di essere il limite superiore minimo sulla funzione che tu dai. Ci sono anche limiti superiori più grandi, come si nota, e quindi quelli non sono i limiti minimi .
f (n) = O (g (n)) afferma che se esiste qualche costante c > 0 e n 0 > 0, quindi f (n) < = cg (n ) per tutti n > = n 0 . Qui n 0 è un limite sopra il quale consideriamo n cioè cerchiamo di trovare la notazione asintotica che di per sé significa che vogliamo trovare la complessità temporale di grandi valori di n. Quindi, consideriamo n 0 come limite inferiore di n e sopra n 0 questa affermazione vale.
Quindi hai frainteso O (g (n)) con O (n), se abbiamo due funzioni con complessità temporale f (n 1 ) = O (n 1 ) e f (n 2 ) = O (n 2 2 ) quindi esiste una proprietà di Big-O che è O (funzione risultante) = max (O (n 1 ), O (n 2 2 )). Quindi, con questo in questo caso O (n 2 ) è il limite superiore rispetto a O (n).
Leggi altre domande sui tag big-o