Notazione O-grande di un'espressione

Question

Se ho un algoritmo che prende 4n ^ 2 + 7n mosse da compiere, qual è il suo O? O (4n ^ 2)? O (n ^ 2)?

So che 7n è tagliato fuori, ma non so se devo mantenere il n ^ 2 coefficiente oppure no.

Grazie

Answer 1

Si dovrebbe lasciare cadere coefficienti perché la questione è veramente chiedere "dell'ordine di", che cerca di caratterizzare come lineare, esponenziale, logaritmica, ecc ... Cioè, quando n è molto grande, il coefficiente è di poca importanza.

Questo spiega anche il motivo per cui si cadere il + 7n, perché quando n è molto grande, quel termine ha relativamente poca importanza per la risposta finale. Se si ha familiarità con il calcolo, si potrebbe dire lim n-> inf (4 * n ^ 2 + 7n) ~ = lim n-> inf (4 * n ^ 2) ~ = lim n-> inf (n ^ 2)

Si può anche pensare a questo in un certo senso grafica ... cioè, se si rappresenta graficamente la funzione 4n ^ 2 + 7n per i valori più grandi di n, un matematico potrebbe dire "sembra che n ^ 2". Certo, avrebbe dovuto essere un matematico piuttosto liberale, in quanto questa non è una dichiarazione rigorosa, ma questo è fondamentalmente ciò che O (...) sta cercando di trasmettere.

Answer 2

I coefficienti non sono rilevanti nella notazione O-grande, quindi è solo O (n ² ). Come Wikipedia spiega :

  

[...] i coefficienti diventano irrilevanti se confrontiamo qualsiasi altro ordine di espressione, come espressione contenente un termine n ³ o n ² .

Answer 3

tutti la lettura o la scrittura sulla complessità degli algoritmi dovrebbe sapere esattamente ciò che il Landau Simboli e < a href = "http://mathworld.wolfram.com/AsymptoticNotation.html" rel = "nofollow noreferrer"> notazioni asintotiche sono, altrimenti non capire veramente cosa sta succedendo, o semplicemente avere un approssimativo (e spesso fuorvianti) idea.

Per semplificare (molto), lasciate f e g essere due funzioni f : N -> N e g : N -> N. Diciamo che f is O(g) se e solo se c'è una costante M > 0 tale che |f(n)| < M|g(n)|, per tutti n > M. Cioè, più informale, a partire da un grande valore n, tutti i valori f(n) sono più piccoli di un multiplo di g(n) (vale a dire, g cresce più velocemente di f).

Questa definizione è equivalente a

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

Quindi, prendiamo f(n) = 4n^2 + 7n e g(n) = n^2, e cercare di dimostrare f is O(g) (io omettere {n -> +oo}):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

Questo implica che ci sia una M tale che n > M ==> |f(n)| < M|g(n)|, e quindi f is O(g).

Quindi tecnicamente è corretto dire 4n^2 + 7n is O(4n^2), come è corretto dire 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n), e così via. Ma per essere significativo, ci interessa il limite inferiore. Quindi, se f is O(e^n) e f is O(n^2), siamo più interessati nel sapere che f is O(n^2), dal momento che questo è molto più restrittiva.

nota molto importante

Qual è extremelly importante nella scelta di un algoritmo è quello di capire che notazioni O grande si riferisce a casi asintotica , cioè, se si considera estremamente, inimmaginabile enormi ingressi , che possono andare ben oltre la potenza di calcolo disponibile nell'universo conosciuto (ossia settata infiniti, espressa matematicamente da {n -> +oo}).

Per gli impieghi pratici (ad esempio, non è così ingressi enormi), quando si sceglie un algoritmo, certo, si potrà osservare gli algoritmi candidati notazioni O grande , ma si deve essere assicurarsi che l'algoritmo scelto è ben adattato (e funziona meglio) per il vostro input (expected).

Infine, di solito migliori algoritmi performanti sono più difficili da capire e da implementare correttamente. È necessario considerare questo fatto come pure nella scelta di un algoritmo (cioè, è il tempo passerò il debug e fissare la mia realizzazione di questo algoritmo considerevolmente superiore al tempo avrei dovuto aspettare con un altro algoritmo, con una notazione O-grande peggio? . Se è così, si dovrebbe considerare l'algoritmo meno efficiente più semplice, come la soluzione complessiva sarebbe più efficiente).

Answer 4

E 'O (n ^ 2). fattori costanti "entrano nella O". Si mantiene solo il più grande esponente in quanto questo è quello dominante. E si può lasciare fuori coefficienti poiché quando si confrontano diversi algoritmi anche molto grandi coefficienti risultano in numero totale più piccoli di avere un esponente più grande (con n abbastanza grande).

Answer 5

Una dichiarazione del genere

4n² + 7n = O(n²)

significa che per qualche c moltiplicatore costante, l'espressione cn² finirà per superare 4n² + 7n. Non è tecnicamente errato di lasciare il coefficiente in là - O(n²) e O(4n²) significano la stessa cosa, perché ogni c costante per l'ex può essere sostituito da c/4 per il secondo. Tuttavia, una cosa del genere è meno chiaro, possibilmente fuorviante, e sicuramente non standard.

Answer 6

Matematicamente parlando, si può scrivere O (4n²). Ciò significa che la funzione di complessità degli algoritmi si comporta come n-> 4n² verso positivo infinito.

Ma in informatica / algoritmo, si sarebbe solo scrivere O (n²), che è sufficiente per classificare il vostro algoritmo.