Big-O per Otto Anni?[duplica]

StackOverflow https://stackoverflow.com/questions/107165

Domanda

A questa domanda ha già una risposta qui:

Sto chiedendo di più su ciò che questo significa per il mio codice.Capisco i concetti matematicamente, io appena ho un momento difficile avvolgere la mia testa intorno a quello che significa concettualmente.Per esempio, se si dovesse eseguire un'operazione O(1) su una struttura di dati, capisco che il numero di operazioni che deve eseguire non crescono perché non ci sono più elementi.E un O(n) operazioni significa che è possibile eseguire una serie di operazioni su ogni elemento.Qualcuno potrebbe riempire gli spazi vuoti qui?

  • Come che cosa esattamente sarebbe un O(n^2) operazione di fare?
  • E che diamine significa se un'operazione è O(n log(n))?
  • E non qualcuno che ha a fumare crack per scrivere un O(x!)?
È stato utile?

Soluzione

Un modo di pensarci è questo:

O (N ^ 2) significa per ogni elemento, stai facendo qualcosa con ogni altro elemento, come confrontarli. L'ordinamento a bolle ne è un esempio.

O (N registro N) significa per ogni elemento, stai facendo qualcosa che deve solo guardare il registro N degli elementi. Questo di solito è perché sai qualcosa sugli elementi che ti consentono di fare una scelta efficiente. I tipi più efficienti ne sono un esempio, come unisci tipo.

O (N!) significa fare qualcosa per tutte le possibili permutazioni degli elementi N. Il commesso viaggiatore ne è un esempio, dove ci sono N! modi per visitare i nodi, e la soluzione della forza bruta è di esaminare il costo totale di ogni possibile permutazione per trovare quella ottimale.

Altri suggerimenti

La cosa grande che la notazione Big-O significa per il tuo codice è come si ridimensionerà quando raddoppi la quantità di " cose " funziona. Ecco un esempio concreto: 

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

Quindi prendi quicksort che è O (n log (n)) vs ordinamento bolla che è O (n ^ 2). Quando si ordinano 10 cose, quicksort è 3 volte più veloce dell'ordinamento a bolle. Ma quando si ordinano 100 cose, è 14 volte più veloce! È quindi importante scegliere chiaramente l'algoritmo più veloce. Quando si arriva a database con milioni di righe, ciò può significare la differenza tra l'esecuzione della query in 0,2 secondi, anziché richiedere ore.

Un'altra cosa da considerare è che un cattivo algoritmo è una cosa che la legge di Moore non può aiutare. Ad esempio, se hai qualche calcolo scientifico che è O (n ^ 3) e può calcolare 100 cose al giorno, raddoppiando la velocità del processore ottieni 125 cose in un giorno. Tuttavia, porta quel calcolo su O (n ^ 2) e stai facendo 1000 cose al giorno.

Chiarimento: In realtà, Big-O non dice nulla sulle prestazioni comparative di algoritmi diversi nello stesso punto di dimensione specifica, ma piuttosto sulle prestazioni comparative dello stesso algoritmo in punti di dimensioni diverse: 

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

Potresti trovare utile visualizzarlo:

Analisi O grande

Inoltre, su LogY / LogX ridimensiona le funzioni n 1/2 , n, n 2 tutte sembra linee rette , su LogY / X 2 n , e n , 10 n sono linee rette e n! è linearithmic (sembra n log n ).

Potrebbe essere troppo matematico, ma ecco il mio tentativo. (Io sono un matematico.)

Se qualcosa è O ( f ( n )), allora il tempo di esecuzione su n sarà uguale a A f ( n ) + B (misurato, ad esempio, cicli di clock o operazioni della CPU). È fondamentale per capire che hai anche queste costanti A e B , che derivano dall'attuazione specifica. B rappresenta essenzialmente il " overhead costante " delle tue operazioni, ad esempio alcune preelaborazioni che fai che non dipendono dalle dimensioni della raccolta. A rappresenta la velocità del tuo attuale algoritmo di elaborazione degli articoli.

La chiave, tuttavia, è che usi la notazione O grande per capire quanto bene si ridimensionerà qualcosa . Quindi quelle costanti non contano davvero: se stai cercando di capire come scalare da 10 a 10000 articoli, a chi importa del costante overhead B ? Allo stesso modo, altre preoccupazioni (vedi sotto) supereranno sicuramente il peso della costante moltiplicativa A .

Quindi il vero affare è f ( n ). Se f non cresce affatto con n , ad es. f ( n ) = 1, quindi ridimensionerai in modo fantastico --- il tuo tempo di esecuzione sarà sempre solo A + B . Se f cresce linearmente con n , ovvero f ( n ) = n , il tuo tempo di esecuzione si ridimensionerà al meglio delle aspettative --- se i tuoi utenti stanno aspettando 10 ns per 10 elementi, aspetteranno 10000 ns per 10000 elementi (ignorando la costante additiva). Ma se cresce più velocemente, come n 2 , allora sei nei guai; le cose inizieranno a rallentare troppo quando si ottengono raccolte più grandi. f ( n ) = n log ( n ) è un buon compromesso, di solito: l'operazione non può essere così semplice da dare un ridimensionamento lineare, ma sei riuscito a ridurre le cose in modo che ridimensioni molto meglio di f ( n ) = n 2 .

In pratica, ecco alcuni buoni esempi:

  • O (1): recupero di un elemento da un array. Sappiamo esattamente dove si trova nella memoria, quindi andiamo a prenderlo. Non importa se la collezione ha 10 articoli o 10000; è ancora all'indice (diciamo) 3, quindi passiamo alla posizione 3 in memoria.
  • O ( n ): recupero di un elemento da un elenco collegato. Qui, A = 0,5, perché in media dovrai passare attraverso 1/2 dell'elenco collegato prima di trovare l'elemento che stai cercando.
  • O(n 2 ): vari " dumb " algoritmi di ordinamento. Perché generalmente la loro strategia prevede, per ogni elemento ( n ), guardi tutti gli altri elementi (quindi ogni volta un altro n , dando n < sup> 2 ), quindi posizionati nel posto giusto.
  • O ( n log ( n )): vari " smart " algoritmi di ordinamento. Si scopre che devi solo guardare, diciamo, 10 elementi in una raccolta di elementi 10 10 per ordinare in modo intelligente te stesso rispetto a tutti nella raccolta. Poiché tutti gli altri anche esamineranno 10 elementi e il comportamento emergente è orchestrato nel modo giusto in modo che questo sia sufficiente per produrre un elenco ordinato.
  • O ( n !): un algoritmo che " prova tutto, " poiché ci sono (proporzionale a) n ! possibili combinazioni di n elementi che potrebbero risolvere un determinato problema. Quindi passa in rassegna tutte queste combinazioni, le prova, quindi si interrompe ogni volta che riesce.

La risposta di don.neufeld è molto buona, ma probabilmente la spiegherei in due parti: in primo luogo, c'è una gerarchia approssimativa di O () in cui cadono la maggior parte degli algoritmi. Quindi, puoi guardare ognuno di questi per elaborare schizzi di ciò che fanno gli algoritmi tipici di quella complessità temporale.

Ai fini pratici, le uniche O () che sembrano avere importanza sono:

  • O (1) " tempo costante " - il tempo richiesto è indipendente dalla dimensione dell'input. Come categoria approssimativa, includerei qui algoritmi come ricerche di hash e Union-Find, anche se nessuno di questi è in realtà O (1).
  • O (log (n)) " logaritmico " - diventa più lento man mano che ottieni input più grandi, ma una volta che l'input diventa abbastanza grande, non cambierà abbastanza di cui preoccuparti. Se il tuo runtime va bene con dati di dimensioni ragionevoli, puoi inondarlo con tutti i dati aggiuntivi che desideri e andrà comunque bene.
  • O (n) " lineare " - più input, più tempo ci vuole, in un compromesso uniforme. Tre volte la dimensione dell'input richiederà circa tre volte di più.
  • O (n log (n)) " migliore di quadratic " - Aumentare le dimensioni dell'input fa male, ma è ancora gestibile. L'algoritmo è probabilmente decente, è solo che il problema di fondo è più difficile (le decisioni sono meno localizzate rispetto ai dati di input) rispetto a quei problemi che possono essere risolti in tempo lineare. Se le dimensioni dell'input stanno aumentando, non dare per scontato che potresti necessariamente gestire il doppio delle dimensioni senza cambiare la tua architettura (ad esempio spostando le cose in calcoli batch notturni o non facendo cose per frame). Va bene se la dimensione dell'input aumenta un po ', però; fai attenzione ai multipli.
  • O (n ^ 2) " quadratic " - funzionerà davvero solo fino a una certa dimensione del tuo input, quindi presta attenzione a quanto potrebbe arrivare. Inoltre, il tuo algoritmo potrebbe fare schifo: pensa a fondo se c'è un algoritmo O (n log (n)) che ti darebbe ciò di cui hai bisogno. Una volta che sei qui, sentiti molto grato per l'eccezionale hardware di cui siamo stati dotati. Non molto tempo fa, quello che stai cercando di fare sarebbe stato impossibile per tutti gli scopi pratici.
  • O (n ^ 3) " cubico " - qualitativamente non molto diverso da O (n ^ 2). Si applicano gli stessi commenti, solo di più. C'è una buona possibilità che un algoritmo più intelligente questa volta si riduca a qualcosa di più piccolo, ad esempio O (n ^ 2 log (n)) o O (n ^ 2.8 ...), ma poi c'è una buona possibilità che non varrà la pena. (Sei già limitato nella tua dimensione di input pratica, quindi i fattori costanti che potrebbero essere richiesti per gli algoritmi più intelligenti probabilmente sommergeranno i loro vantaggi per casi pratici. Inoltre, pensare è lento; lasciare che il computer lo mastichi potrebbe farti risparmiare tempo nel complesso.)
  • O (2 ^ n) " esponenziale " - il problema è fondamentalmente difficile dal punto di vista computazionale o sei un idiota. Questi problemi hanno un sapore riconoscibile per loro. Le dimensioni degli input sono limitate a un limite rigido piuttosto specifico. Saprai rapidamente se rientri in quel limite.

E questo è tutto. Esistono molte altre possibilità che si adattano tra queste (o sono maggiori di O (2 ^ n)), ma spesso non si verificano in pratica e non sono qualitativamente molto diverse da una di queste. Gli algoritmi cubici sono già un po 'lunghi; Le ho incluse solo perché le ho incontrate abbastanza spesso da essere degne di nota (ad es. Moltiplicazione di matrici).

Cosa sta realmente accadendo per queste classi di algoritmi? Bene, penso che tu abbia avuto un buon inizio, anche se ci sono molti esempi che non si adattano a queste caratterizzazioni. Ma per quanto sopra, direi che di solito va qualcosa del genere:

  • O (1) - stai solo guardando al massimo una porzione di dati fissi dei tuoi dati di input, e probabilmente nessuno di essi. Esempio: il massimo di un elenco ordinato.
    • O la dimensione dell'input è limitata.Esempio: aggiunta di due numeri. (Notare che l'aggiunta di numeri N è tempo lineare.)
  • O (log n): ogni elemento del tuo input ti dice abbastanza per ignorare una grande frazione del resto dell'input. Esempio: quando si guarda un elemento array nella ricerca binaria, il suo valore indica che è possibile ignorare & Quot; half & Quot; del tuo array senza guardarlo. O allo stesso modo, l'elemento che guardi ti dà abbastanza un sommario di una frazione dell'input rimanente che non dovrai guardarlo.
    • Tuttavia, non c'è nulla di speciale nelle metà: se puoi ignorare solo il 10% del tuo input ad ogni passaggio, è comunque logaritmico.
  • O (n): esegui una quantità fissa di lavoro per elemento di input. (Ma vedi sotto.)
  • O (n log (n)) - ci sono alcune varianti.
    • È possibile dividere l'input in due pile (in non più di un tempo lineare), risolvere il problema in modo indipendente su ogni pila e quindi combinare le due pile per formare la soluzione finale. L'indipendenza delle due pile è la chiave. Esempio: fusione classica ricorsiva.
    • Ogni passaggio di tempo lineare sui dati ti porta a metà della tua soluzione. Esempio: quicksort se si pensa in termini di distanza massima di ciascun elemento alla sua posizione ordinata finale ad ogni passo di partizionamento (e sì, so che in realtà è O (n ^ 2) a causa di scelte pivot degenerate. Ma in pratica, rientra nella mia categoria O (n log (n)).)
  • O (n ^ 2) - devi guardare ogni coppia di elementi di input.
    • Oppure no, ma pensi di sì e stai usando l'algoritmo sbagliato.
  • O (n ^ 3) - um ... Non ho una caratterizzazione scattante di questi. È probabilmente uno di:
    • Stai moltiplicando le matrici
    • Stai guardando ogni coppia di input ma l'operazione che fai richiede di guardare di nuovo tutti gli input
    • l'intera struttura grafica del tuo input è rilevante
  • O (2 ^ n) - devi considerare ogni possibile sottoinsieme dei tuoi input.

Nessuno di questi è rigoroso. Soprattutto algoritmi di tempo lineari (O (n)): potrei trovare un numero di esempi in cui devi guardare tutti gli input, quindi metà di essi, quindi metà di quelli, ecc. O viceversa - - si piegano insieme coppie di input, quindi si ricorre all'output. Questi non si adattano alla descrizione sopra, dal momento che non stai guardando ogni input una volta, ma esce comunque in tempo lineare. Tuttavia, il 99,2% delle volte, tempo lineare significa guardare ogni input una volta.

Molti di questi sono facili da dimostrare con qualcosa di non programmabile, come mescolare le carte.

Ordinamento di un mazzo di carte passando attraverso l'intero mazzo per trovare l'asso di picche, quindi attraversando l'intero mazzo per trovare il 2 di picche, e così via sarebbe il caso peggiore n ^ 2, se il mazzo fosse già ordinati al contrario. Hai guardato tutte e 52 le carte 52 volte.

In generale gli algoritmi veramente cattivi non sono necessariamente intenzionali, sono comunemente un uso improprio di qualcos'altro, come chiamare un metodo che è lineare all'interno di un altro metodo che si ripete sullo stesso set in modo lineare.

Ok - ci sono alcune risposte molto buone qui, ma quasi tutte sembrano fare lo stesso errore ed è uno che sta pervadendo l'uso comune.

Informalmente, scriviamo che f (n) = O (g (n)) if, fino a un fattore di ridimensionamento e per tutti n maggiore di alcuni n0, g (n) è più grande di f (n). Cioè, f (n) non cresce più velocemente di, oppure è delimitato dall'alto da, g (n). Questo non ci dice nulla sulla velocità con cui f (n) cresce, tranne per il fatto che è garantito che non sia peggio di g (n).

Un esempio concreto: n = O (2 ^ n). Sappiamo tutti che n cresce molto meno rapidamente di 2 ^ n, quindi ciò ci dà diritto a dire che è limitato da sopra dalla funzione esponenziale. C'è molto spazio tra n e 2 ^ n, quindi non è un limite molto stretto , ma è comunque un limite legittimo.

Perché noi (informatici) utilizziamo i limiti anziché essere esatti? Poiché a) i limiti sono spesso più facili da dimostrare eb) ci dà una scorciatoia per esprimere le proprietà degli algoritmi. Se dico che il mio nuovo algoritmo è O (n.log n) ciò significa che nel peggiore dei casi il suo tempo di esecuzione sarà limitato dall'alto da n.log n su n input, per n abbastanza grande (anche se vedi i miei commenti qui sotto su quando potrei non voler dire nel caso peggiore).

Se invece, vogliamo dire che una funzione cresce esattamente altrettanto rapidamente di un'altra funzione, usiamo theta per evidenziare quel punto (scriverò T (f (n)) per significare \ Theta di f (n) nel markdown). T (g (n)) è una scorciatoia per essere limitato da sopra e sotto da g (n), di nuovo, fino a un fattore di ridimensionamento e asintoticamente.

Questo è f (n) = T (g (n)) < = > f (n) = O (g (n)) e g (n) = O (f (n)). Nel nostro esempio, possiamo vedere che n! = T (2 ^ n) perché 2 ^ n! = O (n).

Perché preoccuparsi di questo? Perché nella tua domanda scrivi "qualcuno dovrebbe fumare crack per scrivere una O (x!)?" La risposta è no, perché in pratica tutto ciò che scrivi sarà limitato dalla funzione fattoriale. Il tempo di esecuzione di quicksort è O (n!) - non è un limite stretto.

C'è anche un'altra dimensione di sottigliezza qui. In genere stiamo parlando del input del caso peggiore quando usiamo la notazione O (g (n)), quindi stiamo facendo un'istruzione composta: nel peggiore dei casi il tempo di esecuzione non sarà peggiore di un algoritmo che esegue g (n) passi, di nuovo in scala modulo e per n abbastanza grande. Ma a volte vogliamo parlare del tempo di esecuzione dei casi medi e persino migliori .

Quicksort alla vaniglia è, come sempre, un buon esempio. È T (n ^ 2) nel peggiore dei casi (in realtà richiederà almeno n ^ 2 passaggi, ma non significativamente di più), ma T (n.log n) nel caso medio, vale a dire il numero previsto di passi è proporzionale a n.log n. Nel migliore dei casi è anche T (n.log n) - ma è possibile migliorarlo, ad esempio controllando se l'array è già stato ordinato, nel qual caso il tempo di esecuzione del caso migliore sarebbe T (n).

In che modo questo si collega alla tua domanda sulle realizzazioni pratiche di questi limiti? Bene, sfortunatamente, la notazione O () nasconde costanti con cui le implementazioni del mondo reale devono fare i conti. Quindi, sebbene possiamo dire che, per esempio, per un'operazione T (n ^ 2) dobbiamo visitare ogni possibile coppia di elementi, non sappiamo quante volte dobbiamo visitarli (tranne che non è una funzione di n). Quindi potremmo dover visitare ogni coppia 10 volte, o 10 ^ 10 volte, e l'istruzione T (n ^ 2) non fa alcuna distinzione. Anche le funzioni di ordine inferiore sono nascoste: potremmo dover visitare ogni coppia di elementi una volta e ogni singolo elemento 100 volte, perché n ^ 2 + 100n = T (n ^ 2). L'idea alla base della notazione O () è che per n abbastanza grande, questo non importa affatto perché n ^ 2 diventa così tanto più grande di 100n che non notiamo nemmeno l'impatto di 100n sul tempo di esecuzione. Tuttavia, abbiamo spesso a che fare con "sufficientemente piccoli" in modo tale che fattori costanti e cosìfare una differenza reale, significativa.

Ad esempio, quicksort (costo medio T (n.log n)) e heapsort (costo medio T (n.log n)) sono entrambi algoritmi di ordinamento con lo stesso costo medio, ma quicksort è in genere molto più veloce di heapsort. Questo perché heapsort esegue alcuni più confronti per elemento rispetto a quicksort.

Questo non vuol dire che la notazione O () sia inutile, solo imprecisa. È uno strumento piuttosto schietto da usare per piccoli n.

(Come nota finale di questo trattato, ricorda che la notazione O () descrive solo la crescita di qualsiasi funzione - non deve necessariamente essere tempo, potrebbe essere memoria, messaggi scambiati in un sistema distribuito o numero di CPU necessarie per un algoritmo parallelo.)

Provo a spiegare dando semplici esempi di codice in C #.

Per List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};

O (1) sembra 

return numbers.First();

O (n) sembra 

int result = 0;
foreach (int num in numbers)
{
    result += num;
}
return result;

O (n log (n)) sembra 

int result = 0;
foreach (int num in numbers)
{
    int index = numbers.length - 1;
    while (index > 1)
    {
        // yeah, stupid, but couldn't come up with something more useful :-(
        result += numbers[index];
        index /= 2;
    }
}
return result;

O (n ^ 2) sembra 

int result = 0;
foreach (int outerNum in numbers)
{
    foreach (int innerNum in numbers)
    {
        result += outerNum * innerNum;
    }
}
return result;

O (n!) sembra stanco di inventare qualcosa di semplice.
Ma spero che tu ottenga il punto generale?

Il modo in cui lo descrivo ai miei amici non tecnici è così:

Prendi in considerazione l'aggiunta di più cifre. Buona aggiunta vecchio stile, carta e matita. Il tipo che hai imparato quando avevi 7-8 anni. Dati due numeri di tre o quattro cifre, puoi scoprire cosa si sommano abbastanza facilmente.

Se ti dessi due numeri di 100 cifre e ti chiedessi a cosa si sommano, capire che sarebbe abbastanza semplice, anche se dovessi usare carta e matita. Un bambino intelligente potrebbe fare una tale aggiunta in pochi minuti. Ciò richiederebbe solo circa 100 operazioni.

Ora considera la moltiplicazione a più cifre. Probabilmente l'hai imparato a circa 8 o 9 anni. (Si spera) hai fatto molti esercizi ripetitivi per imparare la meccanica dietro di essa.

Ora, immagina di averti dato quegli stessi due numeri di 100 cifre e di averti detto di moltiplicarli insieme. Questo sarebbe un compito molto, molto più difficile, qualcosa che ti richiederebbe ore per fare - e che difficilmente faresti senza errori. La ragione di ciò è che (questa versione di) la moltiplicazione è O (n ^ 2); ogni cifra nel numero in basso deve essere moltiplicata per ogni cifra nel numero in alto, lasciando un totale di circa n ^ 2 operazioni. Nel caso dei numeri di 100 cifre, sono 10.000 moltiplicazioni.

No, un algoritmo O (n) non significa che eseguirà un'operazione su ciascun elemento. La notazione Big-O ti dà un modo per parlare di & Quot; speed & Quot; di te algoritmo indipendente dalla tua macchina reale.

O (n) significa che il tempo impiegato dall'algoritmo aumenta linearmente all'aumentare dell'input. O (n ^ 2) significa che il tempo impiegato dall'algoritmo cresce come il quadrato dell'input. E così via.

Il modo in cui ci penso è che hai il compito di ripulire un problema causato da un cattivo malvagio V che sceglie N e devi stimare quanto tempo ci vorrà per risolvere il tuo problema quando aumenta N.

O (1) - > l'aumento di N in realtà non fa alcuna differenza

O (log (N)) - > ogni volta che V raddoppia N, è necessario dedicare un ulteriore periodo di tempo T per completare l'attività. V raddoppia nuovamente N e tu spendi lo stesso importo.

O (N) - > ogni volta che V raddoppia N, passi il doppio del tempo.

O (N ^ 2) - > ogni volta che V raddoppia N, passi 4 volte più tempo. (non è giusto !!!)

O (N log (N)) - > ogni volta che V raddoppia N, passi il doppio del tempo più un po 'di più.

Questi sono limiti di un algoritmo; gli informatici vogliono descrivere quanto tempo ci vorrà per grandi valori di N. (che diventa importante quando si stanno prendendo in considerazione numeri usati nella crittografia - se i computer accelerano di un fattore 10, quanti più bit fanno devi assicurarti che ci vorranno ancora 100 anni per infrangere la tua crittografia e non solo 1 anno?)

Alcuni dei limiti possono avere espressioni strane se fanno la differenza per le persone coinvolte. Ho visto cose come O (N log (N) log (log (N)) da qualche parte in Knuth's Art of Computer Programming per alcuni algoritmi. (non ricordo quale di quelli in cima alla mia testa)

Una cosa che non è stata ancora toccata per qualche motivo:

Quando vedi algoritmi con cose come O (2 ^ n) o O (n ^ 3) o altri valori cattivi spesso significa che dovrai accettare una risposta imperfetta al tuo problema per ottenere prestazioni accettabili .

Soluzioni corrette che esplodono in questo modo sono comuni quando si affrontano problemi di ottimizzazione. Una risposta quasi corretta consegnata in un lasso di tempo ragionevole è meglio di una risposta corretta fornita molto tempo dopo che la macchina è decaduta in polvere.

Considera gli scacchi: non so esattamente quale sia la soluzione corretta, ma è probabilmente qualcosa come O (n ^ 50) o anche peggio. È teoricamente impossibile per qualsiasi computer calcolare effettivamente la risposta corretta - anche se si utilizza ogni particella nell'universo come elemento di calcolo che esegue un'operazione nel minor tempo possibile per la vita dell'universo, rimangono ancora molti zeri . (Se un computer quantistico può risolverlo è un'altra questione.)

Il " Intuitition " dietro Big-O

Immagina un " concorrenza " tra due funzioni su x, mentre x si avvicina all'infinito: f (x) e g (x).

Ora, se da qualche punto in poi (alcune x) una funzione ha sempre un valore più alto dell'altra, allora chiamiamo questa funzione " fast " rispetto all'altro.

Quindi, per esempio, se per ogni x > 100 vedi che f (x) & Gt; g (x), quindi f (x) è " più veloce " di g (x).

In questo caso diremmo g (x) = O (f (x)). f (x) pone una sorta di " limite di velocità " di sorta per g (x), poiché alla fine lo supera e lo lascia indietro per sempre.

Questa non è esattamente la definizione di notazione big-O , che afferma anche che f (x) deve essere maggiore di C * g (x) per una C costante (che è solo un altro modo per dire che non puoi aiutare g (x) a vincere la competizione moltiplicandola per un fattore costante - f (x) vincerà sempre alla fine). La definizione formale utilizza anche valori assoluti. Ma spero di essere riuscito a renderlo intuitivo.

  • E qualcuno deve fumare crack per scrivere una O (x!)?

No, usa solo Prolog. Se scrivi un algoritmo di ordinamento in Prolog semplicemente descrivendo che ogni elemento dovrebbe essere più grande del precedente e lasciando che il backtracking faccia l'ordinamento per te, sarà O (x!). Conosciuto anche come & Quot; permutazione sort & Quot ;.

Mi piace la risposta di don neufeld, ma penso di poter aggiungere qualcosa su O (n log n).

Un algoritmo che utilizza una semplice strategia di divisione e conquista sarà probabilmente O (log n). L'esempio più semplice di ciò è trovare qualcosa in un elenco ordinato. Non si inizia all'inizio e si esegue la ricerca. Vai a metà, decidi se andare avanti o indietro, saltare a metà strada fino all'ultimo posto che hai guardato e ripeterlo fino a trovare l'oggetto che stai cercando.

Se guardi gli algoritmi quicksort o mergesort, vedrai che entrambi adottano l'approccio di dividere l'elenco per essere ordinati a metà, ordinando ogni metà (usando lo stesso algoritmo, ricorsivamente), e quindi ricombinando le due metà . Questo tipo di strategia ricorsiva di divisione e conquista sarà O (n log n).

Se ci pensi attentamente, vedrai che quicksort esegue un algoritmo di partizionamento O (n) su tutti gli n elementi, quindi un partizionamento O (n) due volte su n / 2 elementi, quindi 4 volte su n / 4 elementi, ecc ... fino ad arrivare a n partizioni su 1 elemento (che è degenerato). Il numero di volte che dividi n a metà per arrivare a 1 è approssimativamente log n, e ogni passaggio è O (n), quindi la divisione e la conquista ricorsive è O (n log n). Mergesort costruisce l'altro modo, iniziando con n ricombinazioni di 1 oggetto e finendo con 1 ricombinazione di n oggetti, dove la ricombinazione di due elenchi ordinati è O (n).

Per quanto riguarda il fumo di crack per scrivere un algoritmo O (n!), lo sei a meno che tu non abbia scelta. Si ritiene che il problema del venditore ambulante di cui sopra sia uno di questi problemi.

La maggior parte dei libri di Jon Bentley (ad es. Programming Pearls ) trattano queste cose in un modo davvero pragmatico. Questo discorso tenuto da lui include una di queste analisi di un quicksort.

Sebbene non sia del tutto rilevante per la domanda, Knuth ha escogitato un idea interessante : insegnare la notazione Big-O nelle classi di calcolo delle scuole superiori, anche se trovo questa idea piuttosto eccentrica.

Pensa a come impilare i blocchi lego (n) in verticale e saltarci sopra.

O (1) significa che ad ogni passo non fai nulla. L'altezza rimane la stessa.

O (n) significa ad ogni passo, impilare blocchi c, dove c1 è una costante.

O (n ^ 2) significa ad ogni passo, impilare c2 x n blocchi, dove c2 è una costante e n è il numero di blocchi impilati.

O (nlogn) significa ad ogni passo, impilare c3 x n x log n blocchi, dove c3 è una costante e n è il numero di blocchi impilati.

Per capire O (n log n), ricorda che log n significa log-base-2 di n. Quindi guarda ogni parte:

O (n) è, più o meno, quando si opera su ciascun elemento dell'insieme.

O (log n) è quando il numero di operazioni è lo stesso dell'esponente a cui si alza 2, per ottenere il numero di elementi. Una ricerca binaria, ad esempio, deve tagliare l'insieme in mezzo registro n volte.

O (n log n) è una combinazione & # 8211; stai facendo qualcosa sulla falsariga di una ricerca binaria per ogni elemento nel set. I tipi efficienti operano spesso eseguendo un ciclo per articolo e in ciascun ciclo eseguendo una buona ricerca per trovare il posto giusto per mettere in questione l'oggetto o il gruppo. Quindi n * log n.

Solo per rispondere alla coppia di commenti sul mio post sopra:

Domenic - Sono su questo sito e me ne importa. Non per il bene della pedanteria, ma perché noi - come programmatori - in genere ci teniamo alla precisione. L'uso errato della notazione O () nello stile che alcuni hanno fatto qui lo rende in qualche modo insignificante; possiamo anche dire che qualcosa richiede n ^ 2 unità di tempo come O (n ^ 2) secondo le convenzioni qui usate. L'uso di O () non aggiunge nulla. Non è solo una piccola discrepanza tra uso comune e precisione matematica di cui sto parlando, è la differenza tra essere significativi e non.

Conosco molti programmatori eccellenti che usano esattamente questi termini. Dire "oh, siamo programmatori quindi non ci interessa" riduce l'intera impresa.

onebyone - Beh, non proprio, anche se prendo il tuo punto. Non è O (1) per n arbitrariamente grande, che è una specie della definizione di O (). Ciò dimostra semplicemente che O () ha un'applicabilità limitata per n limitato, in cui preferiremmo effettivamente parlare del numero di passi effettuati piuttosto che di un limite su quel numero.

Dì al tuo log di otto anni (n) significa il numero di volte in cui devi tagliare una lunghezza n accedi in due per farlo scendere alla dimensione n = 1: p

O (n log n) di solito è l'ordinamento O (n ^ 2) di solito confronta tutte le coppie di elementi

Supponi di avere un computer in grado di risolvere un problema di una certa dimensione. Ora immagina di poter raddoppiare la performance alcune volte. Quanto più grande è un problema che possiamo risolvere con ogni raddoppio?

Se riusciamo a risolvere un problema di dimensioni doppie, questo è O (n).

Se abbiamo un moltiplicatore che non è uno, è una sorta di complessità polinomiale. Ad esempio, se ogni raddoppio ci consente di aumentare la dimensione del problema di circa il 40%, è O (n ^ 2) e circa il 30% sarebbe O (n ^ 3).

Se aggiungiamo semplicemente alla dimensione del problema, è esponenziale o peggio. Ad esempio, se ogni raddoppio significa che possiamo risolvere un problema 1 più grande, è O (2 ^ n). (Questo è il motivo per cui forzare brutalmente una chiave di cifratura diventa effettivamente impossibile con chiavi di dimensioni ragionevoli: una chiave a 128 bit richiede circa 16 quintilioni di volte più elaborazione di una a 64 bit.)

Ricordi la favola della tartaruga e della lepre (tartaruga e coniglio)?

Nel lungo periodo, la tartaruga vince, ma nel breve periodo vince la lepre.

È come O (logN) (tartaruga) vs. O (N) (lepre).

Se due metodi differiscono nel loro big-O, allora c'è un livello di N al quale uno di loro vincerà, ma big-O non dice nulla su quanto grande sia quel N.

Per rimanere sincero alla domanda posta risponderei alla domanda nel modo in cui risponderei a un bambino di 8 anni

Supponiamo che un venditore di gelati prepari un numero di gelati (diciamo N) di forme diverse disposte in modo ordinato. Vuoi mangiare il gelato che giace in mezzo

Caso 1: - Puoi mangiare un gelato solo se hai mangiato tutti i gelati più piccoli Dovrai mangiare la metà di tutti i gelati preparati (input). La risposta dipende direttamente dalle dimensioni dell'input La soluzione sarà di ordine o (N)

Caso 2: - Puoi mangiare direttamente il gelato nel mezzo

La soluzione sarà O (1)

Caso 3: puoi mangiare un gelato solo se hai mangiato tutti i gelati più piccoli di lui e ogni volta che mangi un gelato permetti a un altro bambino (bambino nuovo ogni volta) di mangiare tutti i suoi gelati Il tempo totale impiegato sarebbe N + N + N ....... (N / 2) volte La soluzione sarà O (N2)

log(n) significa crescita logaritmica.Un esempio potrebbe essere quello di dividere e conquistare algoritmi.Se si dispone di 1000 ordinate di numeri in un array ( ex.3, 10, 34, 244, 1203 ...) e di voler cercare un numero in elenco (trovare la sua posizione), si potrebbe iniziare con il controllo il valore del numero indice 500.Se è inferiore a ciò che si cerca, saltare a 750.Se è superiore a ciò che si cerca, salto in 250.Poi si ripete il processo fino a trovare il valore (e la chiave).Ogni volta che salta la metà lo spazio di ricerca, siamo in grado di abbattere distanza di test molti altri valori, poiché sappiamo che il numero 3004 non può essere al di sopra di numero 5000 (ricordate, è un elenco ordinato).

n log(n), allora significa che n * log(n).

Proverò a scrivere una spiegazione per un vero bambino di otto anni, a parte termini tecnici e nozioni matematiche.

  

Come esattamente cosa farebbe un'operazione O(n^2)?

Se partecipi a una festa e ci sono n persone nella festa incluso te. Quante strette di mano sono necessarie affinché tutti abbiano stretto la stretta di mano a tutti gli altri, dato che le persone probabilmente dimenticheranno chi hanno stretto la stretta di mano a un certo punto.

Nota: questo è approssimativo a un rendimento simplex n(n-1) che è abbastanza vicino a n^2.

  

E cosa diavolo significa se un'operazione è O(n log(n))?

La tua squadra del cuore ha vinto, sono in fila e ci sono n * log n to the base 10 giocatori nella squadra. Quante frustate ti porterebbe a stringere la mano a ogni giocatore, dato che ti frullerai ognuna più volte, quante volte, quante cifre ci sono nel numero di giocatori O(x!).

Nota: questo produrrà x.

  

E qualcuno deve fumare crack per scrivere un 1?

Sei un bambino ricco e nel tuo guardaroba ci sono molti panni, ci sono 2 cassetti per ogni tipo di abbigliamento, i cassetti sono uno accanto all'altro, il primo cassetto ha 1 articolo, ogni cassetto ha tanti vestiti come nel cassetto a sinistra e uno in più, quindi hai qualcosa come (x-1) cappello, number of children = depth parrucche, .. 1 * 2 * 3 * .. * x pantaloni, quindi <=> camicie. Ora, in quanti modi puoi vestirti usando un singolo oggetto per ogni cassetto.

Nota: questo esempio rappresenta il numero di foglie in un albero decisionale in cui <=>, che viene eseguito tramite <=>

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top