Notazione O-grande di un'espressione
-
21-09-2019 - |
Domanda
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
Soluzione
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.
Altri suggerimenti
I coefficienti non sono rilevanti nella notazione O-grande, quindi è solo O (n 2 ). Come Wikipedia spiega :
[...] i coefficienti diventano irrilevanti se confrontiamo qualsiasi altro ordine di espressione, come espressione contenente un termine n 3 o n 2 .
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).
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).
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.
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.