Qual è una semplice spiegazione inglese della notazione "Big O"?

https://stackoverflow.com/questions/487258

20-08-2019
|

Domanda

Preferirei la minima definizione formale possibile e una matematica semplice.

Soluzione

Nota veloce, questo è quasi certamente fonte di confusione Notazione O grande (che è un limite superiore) con la notazione Theta "Θ" (che è un limite su due lati).Nella mia esperienza, questo è in realtà tipico delle discussioni in contesti non accademici.Ci scusiamo per l'eventuale confusione causata.

La complessità di Big O può essere visualizzata con questo grafico:

Big O Analysis

La definizione più semplice che posso dare per la notazione Big-O è questa:

La notazione Big-O è una rappresentazione relativa della complessità di un algoritmo.

Ci sono alcune parole importanti e scelte deliberatamente in quella frase:

parente: puoi solo confrontare le mele con le mele.Non è possibile confrontare un algoritmo per eseguire moltiplicazioni aritmetiche con un algoritmo che ordina un elenco di numeri interi.Ma un confronto tra due algoritmi per eseguire operazioni aritmetiche (una moltiplicazione, una addizione) ti dirà qualcosa di significativo;

rappresentazione: Big-O (nella sua forma più semplice) riduce il confronto tra algoritmi a una singola variabile.Tale variabile viene scelta sulla base di osservazioni o ipotesi.Ad esempio, gli algoritmi di ordinamento vengono generalmente confrontati in base a operazioni di confronto (confronto di due nodi per determinarne l'ordinamento relativo).Ciò presuppone che il confronto sia costoso.Ma cosa succede se il confronto è economico ma lo scambio è costoso?Cambia il paragone;E

complessità: se mi occorre un secondo per ordinare 10.000 elementi quanto tempo mi occorrerà per ordinarne un milione?La complessità in questo caso è una misura relativa a qualcos'altro.

Torna indietro e rileggi quanto sopra dopo aver letto il resto.

Il miglior esempio di Big-O che mi viene in mente è fare aritmetica.Prendi due numeri (123456 e 789012).Le operazioni aritmetiche di base che abbiamo imparato a scuola erano:

aggiunta;

sottrazione;

moltiplicazione;E

divisione.

Ognuno di questi è un'operazione o un problema.Un metodo per risolverli è chiamato an algoritmo.

L'addizione è la più semplice.Allinei i numeri (a destra) e aggiungi le cifre in una colonna scrivendo l'ultimo numero di quell'addizione nel risultato.La parte "decine" di quel numero viene riportata nella colonna successiva.

Supponiamo che l'addizione di questi numeri sia l'operazione più costosa in questo algoritmo.È ovvio che per sommare questi due numeri dobbiamo sommare 6 cifre (e possibilmente portarne una settima).Se sommiamo due numeri da 100 cifre insieme dobbiamo fare 100 addizioni.Se aggiungiamo due Numeri di 10.000 cifre dobbiamo fare 10.000 addizioni.

Vedi lo schema?IL complessità (essendo il numero di operazioni) è direttamente proporzionale al numero di cifre N nel numero maggiore.Lo chiamiamo SU) O complessità lineare.

La sottrazione è simile (tranne che potrebbe essere necessario prendere in prestito invece di portare).

La moltiplicazione è diversa.Allinei i numeri, prendi la prima cifra del numero in basso e la moltiplichi a turno per ciascuna cifra del numero in alto e così via attraverso ciascuna cifra.Quindi per moltiplicare i nostri due numeri a 6 cifre dobbiamo fare 36 moltiplicazioni.Potrebbe essere necessario aggiungere fino a 10 o 11 colonne per ottenere anche il risultato finale.

Se abbiamo due numeri da 100 cifre dobbiamo fare 10.000 moltiplicazioni e 200 addizioni.Per due numeri da un milione di cifre dobbiamo fare un trilione (10¹²) moltiplicazioni e due milioni di addizioni.

Poiché l'algoritmo scala con n-quadrato, questo è SU²) O complessità quadratica.Questo è un buon momento per introdurre un altro concetto importante:

Ci preoccupiamo solo della parte più significativa della complessità.

L’astuto potrebbe aver capito che potremmo esprimere il numero di operazioni come:N² + 2n.Ma come hai visto nel nostro esempio con due numeri da un milione di cifre ciascuno, il secondo termine (2n) diventa insignificante (rappresentando in quella fase lo 0,0002% delle operazioni totali).

Si può notare che qui abbiamo ipotizzato lo scenario peggiore.Mentre moltiplichiamo numeri a 6 cifre, se uno di essi è di 4 cifre e l'altro è di 6 cifre, avremo solo 24 moltiplicazioni.Tuttavia calcoliamo lo scenario peggiore per quella "n", cioè quando entrambi sono numeri a 6 cifre.Quindi la notazione Big-O riguarda lo scenario peggiore di un algoritmo

L'elenco telefonico

L'altro miglior esempio che mi viene in mente è l'elenco telefonico, normalmente chiamato Pagine Bianche o simili ma varia da paese a paese.Ma sto parlando di quello che elenca le persone per cognome e poi iniziali o nome, eventualmente indirizzo e poi numeri di telefono.

Ora, se dovessi istruire un computer a cercare il numero di telefono di "John Smith" in un elenco telefonico che contiene 1.000.000 di nomi, cosa faresti?Ignorando il fatto che potresti indovinare a che punto iniziano le S (supponiamo che non puoi), cosa faresti?

Una tipica implementazione potrebbe essere quella di aprire al centro, prendendo i 500.000^th e confrontarlo con "Smith".Se si tratta di "Smith, John", siamo stati davvero fortunati.Molto più probabile è che "John Smith" sia prima o dopo quel nome.Se è dopo, dividiamo a metà l'ultima metà della rubrica e ripetiamo.Se è prima, dividiamo a metà la prima metà della rubrica e ripetiamo.E così via.

Questo è chiamato a ricerca binaria e viene utilizzato ogni giorno nella programmazione, che tu te ne accorga o no.

Quindi, se vuoi trovare un nome in una rubrica di un milione di nomi, puoi effettivamente trovare qualsiasi nome eseguendo questa operazione al massimo 20 volte.Nel confrontare gli algoritmi di ricerca decidiamo che questo confronto è la nostra "n".

Per una rubrica di 3 nomi sono necessari 2 confronti (al massimo).

Per 7 ce ne vogliono al massimo 3.

Per 15 ne servono 4.

…

Per 1.000.000 ce ne vogliono 20.

È incredibilmente buono, non è vero?

In termini Big-O questo è O(log n) O complessità logaritmica.Ora il logaritmo in questione potrebbe essere ln (base e), log₁₀, tronco d'albero₂ o qualche altra base.Non importa, è ancora O(log n) proprio come O(2n²) e O(100n²) sono ancora entrambi O(n²).

Vale la pena a questo punto spiegare che Big O può essere utilizzato per determinare tre casi con un algoritmo:

Caso migliore: Nella ricerca nell'elenco telefonico la cosa migliore è che troviamo il nome in un confronto.Questo è O(1) O complessità costante;

Caso previsto: Come discusso sopra questo è O(log n);E

Caso peggiore: Anche questo è O(log n).

Normalmente non ci interessa il caso migliore.Siamo interessati al caso previsto e peggiore.A volte l'uno o l'altro di questi sarà più importante.

Torniamo all'elenco telefonico.

Cosa succede se hai un numero di telefono e vuoi trovare un nome?La polizia dispone di un elenco telefonico inverso, ma tali ricerche sono negate al grande pubblico.Oppure lo sono?Tecnicamente è possibile effettuare la ricerca inversa di un numero in una normale rubrica telefonica.Come?

Inizi dal nome e confronti il numero.Se è una partita, bene, altrimenti si passa a quella successiva.Devi farlo in questo modo perché la rubrica lo è non ordinato (comunque tramite numero di telefono).

Quindi, per trovare un nome dato il numero di telefono (ricerca inversa):

Caso migliore: O(1);

Caso previsto: O(n) (per 500.000);E

Caso peggiore: O(n) (per 1.000.000).

Il commesso viaggiatore

Questo è un problema piuttosto famoso in informatica e merita una menzione.In questo problema hai N città.Ognuna di queste città è collegata ad 1 o più altre città da una strada di una certa distanza.Il problema del commesso viaggiatore è trovare il tour più breve che tocchi ogni città.

Sembra semplice?Pensa di nuovo.

Se hai 3 città A, B e C con strade tra tutte le coppie, potresti procedere:

A→B→C

A→C→B

B → C → A

B → A → C

C → A → B

C → B → A

Beh, in realtà ce n'è meno perché alcuni di questi sono equivalenti (A → B → C e C → B → A sono equivalenti, ad esempio, perché usano le stesse strade, solo al contrario).

In realtà ci sono 3 possibilità.

Portalo in 4 città e avrai (iirc) 12 possibilità.

Con 5 sono 60.

6 diventa 360.

Questa è una funzione di un'operazione matematica chiamata a fattoriale.Fondamentalmente:

5! = 5 × 4 × 3 × 2 × 1 = 120

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040

…

25! = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000

…

50! = 50 × 49 × … × 2 × 1 = 3.04140932 × 10⁶⁴

Quindi la Big-O del problema del commesso viaggiatore è SU!) O complessità fattoriale o combinatoria.

Quando arrivi a 200 città non c'è più abbastanza tempo nell'universo per risolvere il problema con i computer tradizionali.

Qualcosa a cui pensare.

Tempo polinomiale

Un altro punto che volevo menzionare rapidamente è che qualsiasi algoritmo che abbia una complessità di SU^UN) si dice che abbia complessità polinomiale o è risolvibile in tempo polinomiale.

O(n), O(n²) eccetera.sono tutti tempi polinomiali.Alcuni problemi non possono essere risolti in tempo polinomiale.Certe cose vengono usate nel mondo per questo motivo. Crittografia a chiave pubblica è un ottimo esempio.È computazionalmente difficile trovare due fattori primi di un numero molto grande.Se così non fosse, non potremmo usare i sistemi a chiave pubblica che usiamo.

Ad ogni modo, questo è tutto per la mia spiegazione (si spera in un inglese semplice) di Big O (rivisto).

Altri suggerimenti

Si mostra come un algoritmo scale.

O (n ²) : noto come complessità quadratica

1 articolo: 1 secondo
10 articoli: 100 secondi
100 oggetti: 10000 secondi

Si noti che il numero di elementi aumenta di un fattore 10, ma il tempo aumenta di un fattore 10 ². Fondamentalmente, n = 10 e quindi O (n ²) ci dà il fattore di scala n ² che è 10 ².

O (n) : noto come complessità lineare

1 articolo: 1 secondo
10 articoli: 10 secondi
100 oggetti: 100 secondi

Questa volta il numero di elementi aumenta di un fattore 10, e così fa il tempo. n = 10 e quindi O (n) s 'fattore di scala è 10.

O (1) : noto come complessità costante

1 articolo: 1 secondo
10 articoli: 1 secondo
100 oggetti: 1 secondo

Il numero di elementi continua ad aumentare di un fattore di 10, ma il fattore di scala di O (1) è sempre 1.

O (log n) : noto come complessità logaritmica

1 articolo: 1 secondo
10 articoli: 2 secondi
100 oggetti: 3 secondi
1000 articoli: 4 secondi
10000 articoli: 5 secondi

Il numero di calcoli è aumentato solo di un registro del valore di ingresso. Quindi, in questo caso, assumendo ogni calcolo prende 1 secondo il registro dell'ingresso n è il tempo necessario, quindi log n.

Questa è l'essenza di esso. Riducono la matematica verso il basso quindi potrebbe non essere esattamente n ² o qualsiasi altra cosa si dice che è, ma che sarà il fattore dominante nella scala.

notazione O-grande (chiamato anche "la crescita asintotica" notazione) è quali funzioni "guarda come" quando si ignorano i fattori costanti e roba vicino all'origine . L'usiamo per parlare di come scala cosa .

Nozioni di base

per "sufficientemente" grandi ingressi ...

f(x) ∈ O(upperbound) significa f "non più veloce cresce di" upperbound
f(x) ∈ Ɵ(justlikethis) significa justlikethis "cresce esattamente come" f(x) ∈ Ω(lowerbound)
lowerbound significa 9x² "cresce non più lento di" 10x²

notazione O-grande non si preoccupa di fattori costanti: la funzione 10x² - x + 2 è detto di "crescere esattamente come" O(...). Nemmeno grande O- asintotica cura notazione su non asintotico stuff ( "roba vicino all'origine" o "cosa succede quando la dimensione del problema è piccolo"): la funzione < => si dice che "crescere esattamente come" N*log(N).

Perché si vuole ignorare le parti più piccole dell'equazione? Perché diventano completamente sminuito dai grandi parti della equazione come si considera scale sempre più grandi; il loro contributo diventa nano e irrilevante. (Vedere la sezione esempio.)

Detto in altro modo, è tutta una questione di rapporto , come si va all'infinito. Se si divide il tempo effettivo necessario dal f(x), si otterrà un fattore costante nel limite di grandi ingressi Intuitivamente questo ha un senso:. Funzioni "scala come" l'un l'altro, se è possibile moltiplicare uno per ottenere l'altra. Cioè, quando si dice ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... questo significa che per "abbastanza grande" problema di dimensioni N (se ignoriamo roba vicino all'origine), esiste una costante (ad esempio 2,5, completamente fatta) in modo tale che:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)

Ci sono molte scelte di costante; spesso la scelta "migliore" è conosciuto come il "fattore costante" dell'algoritmo ... ma spesso ignorano come noi ignoriamo termini non più grandi (vedi sezione Fattori costante per il motivo per cui di solito non importa). Si può anche pensare di equazione di cui sopra come un limite, ad esempio " Nel peggiore dei casi, il tempo necessario sarà mai peggio di circa N, all'interno di un fattore di 2,5 (un fattore costante noi don' t cura molto circa) ".

In generale, Ɵ(N²) è la più utile perché spesso ci preoccupiamo per il comportamento nel caso peggiore. Se N(N-1)/2 rappresenta qualcosa di "cattivo", come processore o l'utilizzo della memoria, poi "N²" significa "#handshakes ∈ Ɵ(N²) è il peggior scenario di utilizzo del processore / memoria".

Applicazioni

Come un costrutto puramente matematico, notazione O-grande non si limita a parlare di tempo di elaborazione e la memoria. Si può usare per discutere i asintotica di qualsiasi cosa in cui scala è significativa, come ad esempio:

il numero di strette di mano tra possibilmente N*(N-1)/2 persone ad un partito (order N², in particolare lim, ma ciò che conta è che "scale come" O(N))
Numero probabilistica atteso di persone che hanno visto alcuni di marketing virale in funzione del tempo
come squame di latenza sito con il numero di unità di elaborazione in una CPU o un cluster GPU o un computer
come scale di uscita di calore sulla CPU muore in funzione del numero di transistor, tensione, ecc.
quanto tempo un algoritmo deve essere eseguito, in funzione della dimensione di input
quanto spazio ha bisogno di un algoritmo per l'esecuzione, in funzione della dimensione di input

Esempio

Per l'esempio di stretta di mano sopra, tutti in una stanza stringe la mano di tutti gli altri. In tale esempio, O(N log(log(N))). Perché?

Backup un po ': il numero di strette di mano è esattamente n-scegliere-2 o 100000*N log(log(N)) (ciascuno di N persone scuote le mani di N-1 altre persone, ma questo doppio-conti strette di mano in modo da dividere per 2):

href="https://i.stack.imgur.com/rqQMF.png" rel="noreferrer"> adjmatrix acency

Tuttavia, per un gran numero di persone, il termine lineare + 100*N è sminuito ed efficace contribuisce 0 al rapporto (nel grafico: la frazione di scatole vuote sulla diagonale sopra scatole totale si riduce il numero di partecipanti diventa più grande). Pertanto il comportamento di scala è O(N!), o il numero di strette di mano "cresce come n²".

#handshakes(N)
────────────── ≈ 1/2
     N²

È come se le caselle vuote sulla diagonale del grafico (N * (N-1) / 2 segni di spunta) non erano ancora lì (N ² checkmarks asintoticamente).

(digressione temporanea da "Inglese plain" :) Se si voleva dimostrare questo a te stesso, è possibile eseguire alcune semplici algebra sul rapporto di dividerlo in termini multipli (O(N log(N)) significa "considerati nel limite del" , basta ignorarlo, se non l'avete visto, è solo la notazione per "e N è davvero grande"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Il numero di 'assomiglia' strette di mano x² così tanto per i valori di grandi dimensioni, che se dovessimo annotare il rapporto # strette di mano / x², il fatto che non abbiamo bisogno di esattamente X² strette di mano non sarebbe nemmeno presentarsi in decimale per un numero arbitrariamente grande di tempo.

es. per x = 1 milione, il rapporto # strette di mano / x²: 0,499,999 mila ...

Edificio intuizione

Questo ci permette di fare affermazioni come ...

"Per gran inputsize abbastanza = N, non importa quale sia il fattore costante è, se I doppia la dimensione di input ...

... ho il doppio del tempo di un O (N) ( "tempo lineare") algoritmo prende."

N → (2N) = 2 ( N )
... I doppio-squared (quadruple) il tempo di un O (n²) ( "tempo quadratica") algoritmo prende." (ad esempio, un problema 100x grande prende 100² = 10000X il più a lungo ... forse insostenibili)

n² → (2N) ² = 4 ( n² )
... I due cubetti (octuple) il tempo di un O (N³) ( "Tempo cubico") algoritmo prende." (ad esempio, un problema 100x grande prende 100³ = 1000000x più a lungo ... molto insostenibili)

cN³ → c (2N) ³ = 8 ( cN³ )
... aggiungo un importo fisso per il tempo di un O (log (N)) ( "tempo logaritmico") algoritmo prende." (a buon mercato!)

log (n) → c log (2N) = (log c (2)) + ( log (n) ) = (importo fisso) + ( log (n) )
... Io non cambio il tempo di un O (1) ( "costante di tempo") algoritmo prende ". (il più economico!)

c * 1 → c * 1
... I "(in fondo) doppio" il tempo di un O (log N (N)) algoritmo prende." (abbastanza comune)

è inferiore a O (N ^{1,000,001 mila}), che si potrebbe essere disposto a chiamare fondamentalmente lineare
... Ho ridicolmente aumentare il tempo di un O (2 ^N) ( "tempo esponenziale") algoritmo prende." (faresti doppio (o triplo, ecc), il tempo solo aumentando il problema da una sola unità)

2 ^N → 2 ^2N = (4 ^N) ......... ... in altre parole ...... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[per il matematicamente inclinato, è possibile mouse sulle spoiler per note a margine minori]

(con credito per https://stackoverflow.com/a/487292/711085 )

(tecnicamente il fattore costante potrebbe forse materia in alcuni esempi più esoterici, ma ho formulato le cose di cui sopra (per esempio a log (N)) tale che non lo fa)

Questi sono iordini di pane e burro di crescita che i programmatori e gli scienziati informatici applicati usano come punti di riferimento. Vedono questi tutto il tempo. (Così, mentre si potrebbe tecnicamente pensare "Raddoppiando l'ingresso rende un O (√N) algoritmo di 1.414 volte più lento," è meglio pensare ad esso come "questo è peggio di logaritmica ma meglio di lineare".)

i fattori costanti

Di solito non ci interessa quello che gli specifici fattori costanti sono, perché non influiscono sul modo in cui la funzione cresce. Ad esempio, due algoritmi possono entrambi prendono O(N²) tempo per completare, ma possono essere due volte più lento l'altro. Noi di solito non ci importa troppo a meno che il fattore è molto grande, dal momento che l'ottimizzazione è faccenda complicata ( quando è l'ottimizzazione prematura ); anche il semplice atto di prendere un algoritmo con una migliore O-grande spesso migliorare le prestazioni di diversi ordini di grandezza.

Alcuni algoritmi asintoticamente superiori (ad esempio un non-confronto O(1) ordinamento) possono avere così grande un fattore costante (es O(log(N))) o sovraccarico che è relativamente grande come x con una nascosta O(N^2), che sono raramente vale la pena utilizzare anche sui "grandi dati".

Perché O (N) a volte è la migliore che puoi fare, vale a dire il motivo per cui abbiamo bisogno di strutture di dati

O(N)/N algoritmi sono in un certo senso gli algoritmi "migliori", se avete bisogno di leggere tutti i dati. Il atto stesso di lettura una serie di dati è un'operazione O([length of text] + [length of query]). Caricamento in memoria di solito è O(N+M) (o più veloce se si dispone di supporto hardware, o che non si dica, se avete già letto i dati). Tuttavia, se si tocca o anche Cerca ad ogni pezzo di dati (o anche ogni altro pezzo di dati), l'algoritmo avrà O([length of text]*[length of query]) tempo per eseguire questa ricerca. Nomatter quanto tempo il vostro algoritmo attuale prende, sarà almeno O(N*M) perché ha speso quel tempo a guardare tutti i dati.

Lo stesso si può dire per il molto atto di scrivere . Tutti gli algoritmi che stampano N cose richiedono tempo N, perché l'uscita è almeno così a lungo (ad esempio la stampa di tutte le permutazioni (modi per riorganizzare) un insieme di N carte da gioco è fattoriale: f(x) ∈ O(g(x))).

Questo motiva l'uso di strutture dati : una struttura di dati richiede la lettura dei dati solo una volta (solitamente |f(x)| ≤ const * |g(x)| tempo), oltre a una certa quantità arbitraria di pre-elaborazione (ad esempio O o Ω o o), che cerchiamo di mantenere piccole. Successivamente, modificando la struttura dei dati (inserimenti / delezioni / etc.) e rendendo le query sui dati occupano poco tempo, come ω o f(x) ∈ Ɵ(g(x)). È quindi procedere a fare un gran numero di query! In generale, il lavoro più si è disposti a fare prima del tempo, meno lavoro che dovrà fare in seguito.

Ad esempio, dire che hai avuto le coordinate di latitudine e longitudine di milioni di segmenti di strade, e volevo trovare tutte le intersezioni stradali.

metodo Naive:. Se tu avessi le coordinate di un incrocio stradale, e ha voluto esaminare strade vicine, si dovrà passare attraverso i milioni di segmenti di volta in volta, e verificare ciascuno per adiacenze
Se avete solo bisogno di fare questo una volta, non sarebbe un problema di avere a che fare il metodo ingenuo di f(x) ∈ Ω(g(x)) lavoro solo una volta, ma se si vuole fare molte volte (in questo caso, const1*g(x) volte, una per ogni segmento), avremmo dovuto fare const2*g(x) lavoro, o 1000000² = 1000000000000 operazioni. Non va bene (un computer moderno in grado di eseguire circa un miliardo di operazioni al secondo).
Se usiamo una struttura semplice chiamata una tabella hash (una tabella di riferimento istante velocità, noto anche come un HashMap o un dizionario), paghiamo un piccolo costo da pre-elaborazione tutto in == tempo. Successivamente, ci vuole solo tempo costante, in media, per cercare qualcosa da sua chiave (in questo caso, la chiave è la latitudine e longitudine, arrotondati in una rete; cerchiamo i gridspaces adiacenti di cui ci sono solo 9, che è un costante).
Il nostro compito è andatoda un fattibile = O(...) a un gestibile ∈ O(...), e tutti abbiamo dovuto fare era pagare un costo minore per fare una tabella di hash.
analogia : L'analogia in questo caso particolare, è un puzzle: Abbiamo creato una struttura dati che sfrutta alcune proprietà dei dati. Se i nostri tratti di strada sono come pezzi di un puzzle, ci raggrupparli abbinando il colore ed il modello. Abbiamo poi sfruttare questo per evitare di fare un lavoro extra dopo (confrontando i pezzi del puzzle di colore come gli uni agli altri, non ad ogni altro pezzo di puzzle singolo).

La morale della storia: una struttura di dati ci permette di velocizzare le operazioni. Anche le più avanzate strutture di dati può farvi combinare, ritardare, o addirittura ignorare le operazioni in modi incredibilmente intelligenti. Diversi problemi si hanno diverse analogie, ma avevano tutte coinvolgere organizzare i dati in un modo che sfrutta qualche struttura ci sta a cuore, o di cui abbiamo artificialmente imposto su di esso per la contabilità. Noi lavoriamo in anticipo (in pratica di pianificazione e organizzazione), ei compiti ora ripetuti siamo molto più facile!

Esempio pratico: visualizzare gli ordini di crescita, mentre la codifica

notazione asintotica è, nella sua essenza, tutto separato dalla programmazione. notazione asintotica è un framework matematico per pensare a come scalare le cose, e può essere utilizzato in molti campi diversi. Detto questo ... questo è il modo per Applica notazione asintotica alla codifica.

I principi fondamentali: Ogni volta che ci interagiamo con ogni elemento in un insieme di dimensione A (ad esempio una matrice, un set, tutte le chiavi di una mappa, ecc), o eseguire un'iterazioni di un ciclo, che è un fattore multiplcative di dimensioni A. perché dico "un fattore moltiplicativo" - perché i cicli e le funzioni (quasi per definizione) hanno il tempo di funzionamento moltiplicativa:? il numero di iterazioni, tempi lavoro svolto nel ciclo (o per le funzioni: il numero di volte si chiama la funzione, i tempi di lavoro svolto nella funzione). (Questo vale se non facciamo niente di eccezionale, come il loop saltare o uscire dal ciclo presto, o cambiamo flusso di controllo nella funzione sulla base di argomenti, che è molto comune.) Ecco alcuni esempi di tecniche di visualizzazione, con accompagnamento pseudocodice.

(qui, i ∈ s rappresentano unità costante di tempo di lavoro, istruzioni del processore, codici operativi interprete, quale che sia)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Esempio 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Esempio 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Se facciamo qualcosa di un po 'complicato, si potrebbe ancora essere in grado di immaginare visivamente quello che sta succedendo:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Qui, il più piccolo contorno riconoscibile è possibile disegnare è ciò che conta; un triangolo è una forma bidimensionale (0,5 A ^ 2), proprio come un quadrato è una forma bidimensionale (A ^ 2); il fattore costante di due qui rimane nel rapporto asintotico tra i due, ma l'ignoriamo come tutti i fattori ... (ci sono alcune sfumature sfortunati a questa tecnica non vado in questa sede, ma può indurre in errore voi.)

Naturalmente questo non significa che i cicli e le funzioni sono cattivi; al contrario, essi sono i mattoni dei moderni linguaggi di programmazione, e li amiamo. Tuttavia, possiamo vedere che il nostro modo di tessere loop e funzioni e condizionali insieme con i nostri dati (controllo di flusso, ecc) imita il tempo e l'utilizzo dello spazio del nostro programma! Se il tempo e l'utilizzo dello spazio diventa un problema, cioè quando si ricorre ad intelligenza, e trovare una struttura algoritmo o dei dati facile non avevamo considerato, per ridurre l'ordine di una crescita in qualche modo. Tuttavia, queste tecniche di visualizzazione (anche se non sempre funzionano) in grado di dare una supposizione naif in un caso peggiore tempo di esecuzione.

Qui è un'altra cosa che possiamo riconoscere visivamente:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

Possiamo solo riorganizzare questo e vedere che è O (N):

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

O forse non log (N) passa dei dati, per O (N * log (N)) tempo totale:

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Unrelatedly ma vale la pena ricordare ancora una volta: Se eseguiamo un hash (per esempio un dizionario / tabella hash di ricerca), che è un fattore di O (1). Questo è abbastanza veloce.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

Se non facciamo qualcosa di molto complicato, ad esempio con unfunzione ricorsiva o algoritmo divide et impera, ~~è possibile utilizzare il teorema (di solito opere), o in casi ridicole l'Akra-Bazzi Teorema (funziona quasi sempre)~~ si guarda il tempo di esecuzione del vostro algoritmo su Wikipedia.

Ma, i programmatori non pensano così perché alla fine, l'algoritmo intuizione diventa solo una seconda natura. Si inizierà a codice qualcosa inefficiente, e subito penso "sto facendo qualcosa di grossolanamente inefficiente? ". Se la risposta è "sì" e si prevede in realtà importando, allora si può fare un passo indietro e pensare a vari trucchi per fare funzionare le cose più velocemente (la risposta è quasi sempre "utilizzare una tabella hash", raramente "Utilizza un albero", e molto raramente qualcosa di un po 'più complicato).

complessità ammortizzato e caso medio

C'è anche il concetto di "ammortizzato" e / o "caso medio" (si noti che questi sono diversi).

Caso media : Questo non è altro che usare la notazione O-grande per il valore atteso di una funzione, piuttosto che la funzione stessa. Nel caso normale in cui si considerano tutti gli ingressi di essere altrettanto probabile, il caso medio è solo la media del tempo di esecuzione. Ad esempio, con il Quicksort, anche se il caso peggiore è 2 N² per alcuni input davvero male, il caso medio è il solito 3 N² (gli ingressi davvero male sono molto piccoli in numero, così pochi che non li notiamo nel caso medio).

ammortizzato peggior caso : alcune strutture di dati possono avere un caso peggiore complessità che è grande, ma garantisce che se si fa molte di queste operazioni, la quantità media di lavoro che fate sarà migliore che nel caso peggiore. Per esempio si può avere una struttura dati che normalmente richiede tempo 1/2 N² costante. Tuttavia, di tanto in tanto lo farà 'singhiozzo' e prendere 2 N² + log(N) tempo per una sola operazione a caso, perché forse ha bisogno di fare un po 'di contabilità o di garbage collection o qualcosa del genere ... ma ti promette che se lo fa singhiozzo, non sarà singhiozzo ancora per N più operazioni. Il costo nel caso peggiore è ancora - N² + N^1.9 per singola operazione, ma il costo ammortizzato tra le tante piste è = = Ɵ(...) per operazione. Perché le grandi operazioni sono sufficientemente rare, l'enorme quantità di lavoro occasionale può essere considerato per fondersi con il resto del lavoro come fattore costante. Diciamo che il lavoro è "ammortizzato" su un numero sufficientemente ampio di chiamate che scompare asintoticamente.

L'analogia per l'analisi ammortizzato:

Si guida una macchina. Di tanto in tanto, è necessario spendere 10 minuti andando a   il distributore di benzina e poi spendere 1 minuto si riempie il serbatoio di gas.   Se avete fatto questo ogni volta che sei andato da nessuna parte con la vostra auto (spendere 10   minuti di auto alla stazione di benzina, trascorrono alcuni secondi compilando un   frazione di gallone), sarebbe molto inefficiente. Ma se si compila   il serbatoio una volta ogni pochi giorni, i 11 minuti spesi guida al   stazione di gas è "ammortizzato" su un numero sufficientemente grande di viaggi,   che si può ignorare e fingere tutti i vostri viaggi sono stati forse 5% in più.

Confronto tra caso medio e ammortizzati nel caso peggiore:

caso medio: Facciamo alcune ipotesi circa i nostri ingressi; cioè se i nostri ingressi hanno diverse probabilità, allora le nostre uscite / runtime avranno diverse probabilità (che prendiamo la media di). Di solito diamo per scontato che i nostri ingressi sono tutti la stessa probabilità (probabilità uniforme), ma se gli ingressi del mondo reale non si adattano le nostre ipotesi di "input media", la produzione media / calcoli di runtime può essere priva di significato. Se si prevede ingressi uniformemente a caso, però, questo è utile per pensare!
Amortised caso peggiore: se si utilizza una struttura di dati nel caso peggiore ammortizzato, le prestazioni è garantito per essere all'interno del caso peggiore ammortizzato ... alla fine (anche se gli ingressisono scelti da un demone malvagio che sa tutto e sta cercando di vite voi sopra). Di solito usiamo questo per analizzare algoritmi che possono essere molto 'mosso' in termini di prestazioni con grandi singhiozzo inaspettate, ma nel corso del tempo ad effettuare altrettanto bene come altri algoritmi. (Tuttavia a meno che la vostra struttura di dati ha limiti superiori per molto lavoro straordinario è disposto a procrastinare su, un utente malintenzionato potrebbe forse del male ti costringono a recuperare la massima quantità di lavoro procrastinato tutto-at-once.

Anche se, se siete ragionevolmente preoccupati per un attaccante, ci sono molti altri vettori di attacco algoritmico di cui preoccuparsi oltre ammortamenti e caso medio.)

Sia nel caso medio e l'ammortamento sono strumenti incredibilmente utili per pensare e progettare con il ridimensionamento in mente.

(Vedere tra il caso medio e ammortizzati analisi se interessati su questo argomento secondario.)

Multidimensional O-grande

La maggior parte del tempo, le persone non si rendono conto che non c'è più di una variabile al lavoro. Per esempio, in un algoritmo di stringa di ricerca, l'algoritmo potrebbe richiedere tempo Ɵ(exactlyThis), vale a dire che è lineare in due variabili come O(noGreaterThanThis). Altri algoritmi più naive possono essere <=> o <=>. Ignorando più variabili è una delle sviste più comuni che vedo in analisi di algoritmi, e può Handicap durante la progettazione di un algoritmo.

L'intera storia

Tieni presente che O-grande non è tutta la storia. È drasticamente possibile accelerare alcuni algoritmi utilizzando la cache, che li rende cache-ignari, evitando i colli di bottiglia, lavorando con RAM invece di disco, utilizzando la parallelizzazione, o fare il lavoro prima del tempo - queste tecniche sono spesso indipendente della notazione ordine-di-crescita "O-grande", anche se spesso si vedrà il numero di core nella notazione O-grande di algoritmi paralleli.

Anche tenere a mente che a causa di vincoli nascoste del programma, non si potrebbe veramente cura sul comportamento asintotico. Si può lavorare con un numero limitato di valori, ad esempio:

Se stai ordinamento qualcosa come 5 elementi, non si desidera utilizzare il quicksort <=> veloce; si desidera utilizzare insertion sort, che sembra funzionare bene su piccoli ingressi. Queste situazioni viene spesso in algoritmi divide et impera, dove si contempla il problema in sottoproblemi più piccoli, come la fascicolazione ricorsiva, trasformate di Fourier veloce, o la moltiplicazione di matrici.
Se alcuni valori siano effettivamente limitati a causa di qualche fatto nascosto (per esempio il nome umano medio è leggermente limitato a forse 40 lettere, e l'età umana è leggermente limitato a circa 150). Si può anche imporre limiti sul vostro contributo per rendere efficace termini costante.

In pratica, anche tra algoritmi che hanno lo stesso o simile prestazione asintotico, loro merito relativo può effettivamente essere guidato da altre cose, come: altri fattori di prestazioni (quicksort mergesort e sono entrambi <=>, ma quicksort sfrutta cache CPU); considerazioni non prestazioni, come la facilità di attuazione; se una libreria è disponibile, e come reputazione e mantenuto la biblioteca è.

I programmi saranno anche eseguire più lenta su un computer 500MHz vs computer di 2GHz. Noi in realtà non consideriamo questo come parte dei limiti di risorse, perché pensiamo di ridimensionamento in termini di risorse della macchina (ad esempio per ciclo di clock), non al secondo reale. Tuttavia, ci sono cose simili che possono 'segretamente' influire sulle prestazioni, ad esempio se si esegue sotto emulazione, o se il codice compilatore ottimizzato o no. Queste potrebbero effettuare alcune operazioni di base richiedono più tempo (anche rispetto all'altro), o addirittura accelerare o rallentare alcune operazioni asintoticamente (anche relativa ad ogni otheR). L'effetto può essere piccola o grande tra differenti attuazione e / o l'ambiente. Ti passa lingue o macchine per guadagnarsi da quel po 'di lavoro in più? Questo dipende da un centinaio di altre ragioni (necessità, abilità, colleghi, la produttività dei programmatori, il valore monetario del vostro tempo, la familiarità, soluzioni alternative, perché non montaggio o GPU, ecc ...), che può essere più importante delle prestazioni.

Le questioni di cui sopra, come il linguaggio di programmazione, non sono quasi mai considerati come parte del fattore costante (né dovrebbero essere); ma si deve essere consapevoli di loro, perché a volte (anche se raramente) essi possono influenzare le cose. Ad esempio, nel CPython, l'attuazione coda di priorità nativo è asintoticamente non ottimale (<=> piuttosto che <=> per la vostra scelta di inserimento o find-min); si usa un'altra implementazione? Probabilmente no, dal momento che l'implementazione C è probabilmente più veloce, e ci sono probabilmente altri problemi simili altrove. Ci sono dei compromessi; a volte sono importanti e, a volte non lo fanno.

( modifica :. La spiegazione "povere" finisce qui)

Math addenda

Per completezza, la definizione precisa di notazione O-grande è il seguente: <=> significa che "f è asintoticamente superiore delimitata da const * g": ignorando tutto sotto di un certo valore finito di x, esiste una costante tale che <=>. (Gli altri simboli sono i seguenti: proprio come <=> significa ≤, <=> significa ≥ Ci sono varianti minuscole:. <=> mezzi <, e <=> significa>.) <=> significa sia <=> e <=> (superiore e inferiore delimitata da g): esiste alcune costanti tale che f sarà sempre trovarsi nella "banda" tra <=> e <=>. E 'la dichiarazione più forte asintotica è possibile effettuare e meno equivalente a <=>. (Scusate, ho scelto di ritardare la menzione dei simboli assoluti di valore fino ad ora, per amor di chiarezza;. Soprattutto perché non ho mai visto i valori negativi vengono su in un contesto informatica)

La gente userà spesso <=>, che è forse il più corretto la notazione 'comp-sci', e del tutto legittimo da usare; "F = O (...)" viene letto "f è ordine ... / f è xxx-delimitata da ..." ed è pensato come "f è un'espressione asintotica cui sono ...". Mi è stato insegnato ad usare il <=> più rigorosa. <=> significa "è un elemento di" (ancora leggere come prima). <=> è in realtà un equivalenza classe , cioè, è un insieme di cose che riteniamo essere la stessa. In questo caso particolare, <=> contiene elementi come {<=>, <=>, <=>, <=>, <=>, ...} ed è infinitamente grande, ma è ancora un set. Il <=> notazione potrebbe essere quello più comune, ed è anche utilizzato in saggi di esperti informatici di fama mondiale. Inoltre, è spesso il caso che in un ambiente informale, la gente dirà <=> quando significano <=>; questo è tecnicamente vero dal momento che l'insieme delle cose <=> è un sottoinsieme di <=> ... ed è più facile da digitare. ; -)

EDIT: Nota veloce, questo è quasi certamente confusa notazione O-grande (che è un superiore bound) con Theta notazione (che è sia un limite superiore e limite inferiore). Nella mia esperienza questo è in realtà tipico delle discussioni in ambienti non accademici. Ci scusiamo per la confusione causati.

In una frase:? Come la dimensione del vostro lavoro aumenta, quanto tempo ci vuole per completarlo

Ovviamente questo è solo l'utilizzo di "taglia" come ingresso e "tempo impiegato" come uscita -. La stessa idea si applica se si vuole parlare di utilizzo della memoria etc

Ecco un esempio in cui abbiamo N magliette che vogliamo ad asciugare. Ci assumiamo E 'incredibilmente veloce per farli nella posizione di asciugatura (vale a dire l'interazione umana è trascurabile). Questo non è il caso nella vita reale, ovviamente ...

Uso di una linea di lavaggio esterno: ammesso che abbiate un infinitamente grande cortile, il lavaggio si asciuga in O (1) tempo. Per quanto si ha di esso, otterrà lo stesso sole e l'aria fresca, quindi la dimensione non influenza il tempo di asciugatura.
Utilizzando un asciugabiancheria: si mette 10 camicie in ogni carico, e poi si è fatto un'ora più tardi. (Ignorare i numeri reali qui -. Sono irrilevanti). Così asciugatura 50 camicie prende su 5 volte più a lungo di essiccazione 10 camicie
Mettere tutto in un armadio in onda: Se mettiamo tutto in un grande mucchio e lasciare che il calore in generale farlo, ci vorrà molto tempo per le camicie di mezzo per arrivare a secco. Non vorrei indovinare dettaglio, ma ho il sospetto questo è almeno O (N ^ 2) -. Come si aumenta il carico di lavaggio, il tempo di asciugatura aumenta più velocemente

Un aspetto importante della notazione "O grande" è che non dire che l'algoritmo sarà più veloce per una data dimensione. Prendere una tabella hash (string key, valore intero) contro una matrice di coppie (stringa, intero). E 'più veloce per trovare una chiave nella tabella hash o un elemento della matrice, sulla base di una stringa? (Vale a dire per l'array, "trovare il primo elemento in cui la parte di stringa corrisponde alla chiave data.") Hashtables sono generalmente ammortizzati (~ = "in media") O (1) - una volta che sono istituiti, che dovrebbe prendere circa allo stesso tempo per trovare una voce in una tabella 100 di entrata come in una tabella di 1.000.000 di entrata. Trovare un elemento di un array (in base al contenuto, piuttosto che indice) è lineare, cioè O (N) -. In media, si sta andando ad avere a guardare la metà delle voci

Questo rende una tabella hash più veloce di una matrice per le ricerche? Non necessariamente. Se hai una piccola raccolta di voci, una matrice potrebbe essere più veloce - si può essere in grado di controllare tutte le stringhe nel tempo che ci vuole per calcolare solo il codice hash di quello che stai guardando. Come set di dati diventa più grande, tuttavia, la tabella hash finirà per battere la matrice.

Big O descrive un limite superiore sul comportamento di crescita di una funzione, ad esempio l'esecuzione di un programma, quando gli ingressi diventano grandi.

Esempi:

O (n): Se ho il doppio della dimensione di input raddoppia runtime
O (n ²): Se la dimensione di input raddoppia il runtime quadruplica
O (log n): Se la dimensione di input raddoppia gli aumenti di runtime da uno
O (2 ⁿ): Se le dimensioni di ingresso aumenta di uno, il doppio runtime

Il formato di ingresso è di solito lo spazio in bit necessari per rappresentare l'ingresso.

o-grande è più comunemente usato dai programmatori come misura approssimativa di quanto tempo un calcolo (algoritmo) necessario per completare espresso in funzione della dimensione del set di input.

Big O è utile confrontare quanto bene due algoritmi scalare come si aumenta il numero di ingressi.

notazione O-grande viene utilizzato per esprimere il comportamento asintotico di una funzione. Ciò significa che come la funzione si comporta come si tende all'infinito.

In molti casi la "O" di un algoritmo cadrà in uno dei seguenti casi:

O (1) - Il tempo per completare è lo stesso, indipendentemente dalle dimensioni del set di input. Un esempio accede a un array tramite indice.
O (log N) - tempo per completare gli aumenti più o meno in linea con il log2 (n). Per esempio 1024 articoli vogliono circa il doppio del tempo a 32 elementi, perché log2 (1024) = 10 e log2 (32) = 5. Un esempio è trovare un elemento in una binario di ricerca albero (BST).
O (N) - tempo per completare in grado di scalare linearmente con la dimensione del set di input. In altre parole, se si raddoppia il numero di elementi nel set di input, l'algoritmo richiede circa il doppio del tempo. Un esempio conta il numero di elementi in una lista collegata.
O (N log N) - tempo per completare gli aumenti per il numero di articoli volte il risultato di log2 (N). Un esempio di questo è mucchio sorta e rapida sorta .
O (N ^ 2) - Il tempo per completare è approssimativamente uguale al quadrato del numero di elementi. Un esempio di questo è sorta .
O (N!) - Il tempo per completare il fattoriale del set di input. Un esempio di questo è il problema del commesso viaggiatore soluzione di forza bruta .

Big O ignora fattori che non contribuiscono in modo significativo alla curva di crescita di una funzione come la dimensione di ingresso aumenta verso l'infinito. Ciò significa che le costanti che vengono aggiunti o moltiplicato per la funzione vengono semplicemente ignorati.

Big O è solo un modo per "esprimere" se stessi in un modo comune, "Quanto tempo / spazio è necessario per eseguire il mio codice?".

È possibile vedono spesso O (n), O (n ²), O (nlogn) e così via, tutte queste sono solo modi per mostrare; Come funziona un cambiamento algoritmo?

O (n) significa Big O è n, e ora si potrebbe pensare, "Che cosa è n !?" Bene "n" è la quantità di elementi. Imaging si desidera cercare un elemento in un array. Si dovrebbe guardare su ogni elemento e come "Sei l'elemento / articolo corretto?" nel peggiore dei casi, l'elemento è l'ultimo indice, il che significa che ci sono voluti tutto il tempo che ci sono elementi nella lista, in modo da essere generico, diciamo "Oh, hey, n è una fiera data quantità di valori!" .

Quindi, allora si potrebbe capire che cosa "n ²" si intende, ma per essere ancora più specifico, giocare con il pensiero si dispone di un semplice, il più semplice degli algoritmi di ordinamento; bubblesort. Questo algoritmo ha bisogno di guardare attraverso l'intera lista, per ogni voce.

Il mio

Il flusso qui sarebbe:

Confronto 1 e 6, che è più grande? Ok 6 è nella posizione giusta, andare avanti!
Confronto 6 e 3, oh, 3 è di meno! Passiamo che, Ok la lista cambiato, dobbiamo cominciare fin dall'inizio ora!

Questo è O n ² in quanto, è necessario guardare a tutti gli elementi nella lista ci sono elementi "n". Per ogni elemento, si guarda a tutte le voci una volta di più, per il confronto, questo è anche "n", quindi per ogni elemento, si guarda "n" volte che significa n * n = n ²

Spero che questo è così semplice come si desidera.

Ma ricordate, Big O è solo un modo per experss te stesso nel modo di tempo e spazio.

Big O descrive la natura fondamentale di scala di un algoritmo.

Ci sono un sacco di informazioni che Big O non ti dice su un determinato algoritmo. Taglia fino all'osso e dà solo informazioni sulla natura ridimensionamento di un algoritmo, in particolare come l'uso delle risorse (si pensi tempo o di memoria) di un algoritmo scale in risposta al "formato di input".

Si consideri la differenza tra un motore a vapore e un razzo. Essi non sono solo diverse varietà della stessa cosa (come, ad esempio, un motore di Prius contro un motore Lamborghini), ma sono drammaticamente diversi tipi di sistemi di propulsione, nella loro essenza. Un motore a vapore può essere più veloce di un razzo giocattolo, ma nessun motore a pistoni a vapore sarà in grado di raggiungere le velocità di un veicolo di lancio orbitale. Questo è perché questi sistemi hanno differenti caratteristiche di scala per quanto riguarda il rapporto di combustibile richiesto ( "utilizzo delle risorse") per raggiungere una determinata velocità ( "size input").

Perché è così importante? A causa offerte di software con problemi che possono differire in dimensioni da fattori fino ad un trilioni di. Si consideri che per un momento. Il rapporto tra la velocità necessaria per viaggiare verso la Luna e la velocità di deambulazione umana è inferiore a 10.000: 1, e che è assolutamente minuscolo rispetto alla gamma di ingresso in dimensioni software può affrontare. E perché il software può affrontare una gamma astronomico di ingresso dimensioni v'è la possibilità per la complessità Big O di un algoritmo, è fondamentale la natura di scala, a briscola eventuali dettagli di implementazione.

Si consideri l'esempio di ordinamento canonico. Bubble-sort è O (n ²), mentre merge-sort è O (n log n). Diciamo che sono presenti due applicazioni di ordinamento, l'applicazione che utilizza A bubble-ordinamento e applicazione B che utilizza merge-sort, e diciamo che per le dimensioni di ingresso di circa 30 elementi di applicazione A è 1,000x più veloce di applicazione B a l'ordinamento. Se non hai mai sorta molto di più di 30 elementi, allora è ovvio che si dovrebbe preferisce applicazione A, in quanto è molto più veloce in queste dimensioni di input. Tuttavia, se si scopre che potrebbe essere necessario ordinare dieci milioni di voci, allora quello che ci si aspetta è che l'applicazione B in realtà finisce per essere migliaia di volte più veloce di applicazione A in questo caso, interamente dovuto al modo in cui ciascuno scale algoritmo.

Ecco il semplice bestiario inglese che tendo a usare quando spiego le varietà comuni di Big-O

In tutti i casi, preferisci gli algoritmi più in alto nell'elenco a quelli più in basso nell'elenco.Tuttavia, il costo del passaggio a una classe di complessità più costosa varia in modo significativo.

O(1):

Nessuna crescita.Non importa quanto sia grande il problema, puoi risolverlo nello stesso lasso di tempo.Ciò è in qualche modo analogo alla trasmissione in cui è necessaria la stessa quantità di energia per trasmettere su una determinata distanza, indipendentemente dal numero di persone che si trovano all'interno del raggio di trasmissione.

O(log N):

Questa complessità è la stessa di O(1) tranne che è solo un po' peggio.A tutti gli effetti pratici, puoi considerarlo come un ridimensionamento costante molto ampio.La differenza di lavoro tra l'elaborazione di 1.000 e 1 miliardo di articoli è solo un sesto fattore.

O(N):

Il costo per risolvere il problema è proporzionale alla dimensione del problema.Se il tuo problema raddoppia di dimensioni, anche il costo della soluzione raddoppia.Poiché la maggior parte dei problemi devono essere scansionati nel computer in qualche modo, come l'immissione di dati, le letture del disco o il traffico di rete, questo è generalmente un fattore di scala conveniente.

O(N tronco d'albero N):

Questa complessità è molto simile a O(N).Per tutti gli scopi pratici, i due sono equivalenti.Questo livello di complessità sarebbe generalmente ancora considerato scalabile.Modificando alcune ipotesi O(N tronco d'albero N) gli algoritmi possono essere trasformati in O(N) algoritmi.Ad esempio, limitare la dimensione delle chiavi riduce l'ordinamento da O(N tronco d'albero N) A O(N).

O(N²):

Cresce come un quadrato, dove N è la lunghezza del lato di un quadrato.Questo è lo stesso tasso di crescita dell '"effetto rete", dove tutti in una rete potrebbero conoscere tutti gli altri nella rete.La crescita è costosa.La maggior parte delle soluzioni scalabili non possono utilizzare algoritmi con questo livello di complessità senza fare ginnastica significativa.Questo generalmente si applica a tutte le altre complessità polinomiali: O(N^K) - anche.

O(2^N):

Non scala.Non hai speranza di risolvere alcun problema di dimensioni non banali.Utile per sapere cosa evitare e per gli esperti per trovare algoritmi approssimativi adatti O(N^K).

Big O è una misura di quanto tempo / spazio un algoritmo utilizza rispetto alle dimensioni del suo ingresso.

Se un algoritmo è O (n) allora il tempo / spazio aumenterà alla stessa velocità come input.

Se un algoritmo è O (n ²) allora il tempo / aumentare lo spazio al tasso del suo ingresso quadrato.

e così via.

E 'molto difficile per misurare la velocità di programmi software, e quando cerchiamo, le risposte possono essere molto complessa e piena di eccezioni e casi particolari. Questo è un grosso problema, perché tutte quelle eccezioni e casi particolari sono fonte di distrazione e scostante quando vogliamo confrontare due programmi diversi tra loro per scoprire che è "più veloce".

Come risultato di tutta questa complessità inutile, la gente cerca di descrivere la velocità di programmi software utilizzando le espressioni più piccole e meno complesse (matematici) possibile. Queste espressioni sono approssimazioni molto grossolane. Anche se, con un po 'di fortuna, che cattureranno l' "essenza" di se un pezzo di software è veloce o lento

Perché sono approssimazioni, usiamo la lettera "O" (Big Oh) nell'espressione, come una convenzione per segnalare al lettore che stiamo facendo una grossolana. (E per assicurarsi che nessuno pensa erroneamente che l'espressione è in alcun modo preciso).

Se leggete il "Oh" nel senso "dell'ordine di" o "approssimativamente" voi non andare troppo lontano sbagliato. (Penso che la scelta del Big-Oh potrebbe essere stato un tentativo di umorismo).

L'unica cosa che queste espressioni "-Oh Big" cercano di fare è quello di descrivere quanto il software rallenta mentre aumentiamo la quantità di dati che il software deve processare. Se raddoppiamo la quantità di dati che devono essere elaborati, non il software è necessario il doppio del tempo per finire è un lavoro? Dieci volte più a lungo? In pratica, ci sono un numero molto limitato di grandi-Oh espressioni che si incontrano e hanno bisogno di preoccuparsi:

La buona:

O(1) Costante :. Il programma impiega lo stesso tempo per l'esecuzione non importa quanto grande l'ingresso è
O(log n) logaritmico :. Run-time Il programma aumenta solo lentamente, anche con grandi aumenti nella dimensione dell'input

La cattiva:

O(n) lineare :. Run-time Il programma aumenta proporzionalmente alla dimensione dell'input
O(n^k) polinomiale : -. Tempo di lavorazione cresce sempre più veloce - come funzione polinomiale - come la dimensione degli aumenti di ingresso

... e il brutto:

O(k^n) esponenziale Il programma runtime aumenta molto rapidamente anche con moderati aumenti nella dimensione del problema -. È solo pratico per elaborare insiemi di dati di piccole dimensioni con algoritmi esponenziali
O(n!) fattoriale Il programma run-time sarà più lungo di quello che può permettersi di aspettare nulla, ma i set di dati molto più piccole e banali apparentemente.

Che cosa è un semplice spiegazione inglese di Big O? Con il poco definizione formale possibile e semplice matematica.

Una spiegazione Plain English del Bisogno per la notazione O-grande:

Quando si programma, stiamo cercando di risolvere un problema. Quello che il codice si chiama un algoritmo. Notazione O-grande ci permette di confrontare il caso peggiore performance dei nostri algoritmi in modo standardizzato. specifiche hardware variano nel tempo e miglioramenti in hardware può ridurre il tempo necessario per eseguire un algoritmo. Ma sostituire l'hardware non significa che il nostro algoritmo è migliore o migliorata nel tempo, come il nostro algoritmo è sempre la stessa. Quindi, al fine di permetterci di confrontare diversi algoritmi, per determinare se uno è meglio o no, usiamo notazione O-grande.

Una spiegazione Plain English di Cosa notazione O-grande è:

Non tutti gli algoritmi eseguiti nello stesso lasso di tempo, e possono variare in base al numero di elementi in ingresso, che chiameremo n . Sulla base di questo, consideriamo l'analisi del caso peggiore, o un limite superiore del run-time come n si fanno più grandi e più grande. Dobbiamo essere consapevoli di ciò che n è, perché molte delle notazioni Big O fare riferimento a esso.

Una semplice risposta diretta può essere:

Big O rappresenta il peggior tempo / spazio possibile per tale algoritmo. L'algoritmo non prenderà mai più spazio / tempo sopra di tale limite. Big O rappresenta il tempo / spazio complessità nel caso estremo.

Ok, i miei 2Cents.

Big-O, è tasso di aumento di risorsa consumata da programma, w.r.t. problema-esempio-size

Resource: Potrebbe essere il tempo totale della CPU, potrebbe essere il massimo spazio di RAM. Di default si riferisce al tempo di CPU.

dicono che il problema è "Trova la somma",

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problema istanza = {5,10,15} ==> problema-instance-size = 3, iterazioni-in-loop = 3

problema istanza = {5,10,15,20,25} ==> problemi esempio size = 5 iterazioni-in-loop = 5

Per input di dimensione "n" il programma sta crescendo a velocità di "n" iterazioni a matrice. Quindi O-grande è N espresso come O (n)

dicono che il problema è "trovare la combinazione",

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problema istanza = {5,10,15} ==> problema-instance-size = 3, totale iterazioni-= 3 * 3 = 9

problema istanza = {5,10,15,20,25} ==> problema-instance-size = 5, in totale iterazioni-= 5 * 5 = 25

Per input di dimensione "n" il programma sta crescendo a velocità di "n * n" iterazioni a matrice. Quindi O-grande è N ² espresso in O (n ²)

notazione O-grande è un modo di descrivere il limite superiore di un algoritmo in termini di spazio o di tempo di esecuzione. Il n è il numero di elementi nel problema (cioè dimensione di una matrice, numero di nodi in un albero, ecc) Siamo interessati a descrivere il tempo di esecuzione come n diventa grande.

Quando diciamo qualche algoritmo è O (f (n)) stiamo dicendo che il tempo di esecuzione (o lo spazio necessario) da tale algoritmo è sempre inferiore a volte costante f (n).

Per dire che la ricerca binaria ha un tempo di esecuzione di O (log n) è come dire che esiste un certo c costante che si può moltiplicare log (n) di che sarà sempre più grande rispetto al tempo di calcolo della ricerca binaria. In questo caso si avrà sempre qualche fattore costante di log (n) confronti.

In altre parole, dove g (n) è il tempo di esecuzione del vostro algoritmo, diciamo che g (n) = O (f (n)), quando g (n) <= c * f (n) quando n> k, dove c e k sono alcune costanti.

" Che cosa è un semplice spiegazione inglese di Big O? Con il meno formale Definizione possibile e semplice matematica. "

Una tale domanda meravigliosamente semplice e breve sembra, almeno per meritare una risposta altrettanto breve, come uno studente potrebbe ricevere durante il tutoraggio.

notazione O-grande dice semplicemente quanto tempo * un algoritmo può essere eseguito all'interno, in termini di solo la quantità di dati di ingresso **.

(* in un meraviglioso, senza unità senso del tempo!)
(** che è ciò che conta, perché la gente sempre vogliono più , se vivono oggi o domani)

Bene, cosa c'è di così meravigliosa di notazione O-grande, se questo è quello che fa?

In pratica, Big analisi O è così utile e importante , perché Big O pone l'accento angolo retto sul proprio la complessità dell'algoritmo e completamente ignora tutto ciò che è semplicemente una costante di proporzionalità, come un motore JavaScript, la velocità di una CPU, la connessione a Internet, e tutte quelle cose che diventano rapidamente diventano come ridicolmente obsoleto come un modello di T . Big O si concentra sulle prestazioni solo nel modo che conta altrettanto molto per le persone che vivono nel presente o nel futuro.
notazione O-grande brilla anche un riflettore direttamente sul principio più importante della programmazione informatica / ingegneria, il fatto che ispira tutti i buoni programmatori di continuare a pensare e sognare: l'unico modo per ottenere risultati al di là della lenta marcia in avanti della la tecnologia è quello di inventare un algoritmo migliore .

Esempio di algoritmo (Java):

// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

Descrizione dell'algoritmo:

Questo algoritmo ricerca un elenco, elemento per elemento, alla ricerca di una chiave,
Iterando su ciascun elemento dell'elenco, se è la chiave, restituisce True,
Se il ciclo è terminato senza trovare la chiave, restituisce False.

La notazione Big-O rappresenta il limite superiore della complessità (tempo, spazio, ..)

Per trovare il Big-O sulla complessità temporale:

Calcola quanto tempo (per quanto riguarda la dimensione dell'input) impiega il caso peggiore:
Caso peggiore:la chiave non esiste nell'elenco.
Tempo (caso peggiore) = 4n+1
Tempo:O (4n+1) = O (n) | In Big-O, le costanti vengono trascurate
O(n) ~ Lineare

C'è anche Big-Omega, che rappresenta la complessità del Best-Case:

Caso migliore:la chiave è il primo elemento.
Tempo (caso migliore) = 4
Tempo:Ω(4) = O(1) ~ Istantaneo\Costante

Big O

f (x) = O ( g (x)) quando x va ad un (per esempio, a = + ∞) significa che v'è una funzione < em> k tale che:

f (x) = k (x) g (x)
k è delimitata in qualche quartiere di una (se a = + ∞, questo significa che ci sono numeri N ed M tale che per ogni x> N, | k (x) |

In altre parole, in parole povere: f (x) = O ( g (x)), x → una, significa che in un quartiere di una, f scompone nel prodotto di g e qualche funzione limitata.

Piccolo o

A proposito, qui è per il confronto la definizione di piccola o.

f (x) = o ( g (x)) quando x va ad un mezzo che vi sia una funzione k tale che:

f (x) = k (x) g (x)
k (x) va a 0 quando x va ad un.

Esempi

sin x = O (x) quando x → 0.
sin x = O (1), quando x → + ∞,
x ² + x = O (x) quando x → 0,
x ² + x = O (x ²), quando x → + ∞,
ln (x) = o (x) = O (x) quando x → + ∞.

Attenzione La notazione con il segno di uguale "=" utilizza una "uguaglianza falso!": È vero che O (g (x)) = O (g (x)), ma falsa che O (g (x)) = O (g (x)). Allo stesso modo, è ok per scrivere "ln (x) = O (x) quando x → + ∞", ma la formula "o (x) = ln (x)" non avrebbe senso.

Altri esempi

O (1) = O (n) = O (n ²) quando n → + ∞ (ma non il contrario, l'uguaglianza è "falso"),
O (n) + O (n ²) = O (n ²) quando n → + ∞
O (O (n ²)) = O (n ²) quando n → + ∞
O (n ²) O (n ³) = O (n ⁵) quando n → + ∞

Ecco l'articolo di Wikipedia: https://en.wikipedia.org/wiki/Big_O_notation

notazione O-grande è un modo di descrivere quanto velocemente un algoritmo verrà eseguito dato un numero arbitrario di parametri di input, che chiameremo "n". E 'utile in informatica, perché diverse macchine funzionano a velocità diverse, e semplicemente dicendo che un algoritmo prende 5 secondi non dirà molto, perché mentre si può essere in esecuzione un sistema con un processore octo-core 4.5 Ghz, mi potrebbe essere in esecuzione un 15enne, sistema a 800 MHz, che potrebbe richiedere più tempo a prescindere dell'algoritmo. Così, invece di specificare quanto velocemente un algoritmo viene eseguito in termini di tempo, diciamo la velocità con cui viene eseguito in termini di numero di parametri di input, o "n". Descrivendo algoritmi in questo modo, siamo in grado di confrontare le velocità di algoritmi senza dover tener conto della velocità del computer stesso.

Non sono sicuro che sto contribuendo ulteriormente l'argomento, ma ancora ho pensato di condividere: una volta ho trovato questo post del blog di avere alcuni molto utili (anche se molto di base) spiegazioni ed esempi su Big O:

Via esempi, questo ha aiutato avere le basi nude nel mio cranio tartaruga-come, così penso che sia una bella discesa 10 minuti a leggere per farti andando nella giusta direzione.

Volete sapere tutto quello che c'è da sapere su O grande? Anch'io.

Quindi, per parlare di grande O, userò parole che hanno solo un battito in loro. Un suono per parola. Le piccole parole sono veloci. Sai queste parole, e anche a me Useremo le parole con un suono. Sono piccoli. Sono sicuro si sa tutte le parole che useremo!

Ora, cerchiamo di te e me parlare di lavoro. Il più delle volte, non mi piace il lavoro. Ti piace il lavoro? Può essere il caso che si fa, ma sono sicuro che non lo faccio.

Non mi piace andare al lavoro. Non mi piace trascorrere del tempo sul posto di lavoro. Se fosse per me, vorrei solo giocare e fare cose divertenti. Ti senti lo stesso che faccio io?

Ora, a volte, devo andare al lavoro. E 'triste ma vero. Così, quando sono al lavoro, ho una regola: cerco di fare meno lavoro. Il più vicino a nessun lavoro come posso. Poi ho andare a giocare!

Quindi, ecco la grande novità: il grande O mi può aiutare a non fare il lavoro! Posso giocare più delle volte, se conosco grande O. Meno lavoro, più giocare! Questo è ciò che grande O mi aiuta a fare.

Ora ho un po 'di lavoro. Ho questa lista: uno, due, tre, quattro, cinque, sei. Devo aggiungere tutte le cose in questo elenco.

Wow, io odio il lavoro. Ma vabbè, io devo fare questo. Così qui vado.

Uno più due fa tre ... più tre è di sei ... e quattro è ... non lo so. Mi sono perso. E 'troppo difficile per me fare nella mia testa. Io non molta cura per questo tipo di lavoro.

Quindi cerchiamo di non fare il lavoro. Diamo voi e mi basta pensare quanto sia difficile. Quanto lavoro che avrei dovuto fare, per aggiungere sei numeri?

Bene, vediamo. Devo aggiungere uno e due, e poi aggiungere che a tre, e quindi aggiungere che a quattro ... Tutto sommato, io conto sei aggiunge. Devo fare sei aggiunge per risolvere questo.

Ecco che arriva grande O, per dirci quanto sia difficile questa matematica è.

Big O dice: dobbiamo fare sei aggiunge per risolvere questo. Uno aggiungere, per ogni cosa da uno a sei. Sei piccoli pezzi di lavoro ... ogni bit di lavoro è un add.

Beh, non voglio fare il lavoro per aggiungerli ora. Ma io so quanto sia difficile sarebbe. Sarebbe sei aggiunge.

Oh no, ora ho più lavoro. Sheesh. Chi fa questo genere di cose?!

Ora mi chiedono di aggiungere da uno a dieci! Perchè dovrei farlo? Non volevo aggiungere uno a sei. Per aggiungere da uno a dieci ... beh ... che sarebbe ancora più difficile!

Quanto più difficile sarebbe? Quanto più il lavoro che avrei dovuto fare? Ho bisogno di passi più o meno?

Beh, credo che avrei dovuto fare dieci aggiunge ... uno per ogni cosa da uno a dieci. Dieci è più di sei. Avrei dovuto lavorare molto altro da aggiungere da uno a dieci, di 1-6!

Non voglio aggiungere in questo momento. Voglio solo pensare a quanto sia difficile potrebbe essere quella di aggiungere più di tanto. E, spero, a giocare il più presto possibile.

Per aggiungere da uno a sei, che è un po 'di lavoro. Ma vedete, da aggiungere da uno a dieci, che è più lavoro?

Big O è tuo amico e la mia. Big O ci aiuta a pensare su quanto lavoro dobbiamo fare, in modo che possiamo pianificare. E, se siamo amici con grande O, può aiutarci a scegliere il lavoro che non è così difficile!

Ora dobbiamo fare un nuovo lavoro. Oh, no. Non mi piace questa cosa lavoro a tutti.

Il nuovo lavoro è: aggiungere tutte le cose da uno a n

Aspetta! Che cosa è n? Mi sono perso questo? Come posso aggiungere da uno a n se non mi dici cosa è n?

Beh, io non so che cosa è n. Non mi avevano detto. Eri tu? No? Oh bene. Quindi non siamo in grado di fare il lavoro. Accidenti.

Ma se noi non faremo il lavoro ora, possiamo immaginare quanto sia difficile sarebbe, se sapevamo n. Dovremmo aggiungere n cose, giusto? Certo!

Ora ecco che arriva O grande, e lui ci dirà quanto sia difficile questo lavoro è. Egli dice: per aggiungere tutte le cose da uno a N, uno per uno, è O (n). Per aggiungere tutte queste cose, [so che devo aggiungere n volte.] [1] Questo è il grande O! Egli ci dice quanto sia difficile fare un certo tipo di lavoro.

Per me, penso a O grande come una grande, lenta, capo uomo. Pensa sul lavoro, ma non lo fa. Si potrebbe dire, "Tlavoro cappello è veloce." O, si potrebbe dire, 'che il lavoro è così lento e duro!' Ma lui non fa il lavoro. Ha appena guarda il lavoro, e poi ci dice quanto tempo potrebbe prendere.

Mi interessa un sacco di grandi O. Perché? Non mi piace lavorare! A nessuno piace lavorare. È per questo che noi tutti amiamo O grande! Egli ci dice quanto velocemente possiamo lavorare. Egli ci aiuta a pensare a come il lavoro duro è.

Uh oh, più lavoro. Ora, cerchiamo di non fare il lavoro. Ma, facciamo un piano per farlo, passo dopo passo.

Ci hanno dato un mazzo di dieci carte. Sono tutti mescolati: sette, quattro, due, sei ... non diritto a tutti. E ora ... il nostro compito è quello di ordinare loro.

ergh. Che suona come un sacco di lavoro!

Come possiamo risolvere questo ponte? Ho un piano.

guarderò ogni coppia di carte, coppia per coppia, attraverso il ponte, dal primo all'ultimo. Se la prima carta in una coppia è grande e la prossima carta in quella coppia è piccolo, io li swap. Altrimenti, vado alla coppia successiva, e così via e così via ... e presto, il ponte è fatto.

Quando il ponte è fatto, mi chiedo: ho scambiare le schede in che passano? Se è così, devo fare tutto ancora una volta, dalla parte superiore.

Ad un certo punto, a un certo momento, non ci saranno swap, e la nostra specie di ponte sarebbe fatto. Così tanto lavoro!

Bene, quanto lavoro si tratterebbe, per ordinare le carte con tali norme?

Ho dieci carte. E, la maggior parte del tempo - che è, se non ho un sacco di fortuna -. Devo passare attraverso l'intero ponte fino a dieci volte, con un massimo di dieci swap carta ogni volta attraverso il ponte

Big O, aiutami!

Big O entra e dice:. Per un mazzo di carte n, per ordinare in questo modo sarà fatto in O (N al quadrato) tempo

Perché dice n quadrato?

Be ', sai n Squared è n volte n. Ora, ho capito: n carte controllato, fino a quello che potrebbe essere n volte attraverso il ponte. Cioè due anelli, ciascuno con n passi. Che molto lavoro è n squadrato da fare. Un sacco di lavoro, di sicuro!

Ora, quando grande O dice che ci vorrà O (n al quadrato) di lavoro, egli non intende n quadrato aggiunge, sul naso. Potrebbe essere un certo piccolo po 'meno, per alcuni casi. Ma nel caso peggiore, sarà vicino al quadrato n fasi di lavoro per ordinare il ponte.

Ora qui è dove grande O è nostro amico.

Big O sottolinea questo: come n diventa grande, quando ordiniamo le carte, il lavoro diventa molto molto più dura che il vecchio-queste cose solo-add-lavoro. Come facciamo a sapere questo?

Bene, se n ottiene vero e proprio grande, non ci importa quello che potremmo aggiungere al n o n quadrato.

Per la grande n, n al quadrato è più grande di n.

Big O ci dice che per sistemare le cose è più difficile di aggiungere le cose. O (n al quadrato) è superiore a O (n) per grande n. Ciò significa che:. Se n diventa vero e proprio grande, per ordinare un mazzo misto di n cose devono prendere più tempo, di aggiungere solo n cose misti

Big O non risolve il lavoro per noi. Big O ci dice quanto sia difficile il lavoro è.

Ho un mazzo di carte. Ho fatto ordinarli. Hai aiutato. Grazie.

C'è un modo più veloce per ordinare le carte? Può grande O aiutarci?

Sì, c'è un modo più veloce! Ci vuole del tempo per imparare, ma funziona ... e funziona abbastanza veloce. Si può provare troppo, ma ha tutto il tempo ad ogni passo e non perdere il posto.

In questo nuovo modo per ordinare un mazzo, noi non controlliamo le coppie di carte come abbiamo fatto qualche tempo fa. Ecco le nuove regole per ordinare questo mazzo:

Uno: scelgo una carta nella parte del ponte lavoriamo su ora. È possibile scegliere uno per me, se volete. (La prima volta che lo facciamo “la parte del ponte lavoriamo su ora” è tutto il ponte, ovviamente.)

Due: ho splay il ponte su quella carta si è scelto. Che cosa è questo splay; come faccio a Splay? Beh, io vado dalla scheda dall'inizio verso il basso, uno per uno, e non vedo per una carta che è più elevata rispetto alla carta splay.

Tre: vado dalla scheda finiscono, e non vedo per una carta che è più bassa rispetto alla carta splay.

Una volta ho trovato queste due carte, li ho swap, e andare a cercare i più carte da scambiare.Cioè, torno alla fase due, e strombatura sulla carta si è scelto un po 'di più.

A un certo punto, questo ciclo (da due a tre) finirà. Finisce quando entrambe le metà di questa ricerca si incontrano alla carta splay. Poi, abbiamo appena strombato ponte con la carta scelto nel passaggio One. Ora, tutte le carte vicino l'inizio sono più bassi rispetto alla carta splay; e le carte vicino alla fine sono più alte rispetto alla carta splay. Freddo trucco!

Quattro (e questa è la parte divertente): Ho due piccoli ponti Ora, uno più in basso rispetto alla carta splay, e un altro alto. Ora vado a passo uno, su ogni piccolo ponte! Vale a dire, comincio dal punto uno al primo piccolo ponte, e quando questo lavoro è fatto, comincio dal punto uno al successivo piccolo ponte.

I rompere il ponte in parti, e ordinare ogni parte, più piccola e più piccola, e ad un certo momento non ho più lavoro da fare. Ora questo può sembrare lento, con tutte le regole. Ma credetemi, non è lento a tutti. E 'molto meno lavoro di quanto il primo modo per sistemare le cose!

Che cosa è questo tipo chiamato? Si chiama rapido Ordina! Questo genere è stata fatta da un uomo chiamato C. A. R. Hoare e lo chiamò rapida Sort. Ora, Quick Sort viene utilizzato tutto il tempo!

Breve Ordina rompe grandi ponti in quelle di piccole dimensioni. Vale a dire, si rompe grandi compiti in quelle piccole.

Hmmm. Ci può essere una regola in là, credo. Per fare grandi compiti piccoli, li rompere.

Questa specie è abbastanza veloce. Come veloce? Big O ci dice: questo tipo ha bisogno di O (n log n) lavoro da fare, nel caso media.

E 'più o meno veloce rispetto alla prima specie? Big O, per favore aiutatemi!

Il primo tipo è O (n al quadrato). Ma rapida Sort è O (n log n). Voi sapete che n log n è minore di n al quadrato, per grande n, giusto? Beh, questo è il modo in cui sappiamo che Quick Sort è veloce!

Se si deve ordinare un mazzo, qual è il modo migliore? Beh, si può fare quello che vuoi, ma avrei scelto rapido Ordina.

Perché scelgo rapido Ordina? Non mi piace lavorare, naturalmente! Voglio il lavoro fatto, non appena posso farlo fare.

Come faccio a sapere rapida Sort è meno lavoro? So che O (n log n) è inferiore a O (n al quadrato). Il O sono più piccoli, in modo rapido Sort è meno lavoro!

Ora sapete il mio amico, Big O. Egli ci aiuta a fare meno lavoro. E se si sa grande O, si può fare meno lavoro troppo!

Hai imparato tutto quello che con me! Sei così intelligente! Grazie mille!

Ora che il lavoro è fatto, andiamo a giocare!

[1]: C'è un modo per ingannare e aggiungere tutte le cose da uno a n, tutto in una volta. Alcuni ragazzo di nome Gauss trovato questo fuori quando aveva otto anni. Io non sono così intelligente, però, così non chiedetemi come lo ha fatto .

Supponiamo che stiamo parlando di un algoritmo di A , che dovrebbe fare qualcosa con un set di dati di dimensioni n .

Poi O( <some expression X involving n> ) mezzi, in inglese semplice:

Se siete sfortunati durante l'esecuzione A, si potrebbe prendere (n) operazioni X per completa.

Si dà il caso, ci sono alcune funzioni (si pensi a loro come implementazioni di X (n) ) che tendono a verificarsi molto spesso. Questi sono ben noti e facilmente rispetto (Esempi: 1, Log N, N, N^2, N!, ecc ..)

Confrontando questi quando si parla di A e altri algoritmi, è facile per classificare gli algoritmi in base al numero di operazioni che possono (caso peggiore) richiedono di completare.

In generale, il nostro obiettivo sarà quello di trovare o di strutturare un algoritmo A in modo tale che avrà una funzione che restituisce X(n) partire un numero il più possibile.

Non ho modo più semplice per capire la complessità temporale egli metrica più comune per il calcolo del tempo la complessità è o-grande. Questo rimuove tutti i fattori costanti in modo che il tempo di esecuzione può essere stimata in relazione alle N come N tende all'infinito. In generale, si può pensare in questo modo:

statement;

è costante. Il tempo di esecuzione della dichiarazione non cambierà in relazione alla N

for ( i = 0; i < N; i++ )
  statement;

è lineare. La durata del ciclo è direttamente proporzionale a N. Se N raddoppia, così il tempo di esecuzione.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

È quadratica. Il tempo di esecuzione delle due anse è proporzionale al quadrato della N. Quando N raddoppia, il tempo di calcolo aumenta di N * N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

è logaritmica. Il tempo di esecuzione dell'algoritmo è proporzionale al numero di volte N può essere divisa per 2. Questo perché l'algoritmo divide l'area di lavoro a metà con ogni iterazione.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

è N * log (N). Il tempo di esecuzione è costituito da N loop (iterativo o ricorsivo) che sono logaritmica, quindi l'algoritmo è una combinazione lineare e logaritmica.

In generale, fare qualcosa con ogni elemento in una dimensione lineare, fare qualcosa con ogni elemento in due dimensioni è quadratica, e dividendo l'area di lavoro a metà è logaritmica. Ci sono altre misure Big O, come radice cubica, esponenziale, e la piazza, ma non sono così comuni. O-grande è descritto come O () dove è la misura. L'algoritmo quicksort sarebbe descritto come O (N * log (N)).

Nota: Niente di tutto questo ha preso in considerazione meglio, media, e le misure del caso peggiore. Ogni avrebbe una propria notazione O-grande. Si noti inoltre che questa è una spiegazione molto semplicistica. Big O è il più comune, ma è anche più complesso, che ho mostrato. Vi sono anche altre notazioni come grande omega, poco o, e grande theta. Probabilmente non li si incontrano al di fuori di un corso di analisi algoritmo.

saperne di più visita: qui

Diciamo ordinate Harry Potter: Completa 8-Film Collection [Blu-ray] da Amazon e scaricare lo stesso collezione di film in linea allo stesso tempo. Si desidera verificare quale metodo è più veloce. La consegna richiede quasi un giorno per arrivare e il download completato circa 30 minuti prima. Grande! Quindi è un testa a testa.

Che cosa succede se ordino diversi film Blu-ray come Il Signore degli Anelli, di Twilight, The Dark Knight Trilogy, ecc e scaricare tutti i film in linea allo stesso tempo? Questa volta, la consegna ancora prendere un giorno per completare, ma il download online richiede 3 giorni di tempo per terminare. Per lo shopping on-line, il numero di oggetto acquistato (ingresso) non influenza il tempo di consegna. L'uscita è costante. Noi chiamiamo questo O (1) .

Per scaricare on-line, il tempo di download è direttamente proporzionale alle dimensioni dei file di film (input). Noi chiamiamo questo O (n) .

Dagli esperimenti, sappiamo che lo shopping online scale meglio di scaricamento on-line. E 'molto importante capire o-grande, perché aiuta ad analizzare il scalabilità e efficienza di algoritmi.

Nota: notazione O-grande rappresenta il scenario peggiore di un algoritmo. Supponiamo che O (1) e O (n) sono gli scenari peggiori dell'esempio sopra.

Riferimento : http://carlcheo.com/compsci

Se si dispone di un adeguato concetto di infinito nella tua testa, poi c'è una breve descrizione:

notazione O-grande ti dice il costo di risoluzione di un infinitamente grande problema.

E inoltre

fattori costanti sono trascurabili

Se si esegue l'aggiornamento a un computer in grado di eseguire l'algoritmo due volte più veloce, o-grande non noterà che. miglioramenti fattore costante sono troppo piccoli per essere notato anche nella scala che notazione O-grande lavora con. Si noti che questa è una parte intenzionale del disegno di grande notazione O.

Anche se nulla "più grande" di un fattore costante può essere rilevato, tuttavia.

Quando interessato a fare calcoli di cui il formato è "grande" abbastanza per essere considerato come circa l'infinito, allora o-grande è pari a circa il costo di risolvere il tuo problema.

Se quanto sopra non ha senso, allora non si dispone di una nozione intuitiva compatibile di infinito nella tua testa, e, probabilmente, si dovrebbe ignorare tutto quanto sopra; l'unico modo che conosco per rendere queste idee rigorosa, o per spiegare loro se non sono già intuitivamente utile, è quello di prima insegnare o-grande o qualcosa di simile. (Anche se, una volta ben capito notazione O-grande, in futuro, può valere la pena di rivisitare queste idee)

Che cosa è un semplice spiegazione inglese della notazione “Big O”?

molto veloce Nota:

Il O in "Big O" si riferisce a come "Ordine" (o appunto "ordine di")
così si potrebbe ottenere la sua idea, letteralmente, che è usato per ordinare qualcosa per confrontarli.

"Big O" fa due cose:
1. stima approssimativa del numero passi del metodo il computer si applica a realizzare un compito.
2. Facilitare il processo di confrontare con gli altri al fine di determinare se è buono o no?
3. "Big O' realizza quanto sopra due con standard Notations.
Ci sono sette notazioni più utilizzati
1. O (1), significa che il computer ottiene un lavoro fatto con 1 passo, è eccellente, ordinato No.1
2. O (log N), significa che il computer completare un compito con logN passi, la sua buona, ordinato No.2
3. O (N), terminare un'attività con N passi, la sua fiera, Ordine No.3
4. O (N log N), si conclude con un compito O(NlogN) gradini, non è buona, Ordine No.4
5. O (N ^ 2), ottenere un lavoro fatto con N^2 gradini, è brutto, Ordine No.5
6. O (2 ^ N), ottenere un lavoro fatto con 2^N gradini, è orribile, Ordine No.6
7. O (N!), Ottenere un lavoro fatto con N! gradini, è terribile, Ordine No.7

Supponiamo che si ottiene la notazione O(N^2), non solo si è chiaro il metodo prende N * N passaggi per realizzare un compito, anche si vede che non è buono come <=> dalla sua classifica.

Si prega di notare l'ordine di fine linea, solo per i vostri migliori più di 7 notazioni di understanding.There se tutte le possibilità prese in considerazione.

Nel CS, la serie di passi per realizzare un compito si chiama algoritmi.
Nella terminologia, notazione O-grande è usato per descrivere le prestazioni o la complessità di un algoritmo.

Inoltre, Big O stabilisce il caso peggiore o misurare i passi upper bound.
Si potrebbe fare riferimento a Big-Ω (Big-Omega) per migliore dei casi.

Big-Ω ( Big-Omega) la notazione (articolo) | Khan Academy

Riepilogo
"Big O" descrive le prestazioni del algoritmo e lo valuta.

o affrontare formalmente, "Big O" classifica gli algoritmi e standardizzare il processo di confronto.

Il modo più semplice di vedere le cose (in parole povere)

Stiamo cercando di vedere come il numero di parametri di input, influenza il tempo di esecuzione di un algoritmo. Se il tempo di esecuzione della vostra applicazione è proporzionale al numero di parametri di input, allora si dice di essere in Big O di n.

La dichiarazione di cui sopra è un buon inizio, ma non del tutto vero.

Una spiegazione più accurata (matematica)

Supponiamo

n = numero di parametri di input

T (n) = La funzione effettiva che esprime il tempo di esecuzione dell'algoritmo in funzione di n

c = una costante

f (n) = Una funzione approssimativa che esprime il tempo di esecuzione dell'algoritmo in funzione di n

Quindi, per quanto Big O è interessato, l'approssimazione f (n) è considerato abbastanza buono fino a quando la condizione di seguito è vera.

lim     T(n) ≤ c×f(n)
n→∞

L'equazione viene letto come Quando n tende all'infinito, T di n, è inferiore o uguale a c volte f n.

In o-grande questo è scritto come

T(n)∈O(n)

Questa viene letta come T di n è in grande O di n.

Torna a Inglese

In base alla definizione matematica di cui sopra, se dite il vostro algoritmo è un Big O di n, vuol dire che è una funzione di n (numero di parametri di input) o più veloce . Se il vostro algoritmo è O-grande di n, allora è anche automaticamente il Big O di n quadrato.

Big O di n significa il mio algoritmo viene eseguito almeno veloce come questo. Non si può guardare in notazione O-grande del vostro algoritmo e dire la sua lenta. Si può solo dire la sua veloce.

questo fuori per un video tutorial su Big O da UC Berkley. E 'è in realtà un concetto semplice. Se si sente professore (insegnante livello aka Dio) Shewchuck spiegarlo, voi direte: "Oh che è tutto quello che è!".

Ho trovato una gran bella spiegazione circa notazione O-grande soprattutto per una persona che non è più in matematica.

https: // rob- bell.net/2009/06/a-beginners-guide-to-big-o-notation/

o-grande è usato in informatica per descrivere le prestazioni   o la complessità di un algoritmo. Big O descrive in particolare la   peggiore dei casi, e può essere usato per descrivere il tempo di esecuzione   richiesto o lo spazio utilizzato (ad esempio in memoria o su disco) da un   algoritmo.

Chiunque abbia letto Perle di programmazione o di qualsiasi altro Computer Science   libri e non ha una preparazione in Matematica avranno colpito un muro   quando hanno raggiunto i capitoli che menzionano O (N log N) o altri apparentemente   sintassi pazzo. Speriamo che questo articolo vi aiuterà a ottenere un   comprensione dei principi fondamentali di Big O e logaritmi.

Come programmatore prima e una seconda matematico (o forse terzo o   quarta) ho trovato il modo migliore per capire a fondo Big O è stato quello di   produrre alcuni esempi in codice. Quindi, di seguito sono alcuni ordini comuni di   la crescita con le descrizioni e gli esempi, se possibile.

O (1)

O (1) descrive un algoritmo che sarà sempre eseguito nello stesso tempo   (O spazio) indipendentemente dalle dimensioni del set di dati di ingresso.
bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)
O (N)

O (N) descrive un algoritmo il cui rendimento crescerà in modo lineare e   in modo direttamente proporzionale alla dimensione del set di dati di input. L'esempio   qui di seguito dimostra anche come Big O favorisce le prestazioni nel caso peggiore   scenario; una stringa corrispondente è stato trovato durante ogni iterazione del   per il ciclo e la funzione sarebbe tornato presto, ma o-grande volontà   assumere sempre il limite superiore dove l'algoritmo esegue la   il numero massimo di iterazioni.
bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 
O (N ²)

O (N ²) rappresenta un algoritmo il cui rendimento è direttamente   proporzionale al quadrato della dimensione del set di dati di input. Questo è   comune con algoritmi che coinvolgono nidificate iterazioni sui dati   impostato. iterazioni Deeper annidati si tradurrà in O (N ³), O (N ⁴), ecc.
bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}
O (2 ^N)

O (2 ^N) indica un algoritmo cui crescita raddoppia con ogni additon a   impostare i dati di ingresso. La curva di crescita di un O (2 ^N) funzione è   esponenziale - partendo molto superficiale, quindi aumento meteorically. Un   esempio di una funzione O (2 ^N) è il calcolo ricorsivo di Fibonacci   numeri:
int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}
I logaritmi

I logaritmi sono leggermente più complicato da spiegare in modo da userò un comune   Esempio:

La ricerca binaria è una tecnica utilizzata per cercare set di dati ordinati. Funziona   selezionando l'elemento centrale del set di dati, essenzialmente   mediana, e lo confronta con un valore obiettivo. Se i valori corrispondono essa   tornerà il successo. Se il valore nominale è superiore al valore di   l'elemento della sonda ci vorrà la metà superiore del set di dati e   eseguire la stessa operazione contro di essa. Analogamente, se il valore bersaglio   è inferiore al valore dell'elemento sonda eseguirà la   operazione contro la metà inferiore. Essa continuerà a dimezzare i dati   set con ogni iterazione fino a quando è stato trovato il valore o finchè può   non è più dividere il set di dati.

Questo tipo di algoritmo è descritto come O (log N). Il dimezzamento iterativo   insiemi di dati descritte nell'esempio ricerca binaria produce una crescita   curva che picchi all'inizio e lentamente si appiattisce come la dimensione   I dati insiemi aumentano esempio un insieme di dati di ingresso contenente 10 articoli   prende un secondo per completare, un insieme di dati contenente 100 elementi richiederà   due secondi, e un set di dati contenente 1000 elementi avrà tre   secondi. Raddoppiando le dimensioni del set di dati di input ha scarso effetto sullala sua crescita come dopo una singola iterazione dell'algoritmo data set   sarà dimezzato e quindi alla pari con un set di dati di input metà   taglia. Questo rende algoritmi come la ricerca binaria estremamente efficiente   quando si tratta di grandi insiemi di dati.

Questa è una spiegazione molto semplificata, ma spero che copre i dettagli più importanti.

Diciamo che il vostro algoritmo affrontare il problema dipende da alcuni fattori '', per esempio facciamo è N e X.

A seconda del N e X, l'algoritmo richiede alcune operazioni, ad esempio, nel peggiore dei casi si tratta di operazioni di 3(N^2) + log(X).

Dal Big-O non si preoccupa troppo di fattore costante (aka 3), il Big-O del vostro algoritmo è O(N^2 + log(X)). Traduce in fondo 'la quantità di operazioni vostro algoritmo ha bisogno per il caso peggiore scale con questo'.

Prefazione

algoritmo:procedura/formula per risolvere un problema

Come analizzare gli algoritmi e come possiamo confrontare gli algoritmi tra loro?

esempio: a te e a un amico viene chiesto di creare una funzione per sommare i numeri da 0 a N.Tu ti viene in mente f(x) e il tuo amico ti viene in mente g(x).Entrambe le funzioni hanno lo stesso risultato, ma un algoritmo diverso.Per confrontare oggettivamente l'efficienza degli algoritmi che utilizziamo Notazione O-grande.

Notazione O-grande: descrive la velocità con cui il tempo di esecuzione aumenterà rispetto all'input man mano che l'input diventa arbitrariamente grande.

3 punti chiave:

Confrontare quanto velocemente cresce il tempo di esecuzione NON confrontare i tempi di esecuzione esatti (dipende dall'hardware)
Riguarda solo la crescita del runtime rispetto all'input (N)
COME N diventa arbitrariamente grande, concentrati sui termini che cresceranno più velocemente man mano che n diventa grande (pensa all'infinito) AKA analisi asintotica

Complessità spaziale: oltre alla complessità temporale, ci preoccupiamo anche della complessità spaziale (quanta memoria/spazio utilizza un algoritmo).Invece di controllare il tempo delle operazioni, controlliamo la dimensione dell'allocazione di memoria.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow

Qual è una semplice spiegazione inglese della notazione "Big O"?

L'elenco telefonico

Il commesso viaggiatore

Tempo polinomiale

O (1)

O (N)

O (N 2 )

O (2 N )

I logaritmi

Prefazione

O (N ²)

O (2 ^N)