Big Oh Notation - definizione formale

Question

Sto leggendo un libro di testo per la mia classe Java III. Stiamo leggendo su Big-Oh e sono un po 'confuso dalla sua definizione formale.

Definizione formale: "Una funzione f (n) è di ordine al massimo g (n) - cioè, f (n) = O (g (n)) - se un numero reale positivo c e un numero intero positivo N esiste tale che f (n) < = cg (n) per tutti n> = N. Cioè, cg (n) è un limite superiore su f (n) quando n è sufficientemente grande. "

Ok, questo ha senso. Ma aspettate, continuate a leggere ... il libro mi ha dato questo esempio:

"Nel segmento 9,14, abbiamo detto che un algoritmo che utilizza 5n + 3 operazioni è O (n) Ora può mostrare. che 5n + 3 = O (n) utilizzando la definizione formale di Big Oh.

Quando n> = 3, 5n + 3 < = 5n + n = 6n. Quindi, se lasciamo che f (n) = 5n + 3, g (n) = n, c = 6, N = 3, abbiamo mostrato che f (n) < = 6 g (n) per n> = 3 o 5n + 3 = O (n). Cioè, se un algori thm richiede tempo direttamente proporzionale a 5n + 3, è O (n). "

Ok, questo tipo di ha senso per me. Dicono che se n = 3 o superiore, 5n + 3 richiede meno tempo rispetto a se n era minore di 3 - quindi 5n + n = 6n - giusto? Ha senso, poiché se n era 2, 5n + 3 = 13 mentre 6n = 12 ma quando n è 3 o maggiore 5n + 3 sarà sempre minore o uguale a 6n.

Ecco dove mi confondo. che mi danno un altro esempio:

Esempio 2: "Mostriamo che 4n^2 + 50N - 10 = O (n^2) E 'facile vedere che:. 4n^2 + 50N - 10 < = 4n^2 + 50n per ogni n da 50n < = 50n^2 per n

= 50, 4n^2 + 50N -. 10 < = 4n^2 + 50n^2 = 54n^2 per n> = 50. Quindi, con c = 54 e N = 50, abbiamo mostrato che 4n^2 + 50n - 10 = O (n^2). "

Questa affermazione non ha senso: 50N < = 50n^2 per n> = 50.

Non è alcun n andando a fare il 50N meno di 50 N^2? Non solo maggiore o uguale a 50? Perché hanno persino detto che 50n < = 50n^2? Cosa c'entra questo con il problema?

Inoltre, 4n^2 + 50n - 10 < = 4n^2 + 50n^2 = 54n^2 per n> = 50 sta per essere vero indipendentemente da n.

E come mai i numeri di prelievo mostrano che f (n) = O (g (n))?

Answer 1

Ricorda che stai cercando "un limite superiore su f (n) quando n è sufficientemente grande." Quindi, se puoi dimostrare che f (n) è minore o uguale a qualche c g (n) per valori di n maggiore di N, questo significa c g (n) è un limite superiore per f (n) e la complessità di f (n) è quindi O (g (n)).

Gli esempi hanno lo scopo di mostrare che la data funzione f (n) non può mai crescere oltre c * g (n) per ogni n> N. Manipolando un primo limite superiore in modo che possa essere espressa più semplicemente (se 4n^2 + 50n è un limite superiore su f (n) quindi è 4n^2 + 50n^2, che è uguale a 54n^2, che diventa il tuo 54 * g (n) dove c = 54 eg (n) = n^2), gli autori possono mostrare che f (n) è limitato da c * g (n), che ha complessità O (g (n)) e quindi anche f (n).

Answer 2

50n <= 50n^2 for n >= 50 

perché se n è 50, allora 50n è uguale a n^2, perché 50 * 50 è uguale a 50^2.

Sostituendo n^2 per 50n otteniamo

n^2 <= 50n^2 for n >= 50 

che è ovvio.

Answer 3

Tutto ciò che riguarda il prelievo dei numeri è proprio questo: per semplificare. Dato che puoi scegliere qualsiasi numero che ti piace per N e c, l'autore sceglie solo qualcosa, dove è più facile da vedere. Ed è quello che puoi fare anche tu (quando scrivi un esame, ecc.).

Così, mentre sarebbe spesso possibile utilizzare una N più piccola, il ragionamento diventerebbe un po 'più difficile (spesso richiede alcune conoscenze precedenti sull'analisi - abbiamo imparato tutti anni prima, che x non cresce più velocemente come x^2 ... Ma vuoi scrivere la prova dell'analisi?)

Keep it simple, is the message :-) È un po 'strano abituarsi a questo all'inizio.

Answer 4

Probabilmente la ragione per cui hanno detto 50n < = 50n^2 per n> = 50 è che se n è minore di 1, che n^2 < n. Naturalmente, se n è un numero intero positivo, allora sì 50n < = 50n^2. In questo caso, sembra che n sia considerato un numero intero positivo, sebbene la definizione formale che danno non lo dichiari esplicitamente.

Vedo perché dire 50n < = 50n^2 per n> = 50 può sembrare un po 'sciocco. Ma è ancora vero. Il libro non dice 50n < = 50n^2 tiene SOLO per n> = 50; quello sarebbe falso.

Come un'analogia, se dico "tutti i miei fratelli parlano inglese", ciò sarebbe vero, anche se ci sono molte persone che parlano inglese che non sono i miei fratelli.

Per quanto riguarda la prova, potremmo suddividerla in dichiarazioni diverse.

(1): 4n^2 + 50n - 10 <= 4n^2 + 50n (for all n) 
(2): 4n^2 + 50n <= 4n^2 + 50n^2 (for all n>=50) 
(3): 4n^2 + 50n^2 = 54 n^2 (for all n, including all n>=50) 
(4): Therefore, 4n^2 + 50n - 10 <= 54n^2 for all n>=50 
(5): Therefore, for f(n)=4n^2 + 50n - 10, g(n)=n^2, N=50, and c=54, 
      the statement f(n) <= c g(n) for all n >= N is true 
(6): Therefore, by definition 4n^2 + 50n - 10=O(n^2). 

Dovrebbe essere chiaro che ognuna di queste affermazioni è vera, sia da solo (1,2,3), o come risultato delle affermazioni precedenti.

Answer 5

definizione formale:

• f (n) = O (g (n)) significa che esiste c> 0 e n tale che per ogni n> = n f (n) < = c * g (n)
• f (n) = O (g (n)) mezzi per ogni c> 0 esistono n tale che per ogni n> = n f (n) < = c * g (n)

Come potete notare ci sono leggermente diversi :)