Big Oh notation non menziona il valore costante

O (n) e l'altra notazione degli ordini (in genere) non riguardano il comportamento delle funzioni per valori piccoli. Riguarda il comportamento di funzioni per valori molto grandi, vale a dire i limiti come n si muove verso l'infinito.

Le costanti sono tecnicamente importanti ma sono tipicamente astratte via via che una volta n diventa sufficientemente grande, il valore di c è del tutto irrilevante. Se il valore di c è importante, possiamo includerlo nell'analisi, ma a meno che le funzioni che vengono confrontate abbiano fattori costanti molto grandi o se l'efficienza sia un problema particolarmente importante, in genere non lo sono.

Ci sono diversi motivi, ma probabilmente il più importante è che le costanti sono una funzione dell'implementazione dell'algoritmo, non dell'algoritmo stesso. L'ordine di un algoritmo è utile per confrontare algoritmi indipendentemente dalla loro implementazione.

L'effettivo runtime di un quicksort in genere cambia se è implementato in C o Python o Scala o Postscript. Lo stesso vale per ordinamento a fumetto - il runtime varierà ampiamente in base all'implementazione.

Tuttavia, ciò che non cambierà è il fatto che, a parità di tutti gli altri, con l'aumentare del set di dati il tempo richiesto per eseguire un ordinamento di bolle aumenterà più velocemente del tempo richiesto per eseguire quicksort in il caso tipico, indipendentemente dalla lingua o dalla macchina con cui sono implementati, assumendo un'implementazione ragionevolmente corretta. Questo semplice fatto ti permette di fare inferenze intelligenti sugli stessi algoritmi quando i dettagli concreti non sono disponibili.

L' ordine di un algoritmo filtra i fattori che, sebbene importanti nelle misurazioni reali del mondo reale, tendono a essere solo rumore quando confrontano algoritmi in astratto.

La notazione Big O secondo la definizione afferma che:
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}
La notazione Big O è costruita sull'intuizione che per tutti i valori n at e alla destra di n ', il valore di f (n) è sopra o sotto c.g (n).
Anche le costanti non hanno importanza quando si passano a fattori (variabili) di valore elevato (come n-quadrato o n-cubo) poiché sono solo le costanti e non le quantità variabili che possono diventare grandi come tali fattori.
Di seguito è riportato il grafico della notazione Big-O.

L'essenzadiquestanotazioneènelfatto" how lower is f(n) from c.g(n) and not when it starts becoming lower ".

Nell'analisi dell'algoritmo, Ordine di crescita è l'astrazione chiave e fornisce la velocità con cui il tempo di esecuzione cambia al variare delle dimensioni dell'input. Supponiamo che un algoritmo abbia un tempo di esecuzione f(n) = 2n + 3 . Ora inseriamo alcune dimensioni di input,

n = 10: 2 * 10 + 3 = 23

n = 100: 2 * 100 + 3 = 203

n = 10000: 2 * 10000 + 3 = 20003

n = 1000000: 2 * 1000000 + 3 = 2000003

n = 100000000 : 2 * 100000000 + 3 = 200000003

Come si può vedere, l'ordine di crescita è determinato principalmente dalla variabile n ; le costanti 2 e 3 sono meno significative e man mano che le dimensioni dell'ingresso crescono diventano ancora meno significative nel determinarlo. Questo è il motivo per cui le costanti dell'analisi dell'algoritmo si abbassano a favore della variabile che determina l'ordine di crescita di una funzione.

(poiché questa è una risposta più lunga, leggi i grassetti per un sommario )

Prendiamo il tuo esempio e seguilo passo passo, comprendendo lo scopo dietro ciò che stiamo facendo. Iniziamo con la tua funzione e l'obiettivo di trovare la sua notazione Big Oh:

f(n) = 6n+4

Innanzitutto, lascia che O(g(n)) sia la notazione Big Oh che stiamo cercando di trovare per f(n) . Dalla definizione di Big Oh, dobbiamo trovare un semplificato g(n) dove esistono alcune costanti c e n0 dove c*g(n) >= f(n) è vero per tutto n ' s maggiore di n0 .

Per prima cosa, scegliamo g(n) = 6n + 4 (che renderebbe O(6n+4) in Big Oh). In questo caso vediamo che c = 1 e qualsiasi valore di n0 soddisferanno i requisiti matematici dalla nostra definizione di Big Oh, poiché g(n) è sempre uguale a f(n) :

c*g(n)      >=  f(n)    
1*(6n + 4)  >=  6n + 4    //True for all n's, so we don't need to pick an n0

A questo punto abbiamo soddisfatto i requisiti matematici. Se ci fermiamo a O(6n+4) , è chiaro che non è più utile della scrittura di f(n) , quindi perderebbe il vero scopo della notazione di Big Oh: capire il tempo generale- complessità di un algoritmo! Quindi, passiamo al prossimo passo: semplificazione.

Innanzitutto, possiamo semplificare il 6n in modo che Big Oh sia O(4) ? No! (Esercizio per il lettore se non capiscono perché)

Secondo, possiamo semplificare la 4 in modo che Big Oh sia O(6n) ? Sì! In tal caso, g(n) = 6n , quindi:

c*g(n)    >=  f(n)
c*6n      >=  6n + 4     

A questo punto, scegliamo c = 2 da allora il lato sinistro aumenterà più velocemente (di 12) rispetto al lato destro (di 6) per ogni incremento di n .

2*6n      >=  6n + 4

Ora dobbiamo trovare un n0 positivo in cui l'equazione precedente è vera per tutto n 's maggiore di quel valore. Poiché sappiamo già che il lato sinistro sta aumentando più velocemente del giusto, tutto ciò che dobbiamo fare è trovare una soluzione positiva. Pertanto, poiché n0 = 2 rende vero quanto sopra, sappiamo che g(n)=6n , o O(6n) è una potenziale notazione Big Oh per f(n) .

Ora, possiamo semplificare la 6 in modo che Big Oh sia O(n) ? Sì! In tal caso, g(n) = n , quindi:

c*g(n)      >=  f(n)    
c*n         >=  6n + 4    

Selezioniamo c = 7 poiché la sinistra aumenterebbe più velocemente della destra.

7*n         >=  6n + 4

Vediamo che quanto sopra sarà vero per tutto n 's maggiore o uguale a n0 = 4 . Pertanto, O(n) è una potenziale notazione di Big Oh per f(n) . Possiamo semplificare più g(n) ? No!

Infine, abbiamo rilevato che la notazione Big Oh più semplice per f(n) è O(n) . Perché abbiamo affrontato tutto questo? Poiché ora sappiamo che f(n) è lineare , poiché la notazione Big Oh è di complessità lineare O(n) . La cosa bella è che ora possiamo confrontare la complessità temporale di f(n) con altri algoritmi! Ad esempio, ora sappiamo che f(n) è di complessità temporale paragonabile alle funzioni h(n) = 123n + 72 , i(n) = n , j(n) = .0002n + 1234 , ecc; poiché utilizzando lo stesso processo di semplificazione descritto sopra, tutti hanno una complessità temporale lineare di O(n) .

dolce !!!

Se hai una funzione di rendimento di 6n + 4 , la domanda pertinente è "6 cosa?". Come un commento ha chiesto: cosa rappresenta la tua costante? In termini di fisica, quali sono le unità del tuo fattore costante?

Il motivo per cui la notazione O () è così ampiamente usata per descrivere le prestazioni dell'algoritmo è che non esiste un modo portabile per rispondere a questa domanda. Diversi processori impiegheranno un diverso numero di cicli di clock e diverse quantità di tempo per eseguire lo stesso calcolo elementare, oppure potrebbero variare in modo diverso i calcoli elementari rilevanti. Diversi linguaggi informatici, o diverse descrizioni formali e informali come lo pseudocodice, rappresenteranno algoritmi in modi che sono difficili da confrontare direttamente. Anche le implementazioni nella stessa lingua possono rappresentare lo stesso algoritmo in modi diversi: dettagli di formattazione banale come il numero di righe a parte, in genere è disponibile una vasta gamma di scelte strutturali arbitrarie per implementare qualsiasi algoritmo specificato.

Guardalo in un altro modo: usiamo "algoritmo" per non descrivere una particolare implementazione, ma per descrivere un'intera classe di potenziali implementazioni della stessa procedura generale. Questa astrazione ignora i dettagli dell'attuazione a favore di documentare qualcosa di valore generale e il fattore di prestazione costante è uno di questi dettagli.

Detto questo, le descrizioni degli algoritmi sono spesso accompagnate da folclore, note o anche benchmark effettivi che descrivono le prestazioni delle implementazioni effettive sull'hardware reale. Questo ti dà un'idea approssimativa di quale tipo di fattore costante aspettarti, ma dovrebbe anche essere preso con un pizzico di sale perché le prestazioni effettive dipendono da cose come il lavoro svolto nell'ottimizzazione di una determinata implementazione. Inoltre, a lungo termine, le prestazioni relative di algoritmi comparabili tendono a oscillare man mano che l'architettura dei più recenti e grandi processori cambia ...

L'intera nozione di notazione Big-Oh è specificamente quella di ignorare le costanti e presentare la parte più importante della funzione che descrive il tempo di esecuzione di un algoritmo.

Dimentica la definizione formale per un momento. Qual è la funzione peggiore (più rapida crescita), n^2 - 5000 o 5000 n + 60000 ? Per n in meno di circa 5000, la funzione lineare è maggiore (e quindi peggiore). Oltre a questo (valore esatto 5013?), L'equazione quadratica è maggiore.

Dato che ci sono più (un bel po 'di più) numeri positivi maggiori di 5000 rispetto a meno, consideriamo la quadratica come la funzione "più grande" (peggio) in generale. La notazione degli ordini (Big-Oh, ecc.) Impone che (puoi sempre eliminare un additivo e una costante moltiplicativa usando quelle definizioni).

Certo, le cose non sono sempre semplici. A volte tu fai vuoi sapere quelle costanti. Qual è l'ordinamento Inserimento o il tipo Bubble? Entrambi sono O(n^2) . Ma uno è davvero meglio dell'altro. Con analisi più elaborate si possono ottenere costanti come te ne stavi chiedendo. Di solito è molto più semplice calcolare la funzione Big-Oh di una funzione più precisa.

Big-Oh ignora queste costanti per semplificare e semplificare i confronti più importanti. Ci piace la notazione perché di solito non desidera conoscere le costanti (per lo più irrilevanti).