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


Preferirei la minima definizione formale possibile e la matematica semplice.


4528
2018-01-28 11:10


origine


risposte:


Nota rapida, questo è quasi certamente fonte di confusione Notazione Big O  (che è un limite superiore) con notazione Theta (che è un limite di due lati). Nella mia esperienza questo è in realtà tipico delle discussioni in contesti non accademici. Ci scusiamo per qualsiasi 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 deliberatamente scelte in quella frase:

  • parente:  puoi solo confrontare le mele con le mele. Non è possibile confrontare un algoritmo per eseguire la moltiplicazione aritmetica con un algoritmo che ordina un elenco di numeri interi. Ma un confronto tra due algoritmi per eseguire operazioni aritmetiche (una moltiplicazione, un'aggiunta) ti dirà qualcosa di significativo;
  • rappresentazione:  Big-O (nella sua forma più semplice) riduce il confronto tra algoritmi in una singola variabile. Quella variabile viene scelta in base a osservazioni o ipotesi. Ad esempio, gli algoritmi di ordinamento vengono generalmente confrontati in base a operazioni di confronto (confronto di due nodi per determinare il loro ordine relativo). Ciò presuppone che il confronto sia costoso. Ma cosa succede se il confronto è economico ma lo scambio è costoso? Cambia il confronto; e
  • complessità:  se mi ci vuole un secondo per ordinare 10.000 elementi, quanto tempo mi ci vorrà per ordinare un milione? La complessità in questo caso è una misura relativa a qualcos'altro.

Torna indietro e rileggi quello sopra quando hai letto il resto.

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

  • Inoltre;
  • sottrazione;
  • moltiplicazione; e
  • divisione.

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

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

Supponiamo che l'aggiunta di questi numeri sia l'operazione più costosa in questo algoritmo. È ovvio che per aggiungere questi due numeri insieme dobbiamo aggiungere 6 cifre (e possibilmente portare un 7). Se aggiungiamo due numeri a 100 cifre, dobbiamo fare 100 aggiunte. Se aggiungiamo Due  Numeri di 10.000 cifre dobbiamo fare 10.000 aggiunte.

Vedi lo schema? Il complessità  (essendo il numero di operazioni) è direttamente proporzionale al numero di cifre n  nel numero più grande. Lo chiamiamo Sopra)  o complessità lineare .

La sottrazione è simile (eccetto che potresti aver bisogno di prendere in prestito invece di portare).

La moltiplicazione è diversa. Linea i numeri, prendi la prima cifra nel numero in basso e moltiplicala a turno contro ogni cifra nel numero più alto e così via attraverso ogni cifra. Quindi per moltiplicare i nostri due numeri a 6 cifre dobbiamo fare 36 moltiplicazioni. Potremmo dover fare anche 10 o 11 colonne per ottenere il risultato finale.

Se abbiamo due numeri a 100 cifre, dobbiamo fare 10.000 moltiplicazioni e 200 aggiunte. Per due milioni di numeri, dobbiamo fare un trilione (10 12 ) moltiplicazioni e due milioni di aggiunte.

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

Ci interessa solo la parte più significativa della complessità.

L'astuto potrebbe aver capito che potremmo esprimere il numero di operazioni come: n 2  + 2n. Ma come hai visto dal nostro esempio con due numeri di un milione di cifre a testa, il secondo termine (2n) diventa insignificante (pari allo 0,0002% delle operazioni totali in quella fase).

Si può notare che abbiamo assunto lo scenario peggiore qui. Mentre si moltiplicano i numeri a 6 cifre se uno di questi è a 4 cifre e l'altro a 6 cifre, allora abbiamo solo 24 moltiplicazioni. Ancora calcoliamo lo scenario peggiore per quello 'n', cioè quando entrambi sono numeri a 6 cifre. Quindi la notazione Big-O riguarda lo scenario peggiore di un algoritmo

La rubrica telefonica

Il prossimo esempio migliore che riesco a pensare è l'elenco telefonico, normalmente chiamato White Pages o simile, ma varierà da paese a paese. Ma sto parlando di quello che elenca le persone per cognome e poi le iniziali o il nome, possibilmente l'indirizzo e poi i numeri di telefono.

Ora, se dovessi istruire un computer a cercare il numero di telefono di "John Smith" in una rubrica che contiene 1.000.000 di nomi, cosa faresti? Ignorando il fatto che tu possa indovinare fino a che punto è iniziata la S (supponiamo che tu non possa), cosa faresti?

Una tipica implementazione potrebbe essere quella di aprirsi al centro, prendere i 500.000 esimo  e confrontalo con "Smith". Se capita di essere "Smith, John", siamo stati davvero fortunati. Molto più probabile è che "John Smith" sarà prima o dopo quel nome. Se è dopo, dividiamo metà dell'ultima rubrica e ripetiamo. Se è prima, dividiamo la prima metà della rubrica telefonica a metà e ripetiamo. E così via.

Questo è chiamato a ricerca binaria  e viene utilizzato ogni giorno per programmare se lo si realizza o meno.

Quindi, se vuoi trovare un nome in una rubrica di milioni di nomi, puoi trovare effettivamente un nome facendo almeno 20 volte questo nome. Nel confrontare gli algoritmi di ricerca decidiamo che questo confronto è la nostra 'n'.

  • Per una rubrica di 3 nomi ci vogliono 2 confronti (al massimo).
  • Per 7 ci vuole al massimo 3.
  • Per 15 ci vogliono 4.
  • ...
  • Per 1.000.000 ci vogliono 20.

Questo è incredibilmente buono no?

Questo è in termini Big-O O (log n)  o complessità logaritmica . Ora il logaritmo in questione potrebbe essere ln (base e), log 10 , log 2  o qualche altra base. Non importa che sia ancora O (log n) proprio come O (2n 2 ) e O (100n 2 ) sono ancora entrambi O (n 2 ).

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

  • Caso migliore:  Nella ricerca della rubrica telefonica, il caso 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 al peggio. A volte uno o l'altro di questi sarà più importante.

Torna alla rubrica.

Cosa succede se hai un numero di telefono e vuoi trovare un nome? La polizia ha un elenco telefonico inverso ma tali occhiate sono negate al pubblico in generale. O sono loro? Tecnicamente è possibile invertire la ricerca di un numero in una normale rubrica telefonica. Come?

Si inizia dal primo nome e si confronta il numero. Se è una partita, grande, se non, passa a quella successiva. Devi farlo in questo modo perché la rubrica è non ordinata  (per numero di telefono comunque).

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 venditore ambulante

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

Sembra semplice? Pensa di nuovo.

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

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

Beh, in realtà c'è meno di questo 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 hai 12 possibilità.
  • Con 5 anni 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 64

Quindi il problema di Big-O del commesso viaggiatore è Sopra!)  o complessità fattoriale o combinatoria .

Quando arrivi a 200 città non c'è più 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 ha una complessità di Sopra un )  si dice che abbia complessità polinomiale  o è risolvibile in tempo polinomiale .

O (n), O (n 2 ) ecc. sono tutti tempi polinomiali. Alcuni problemi non possono essere risolti in tempo polinomiale. Alcune cose sono usate nel mondo per questo. La crittografia a chiave pubblica è un ottimo esempio. È difficile da trovare computazionalmente due fattori primi di un numero molto grande. In caso contrario, non potremmo utilizzare i sistemi a chiave pubblica che utilizziamo.

Ad ogni modo, è tutto per la mia (spero inglese) spiegazione di Big O (revisionata).


6087
2018-01-28 11:18



Mostra come un algoritmo scala.

Sopra 2 ) : conosciuto come Complessità quadratica

  • 1 oggetto: 1 secondo
  • 10 articoli: 100 secondi
  • 100 articoli: 10000 secondi

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

Sopra) : conosciuto come Complessità lineare

  • 1 oggetto: 1 secondo
  • 10 articoli: 10 secondi
  • 100 articoli: 100 secondi

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

O (1) : conosciuto come Complessità costante

  • 1 oggetto: 1 secondo
  • 10 articoli: 1 secondo
  • 100 articoli: 1 secondo

Il numero di elementi è ancora in aumento di un fattore 10, ma il fattore di scala di O (1) è sempre 1.

O (log n) : conosciuto come Complessità logaritmica

  • 1 oggetto: 1 secondo
  • 10 articoli: 2 secondi
  • 100 articoli: 3 secondi
  • 1000 articoli: 4 secondi
  • 10000 articoli: 5 secondi

Il numero di calcoli è aumentato solo da un registro del valore di input. Quindi in questo caso, supponendo che ogni computazione impieghi 1 secondo, il log dell'input n è il tempo richiesto, quindi log n.

Questo è il succo di ciò. Riducono la matematica in modo che potrebbe non essere esattamente n 2  o qualunque cosa dicono che sia, ma questo sarà il fattore dominante nel ridimensionamento.


661
2018-01-28 11:28



Notazione Big-O (chiamata anche notazione "crescita asintotica") ciò che funziona "assomiglia" quando ignori fattori costanti e cose vicino all'origine . Lo usiamo per parlare come scala .


Nozioni di base

per "abbastanza" grandi input ...

  • f(x) ∈ O(upperbound) si intende f "cresce non più veloce di" upperbound
  • f(x) ∈ Ɵ(justlikethis) significare f "cresce esattamente come" justlikethis
  • f(x) ∈ Ω(lowerbound) si intende f "cresce non più lentamente di" lowerbound

la notazione big-O non interessa i fattori costanti: la funzione 9x² si dice che "crescono esattamente come" 10x². Neanche Big-O asintotica  la notazione si preoccupa per non asintotico  roba ("roba vicino all'origine" o "cosa succede quando la dimensione del problema è piccola"): la funzione 10x² si dice che "crescono esattamente come" 10x² - x + 2.

Perché dovresti voler ignorare le parti più piccole dell'equazione? Perché diventano completamente sminuiti dalle grandi parti dell'equazione mentre si considerano scale sempre più grandi; il loro contributo diventa sminuito e irrilevante. (Vedi la sezione di esempio.)

In altre parole, è tutto per il rapporto  mentre vai all'infinito. Se si divide il tempo effettivo impiegato da O(...), otterrai un fattore costante nel limite dei grandi input.  Intuitivamente questo ha senso: le funzioni "si ridimensionano" l'una con l'altra se è possibile moltiplicare una per ottenere l'altra. Cioè, quando diciamo ...

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

... ciò significa che per dimensioni del problema "abbastanza grandi" N  (se ignoriamo la roba vicino all'origine), esiste una costante (ad esempio 2.5, completamente inventata) 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 "migliore" scelta è conosciuta come il "fattore costante" dell'algoritmo ... ma spesso lo ignoriamo come ignoriamo termini non più grandi (vedi la sezione Fattori costanti per il motivo per cui di solito non contano). Puoi anche pensare all'equazione di cui sopra come legata, dicendo " Nella peggiore delle ipotesi, il tempo necessario non sarà mai peggiore di grosso modo N*log(N), entro un fattore di 2,5 (un fattore costante non ci interessa molto) ".

In generale, O(...) è il più utile perché spesso ci preoccupiamo del comportamento del caso peggiore. Se f(x) rappresenta qualcosa di "cattivo" come il processore o l'utilizzo della memoria, quindi " f(x) ∈ O(upperbound)" si intende " upperbound è lo scenario peggiore di utilizzo del processore / memoria ".


applicazioni

In quanto costrutto puramente matematico, la notazione O grande non si limita a parlare del tempo di elaborazione e della memoria. Puoi usarlo per discutere asintoti di qualsiasi cosa in cui il ridimensionamento sia significativo, come ad esempio:

  • il numero di possibili strette di mano tra N persone a una festa ( Ɵ(N²), nello specifico N(N-1)/2, ma ciò che importa è che "scala come" )
  • numero previsto probabilistico di persone che hanno visto un marketing virale in funzione del tempo
  • in che modo la latenza del sito web viene ridimensionata con il numero di unità di elaborazione in una CPU o GPU o cluster di computer
  • come l'uscita di calore scala sulla CPU muore in funzione del conteggio dei transistor, della tensione, ecc.
  • quanto tempo deve essere eseguito da un algoritmo, in funzione della dimensione dell'input
  • quanto spazio deve essere eseguito da un algoritmo, in funzione della dimensione dell'input

Esempio

Per l'esempio della stretta di mano sopra, tutti in una stanza scuotono la mano di tutti gli altri. In questo esempio, #handshakes ∈ Ɵ(N²). Perché?

Eseguire il backup un po ': il numero di handshake è esattamente n-choose-2 o N*(N-1)/2 (ognuno di N persone stringe la mano ad altre persone N-1, ma questa doppia stretta di mano è così divisa per 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Tuttavia, per un numero molto elevato di persone, il termine lineare N è sminuito e contribuisce efficacemente a 0 al rapporto (nel grafico: la frazione di caselle vuote sulla diagonale sopra le caselle totali diventa più piccola man mano che il numero di partecipanti diventa più grande). Pertanto il comportamento di ridimensionamento è order 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 fossero nemmeno lì (N 2  segni di spunta asintoticamente).

(digressione temporanea da "plain English" :) Se volevi dimostrarlo a te stesso, potresti eseguire qualche semplice algebra sul rapporto per dividerlo in più termini ( limsignifica "considerato nel limite di", ignoralo solo se non l'hai visto, è solo una notazione per "e N è davvero molto 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 strette di mano 'sembra' x² così tanto per valori grandi, che se dovessimo scrivere il rapporto # handshakes / x², il fatto che non abbiamo bisogno Esattamente  x2 le strette di mano non si visualizzerebbero nemmeno nel decimale per un tempo arbitrariamente grande.

per esempio. per x = 1 milione, rapporto # handshakes / x²: 0.499999 ...


Costruire l'intuizione

Questo ci permette di fare affermazioni come ...

"Per inputize = N abbastanza grandi, non importa quale sia il fattore costante, se io Doppio  la dimensione dell'input


361
2017-07-08 04:46



EDIT: nota rapida, questo è quasi certamente fonte di confusione Notazione Big O  (che è un limite superiore) con notazione Theta (che è sia un limite superiore che uno inferiore). Nella mia esperienza questo è in realtà tipico delle discussioni in contesti non accademici. Ci scusiamo per qualsiasi confusione causata.

In una frase: mano a mano che le dimensioni del tuo lavoro aumentano, quanto tempo ci vuole per completarlo?

Ovviamente è solo usando "size" come input e "time taken" come output - la stessa idea si applica se si vuole parlare dell'uso della memoria ecc.

Ecco un esempio in cui abbiamo N T-shirts che vogliamo asciugare. Bene assumere  è incredibilmente veloce portarli nella posizione di asciugatura (cioè l'interazione umana è trascurabile). Questo non è il caso nella vita reale, ovviamente ...

  • Utilizzando una linea di lavaggio esterna: assumendo di avere un cortile infinitamente grande, il lavaggio asciuga in tempo O (1). Per quanto ne abbiate, otterrà lo stesso sole e l'aria fresca, quindi le dimensioni non influiscono sul tempo di asciugatura.

  • Usando un'asciugabiancheria: metti 10 camicie per ogni carico, e poi si fanno un'ora dopo. (Ignora i numeri reali qui - sono irrilevanti.) Quindi asciuga 50 magliette di  5 volte il tempo di asciugare 10 camicie.

  • Mettere tutto in un armadio di ventilazione: se mettiamo tutto in un unico grande mucchio e lasciamo solo il calore generale, ci vorrà molto tempo perché le camicie intermedie si asciughino. Non mi piacerebbe indovinare il dettaglio, ma sospetto che sia almeno O (N ^ 2) - mentre aumenti il ​​carico di lavaggio, il tempo di asciugatura aumenta più velocemente.

Un aspetto importante della notazione "big O" è questo non lo fa  dire quale algoritmo sarà più veloce per una determinata dimensione. Prendi una tabella hash (chiave stringa, valore intero) rispetto a una matrice di coppie (stringa, intero). È più veloce trovare una chiave nella tabella hash o in un elemento dell'array, in base a una stringa? (cioè per l'array, "trova il primo elemento in cui la parte di stringa corrisponde alla chiave specificata.") Gli hashtable vengono generalmente ammortizzati (~ = "in media") O (1) - una volta impostati, dovrebbe richiedere circa lo stesso tempo per trovare una voce in una tabella di 100 voci come in una tabella di immissione di 1.000.000. Trovare un elemento in un array (basato sul contenuto piuttosto che sull'indice) è lineare, ovvero O (N) - in media, dovrai esaminare metà delle voci.

Questo rende un hashtable più veloce di un array per le ricerche? Non necessariamente. Se hai una raccolta molto piccola di voci, un array potrebbe essere più veloce: potresti essere in grado di controllare tutte le stringhe nel tempo necessario per calcolare semplicemente l'hashcode di quello che stai guardando. Man mano che il set di dati aumenta, tuttavia, l'hashtable alla fine supererà la matrice.


236
2018-01-28 11:16



Big O descrive un limite superiore al comportamento di crescita di una funzione, ad esempio il runtime di un programma, quando gli input diventano grandi.

Esempi:

  • O (n): se raddoppio la dimensione di input, il tempo di esecuzione raddoppia

  • Sopra 2 ): Se la dimensione di input raddoppia i quadrupli di runtime

  • O (log n): se la dimensione di input raddoppia il tempo di esecuzione aumenta di uno

  • O (2 n ): Se la dimensione di input aumenta di uno, il tempo di esecuzione raddoppia

La dimensione di input è solitamente lo spazio in bit necessari per rappresentare l'input.


120
2018-01-28 11:23



La notazione Big O è più comunemente utilizzata dai programmatori come misura approssimativa della durata di un calcolo (algoritmo) per il completamento espresso in funzione della dimensione del set di input.

Big O è utile per confrontare il modo in cui due algoritmi si scaleranno man mano che aumenta il numero di input.

Più precisamente Notazione Big O  è usato per esprimere il comportamento asintotico di una funzione. Ciò significa come la funzione si comporta quando si avvicina all'infinito.

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

  • O (1)  - Il tempo di completamento è lo stesso indipendentemente dalla dimensione del set di input. Un esempio è l'accesso a un elemento dell'array per indice.
  • O (Log N)  - Il tempo di completamento aumenta all'incirca in linea con il log2 (n). Ad esempio, 1024 elementi impiegano circa il doppio di 32 elementi, perché Log2 (1024) = 10 e Log2 (32) = 5. Un esempio è trovare un elemento in un albero di ricerca binario  (BST).
  • SOPRA)  - Il tempo necessario per completare la scala in modo lineare con la dimensione del set di input. In altre parole, se raddoppi il numero di elementi nel set di input, l'algoritmo impiega all'incirca il doppio del tempo. Un esempio è il conteggio del numero di elementi in un elenco collegato.
  • O (N Log N)  - Il tempo di completamento aumenta del numero di elementi moltiplicato per il risultato di Log2 (N). Un esempio di questo è tipo di heap  e ordinamento rapido .
  • O (N ^ 2)  - Il tempo di completamento è approssimativamente uguale al quadrato del numero di elementi. Un esempio di questo è bubble sort .
  • SOPRA!)  - Il tempo di completamento è il fattoriale del set di input. Un esempio di questo è il soluzione di brute-force di commesso viaggiatore .

Big O ignora i fattori che non contribuiscono in maniera significativa alla curva di crescita di una funzione mentre la dimensione di input aumenta verso l'infinito. Ciò significa che le costanti aggiunte o moltiplicate dalla funzione vengono semplicemente ignorate.


97
2017-09-05 16:31



Big O è solo un modo per "esprimere" te stesso in un modo comune, "Quanto tempo / spazio ci vuole per eseguire il mio codice?".

Puoi spesso vedere O (n), O (n 2 ), O (nlogn) e così via, tutti questi sono solo modi per mostrare; Come cambia un algoritmo?

O (n) significa che Big O è n, e ora potresti pensare, "What is n !?" Bene "n" è la quantità di elementi. Imaging che si desidera cercare un oggetto in una matrice. Dovresti cercare Ogni elemento e "Sei l'elemento / elemento corretto?" nel peggiore dei casi, l'articolo è all'ultimo indice, il che significa che ci vuole tanto tempo quanto gli elementi nell'elenco, quindi per essere generici, diciamo "oh hey, n è una giusta quantità di valori!" .

Allora potresti capire cosa "n 2 "significa, ma per essere ancora più specifici, giocare con il pensiero di avere un semplice, il più semplice degli algoritmi di ordinamento, bubblesort.Questo algoritmo deve esaminare l'intera lista, per ogni elemento.

La mia lista

  1. 1
  2. 6
  3. 3

Il flusso qui sarebbe:

  • Confronta 1 e 6, che è il più grande? Ok 6 è nella giusta posizione, andando avanti!
  • Confronta 6 e 3, oh, 3 è inferiore! Spostiamolo, Ok la lista è cambiata, dobbiamo iniziare dall'inizio!

Questo è O n 2  perché, devi guardare tutti gli elementi nella lista ci sono "n" elementi. Per ogni oggetto, guardi tutti gli oggetti ancora una volta, per il confronto, questo è anche "n", quindi per ogni oggetto, guardi "n" volte che significano n * n = n 2

Spero che questo sia semplice come lo vuoi tu.

Ma ricorda, Big O è solo un modo per espanderti nel modo di tempo e spazio.


77
2018-01-28 11:14



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

Ci sono molte informazioni che Big O non ti dice su un determinato algoritmo. Tocca all'osso e fornisce solo informazioni sulla natura di ridimensionamento di un algoritmo, in particolare su come l'utilizzo delle risorse (tempo di riflessione o memoria) di un algoritmo si ridimensiona in risposta alla "dimensione di input".

Considera la differenza tra un motore a vapore e un razzo. Non sono semplicemente diverse varietà della stessa cosa (come, diciamo, un motore Prius contro un motore Lamborghini), ma sono sistemi di propulsione radicalmente diversi, al loro centro. Un motore a vapore potrebbe essere più veloce di un razzo giocattolo, ma nessun motore a pistoni a vapore sarà in grado di raggiungere la velocità di un veicolo di lancio orbitale. Questo perché questi sistemi hanno caratteristiche di ridimensionamento differenti rispetto alla relazione del combustibile necessario ("uso delle risorse") per raggiungere una determinata velocità ("dimensione di input").

Perché è così importante? Perché il software si occupa di problemi che possono differire in termini di dimensioni da fattori fino a un trilione. Consideralo per un momento. Il rapporto tra la velocità necessaria per viaggiare sulla Luna e la velocità di camminata umana è inferiore a 10.000: 1, e questo è assolutamente minuscolo rispetto alla gamma in cui il software di dimensioni dell'input potrebbe trovarsi ad affrontare. E poiché il software può affrontare un intervallo astronomico in dimensioni di input, c'è il potenziale per la complessità Big O di un algoritmo, è la natura di ridimensionamento fondamentale, per superare qualsiasi dettaglio di implementazione.

Considera l'esempio di classificazione canonica. Bubble-sort è O (n 2 ) mentre merge-sort è O (n log n). Supponiamo che tu abbia due applicazioni di ordinamento, l'applicazione A che utilizza bubble-sort e l'applicazione B che usa merge-sort, e diciamo che per le dimensioni di input di circa 30 elementi l'applicazione A è 1.000 volte più veloce dell'applicazione B all'ordinamento. Se non devi mai ordinare più di 30 elementi, è ovvio che dovresti preferire l'applicazione A, poiché è molto più veloce con queste dimensioni di input. Tuttavia, se trovi che potresti dover ordinare dieci milioni di elementi, allora quello che ti aspetteresti è che l'applicazione B in realtà in questo caso sia migliaia di volte più veloce dell'applicazione A, interamente a causa del modo in cui ogni algoritmo scala.


52
2018-01-28 13:12



Ecco il semplice bestiario inglese che tendo ad usare per spiegare 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 per passare a una classe di complessità più costosa varia in modo significativo.

O (1):

Nessuna crescita. Indipendentemente dalla grandezza del problema, puoi risolverlo nello stesso tempo. Questo è in qualche modo analogo alla trasmissione in cui richiede la stessa quantità di energia per trasmettere su una determinata distanza, indipendentemente dal numero di persone che si trovano all'interno della gamma di trasmissione.

O (log n ):

Questa complessità è la stessa di O (1)  tranne che è solo un po 'peggio. Per tutti gli scopi pratici, puoi considerare questo come un ridimensionamento costante molto grande. La differenza di lavoro tra l'elaborazione di 1 miliardo e 1 miliardo di articoli è solo un fattore 6.

O ( n ):

Il costo per risolvere il problema è proporzionale alla dimensione del problema. Se il problema raddoppia, il costo della soluzione raddoppia. Dal momento che la maggior parte dei problemi deve essere scansionata nel computer in qualche modo, come l'immissione dei dati, la lettura del disco o il traffico di rete, questo è generalmente un fattore di ridimensionamento economico.

O ( n  ceppo n ):

Questa complessità è molto simile a O ( n ) . Per tutti gli scopi pratici, i due sono equivalenti. Questo livello di complessità sarebbe generalmente considerato scalabile. Modificando alcune ipotesi O ( n  ceppo n )  gli algoritmi possono essere trasformati in O ( n )  algoritmi. Ad esempio, il limite delle dimensioni delle chiavi riduce l'ordinamento da O ( n  ceppo n )  a O ( n ) .

O ( n 2 ):

Cresce come un quadrato, dove n  è la lunghezza del lato di un quadrato. Questo è lo stesso tasso di crescita dell '"effetto rete", in cui tutti in una rete potrebbero conoscere tutti gli altri nella rete. La crescita è costosa. La maggior parte delle soluzioni scalabili non può 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 problemi di dimensioni non banali. Utile per sapere cosa evitare e per gli esperti per trovare algoritmi approssimativi che sono in O ( n K ) .


35
2018-01-27 23:09



Big O è una misura di quanto tempo / spazio utilizza un algoritmo in relazione alla dimensione del suo input.

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

Se un algoritmo è O (n 2 ) quindi il tempo / spazio aumentano al ritmo del suo input al quadrato.

e così via.


34
2018-01-28 11:19