Che cos'è la notazione Big O? Lo usi? [duplicare]

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

Domanda

    

Questa domanda ha già una risposta qui:

         

Che cos'è la notazione Big O? Lo usi?

Mi è sfuggita questa lezione universitaria, immagino: D

Qualcuno lo usa e fornisce alcuni esempi di vita reale di dove lo hanno usato?

Vedi anche:

Big-O per otto anni?
Big O, come si calcola / approssimazione?
Hai applicato la teoria della complessità computazionale nella vita reale?

È stato utile?

Soluzione

Una cosa importante che la maggior parte delle persone dimentica quando parla di Big-O, quindi sento il bisogno di menzionarlo:

Non puoi usare Big-O per confrontare la velocità di due algoritmi. Big-O dice solo quanto più lentamente un algoritmo otterrà (approssimativamente) se raddoppi il numero di elementi elaborati o quanto più veloce otterrà se riduci il numero a metà.

Tuttavia, se hai due algoritmi completamente diversi e uno ( A ) è O (n ^ 2) e l'altro ( B ) è O (log n) , non si dice che A sia più lento di B . In realtà, con 100 articoli, A potrebbe essere dieci volte più veloce di B . Dice solo che con 200 elementi, A diventerà più lento del fattore n ^ 2 e B diventerà più lento del fattore log n . Pertanto, se esegui il benchmark di entrambi e sai quanto tempo impiega A per elaborare 100 articoli e quanto tempo B richiede per gli stessi 100 articoli e A è più veloce di B , puoi calcolare a quale quantità di elementi B supererà A in velocità (poiché la velocità di < code> B diminuisce molto più lentamente di quello di A , supererà A prima o poi - questo è sicuro).

Altri suggerimenti

La notazione O grande indica il fattore limitante di un algoritmo. È un'espressione semplificata di come il tempo di esecuzione di un algoritmo si ridimensiona rispetto all'input.

Ad esempio (in Java): 

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

Ora pensa a cosa sta effettivamente facendo. Sta attraversando ogni carattere di input e sommandoli insieme. Questo sembra semplice. Il problema è che String è immutabile . Quindi ogni volta che aggiungi una lettera alla stringa devi creare una nuova stringa. Per fare questo devi copiare i valori dalla vecchia stringa nella nuova stringa e aggiungere il nuovo carattere.

Ciò significa che copierai la prima lettera n volte in cui n è il numero di caratteri nell'input. Copierai il carattere n-1 volte, quindi in totale ci saranno copie di (n-1) (n / 2) .

Questo è (n ^ 2-n) / 2 e per la notazione Big O usiamo solo il fattore di magnitudine più alto (di solito) e lasciamo cadere tutte le costanti che si moltiplicano per esso e finiamo con O (n ^ 2) .

L'uso di qualcosa come un StringBuilder sarà lungo le linee di O (nLog (n)). Se si calcola il numero di caratteri all'inizio e si imposta la capacità di StringBuilder , è possibile ottenere che sia O (n) .

Quindi se avessimo 1000 caratteri di input, il primo esempio eseguirà circa un milione di operazioni, StringBuilder eseguirà 10.000 e StringBuilder con setCapacity eseguirà 1000 operazioni per fare la stessa cosa. Questa è una stima approssimativa, ma la notazione O (n) riguarda ordini di grandezza, non tempo di esecuzione esatto.

Non è qualcosa che uso per dire su base regolare. È, tuttavia, costantemente nella parte posteriore della mia mente quando provo a capire l'algoritmo migliore per fare qualcosa.

Una domanda molto simile è già stata posta a Big-O per gli otto anni? . Spero che le risposte qui rispondano alla tua domanda, anche se la domanda che ci ha fatto aveva un po 'di conoscenza matematica su tutto ciò che potresti non avere così chiarire se hai bisogno di una spiegazione più completa.

Ogni programmatore dovrebbe essere consapevole di cosa sia la notazione Big O, come si applica alle azioni con strutture di dati e algoritmi comuni (e quindi scegliere il DS e l'algoritmo corretti per il problema che stanno risolvendo) e come calcolarlo per il loro propri algoritmi.

1) È un ordine di misurazione dell'efficienza di un algoritmo quando si lavora su una struttura di dati.

2) Azioni come 'aggiungi' / 'ordina' / 'rimuovi' possono richiedere diversi periodi di tempo con diverse strutture di dati (e algoritmi), ad esempio 'aggiungi' e 'trova' sono O (1) per una hashmap , ma O (log n) per un albero binario. L'ordinamento è O (nlog n) per QuickSort, ma O (n ^ 2) per BubbleSort, quando si ha a che fare con un array semplice.

3) I calcoli possono essere eseguiti osservando la profondità del loop dell'algoritmo in generale. Nessun loop, O (1), loop che scorre su tutto il set (anche se scoppiano ad un certo punto) O (n). Se il loop dimezza lo spazio di ricerca su ogni iterazione? O (registro n). Prendi la O () più alta per una sequenza di loop e moltiplica la O () quando annidi i loop.

Sì, è più complesso di così. Se sei veramente interessato, prendi un libro di testo.

La notazione 'Big-O' viene utilizzata per confrontare i tassi di crescita di due funzioni di una variabile (diciamo n) quando n diventa molto grande. Se la funzione f cresce molto più rapidamente della funzione g, diciamo che g = O (f) implica che per n abbastanza grande, f sempre sarà più grande di g fino a un fattore di ridimensionamento.

Si scopre che questa è un'idea molto utile nell'informatica e in particolare nell'analisi degli algoritmi, perché spesso ci occupiamo precisamente dei tassi di crescita delle funzioni che rappresentano, ad esempio, il tempo impiegato da due diversi algoritmi. Molto grossolanamente, possiamo determinare che un algoritmo con runtime t1 (n) è più efficiente di un algoritmo con runtime t2 (n) se t1 = O (t2) per n abbastanza grande che è in genere la 'dimensione' di il problema - come la lunghezza dell'array o il numero di nodi nel grafico o altro.

Questa clausola, che n diventa abbastanza grande, ci permette di fare molti trucchi utili. Forse il più usato è che puoi semplificare le funzioni fino ai termini in più rapida crescita. Ad esempio n ^ 2 + n = O (n ^ 2) perché quando n diventa abbastanza grande, il termine n ^ 2 diventa molto più grande di n che il termine n è praticamente insignificante. Quindi possiamo lasciarlo da parte.

Tuttavia, ciò significa che la notazione big-O è meno utile per la piccola n, perché i termini di crescita più lenta che abbiamo dimenticato sono ancora abbastanza significativi da influire sul tempo di esecuzione.

Ciò che abbiamo ora è uno strumento per confrontare i costi di due diversi algoritmi e una scorciatoia per dire che uno è più veloce o più lento dell'altro. La notazione Big-O può essere abusata, il che è un peccato perché è già abbastanza impreciso! Esistono termini equivalenti per dire che una funzione cresce meno rapidamente di un'altra e che due funzioni crescono allo stesso ritmo.

Oh, e lo uso? Sì, sempre - quando sto cercando di capire quanto sia efficiente il mio codice, fornisce una grande approssimazione "back-of-the-envelope" al costo.

Il " Intuitition " dietro Big-O

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

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

Quindi, per esempio, se per ogni x > 100 vedi che f (x) > 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.

Potrebbe anche valere la pena considerare che la complessità di molti algoritmi si basa su più di una variabile, in particolare nei problemi multidimensionali. Ad esempio, di recente ho dovuto scrivere un algoritmo per quanto segue. Dato un insieme di n punti e m poligoni, estrai tutti i punti che si trovano in uno qualsiasi dei poligoni. La complessità si basa su due variabili conosciute, n e m, e l'ignoto di quanti punti ci sono in ciascun poligono. La notazione O grande qui è un po 'più coinvolta di O (f (n)) o persino O (f (n) + g (m)). Big O è buono quando hai a che fare con un gran numero di oggetti omogenei, ma non aspettarti che sia sempre così.

Vale anche la pena notare che il numero effettivo di iterazioni sui dati dipende spesso dai dati. Quicksort di solito è veloce, ma fornisce dati preordinati e rallenta. L'alogoritmo dei miei punti e poligoni è finito abbastanza velocemente, vicino a O (n + (m log (m)), in base alla conoscenza precedente di come i dati sarebbero stati probabilmente organizzati e alle dimensioni relative di n e m. male su dati organizzati in modo casuale di dimensioni relative diverse.

Un'ultima cosa da considerare è che spesso c'è un compromesso diretto tra la velocità di un algoritmo e la quantità di spazio che utilizza. Ordinamento di fori di piccione ne è un ottimo esempio. Tornando ai miei punti e poligoni, diciamo che tutti i miei poligoni erano semplici e veloci da disegnare, e che potevo disegnarli riempiti sullo schermo, diciamo in blu, in un periodo di tempo fisso ciascuno. Quindi, se disegno i miei poligoni su uno schermo nero, ci vorrebbe O (m) tempo. Per verificare se uno dei miei n punti fosse in un poligono, controllo semplicemente se il pixel in quel punto è verde o nero. Quindi il controllo è O (n) e l'analisi totale è O (m + n). Il rovescio della medaglia ovviamente è che ho bisogno di spazio pressoché infinito se ho a che fare con coordinate del mondo reale con precisione millimetrica ....

Potrebbe anche valere la pena considerare il tempo ammortizzato , piuttosto che il caso peggiore. Ciò significa, ad esempio, che se si esegue l'algoritmo n volte, sarà O (1) in media, ma a volte potrebbe essere peggio.

Un buon esempio è una tabella dinamica, che è fondamentalmente una matrice che si espande man mano che aggiungi elementi ad essa. Un'implementazione ingenua aumenterebbe le dimensioni dell'array di 1 per ogni elemento aggiunto, il che significa che tutti gli elementi devono essere copiati ogni volta che ne viene aggiunto uno nuovo. Ciò comporterebbe un algoritmo O (n 2 ) se si concatenasse una serie di array usando questo metodo. Un'alternativa è raddoppiare la capacità dell'array ogni volta che è necessario più spazio di archiviazione. Anche se l'aggiunta è talvolta un'operazione O (n) , dovrai solo copiare gli elementi O (n) per ogni elemento n aggiunto, quindi l'operazione è O (1) in media. Ecco come vengono implementate cose come StringBuilder o std :: vector .

Che cos'è la notazione Big O?

La notazione O grande è un metodo per esprimere la relazione tra molti passaggi richiesti da un algoritmo in relazione alla dimensione dei dati di input. Questa è definita complessità algoritmica. Ad esempio, l'ordinamento di un elenco di dimensioni N mediante Bubble Sort richiede O (N ^ 2) passaggi.

Uso la notazione Big O?

Uso occasionalmente la notazione Big O per trasmettere complessità algoritmica ai colleghi programmatori. Uso sempre la teoria di base (ad es. Tecniche di analisi Big O) quando penso a quali algoritmi usare.

Esempi concreti?

Ho usato la teoria dell'analisi della complessità per creare algoritmi per strutture di dati di stack efficienti che non richiedono riallocazione della memoria e che supportano il tempo medio di O (N) per l'indicizzazione. Ho usato la notazione Big O per spiegare l'algoritmo ad altre persone. Ho anche usato l'analisi della complessità per capire quando è possibile ordinare in modo lineare O (N).

Da Wikipedia .....

La notazione O grande è utile quando si analizzano gli algoritmi per l'efficienza. Ad esempio, il tempo (o il numero di passaggi) necessario per completare un problema di dimensione n potrebbe essere considerato T (n) = 4n & # 178; & # 8722; 2n + 2.

Man mano che n cresce, n & # 178; il termine verrà a dominare, in modo che tutti gli altri termini possano essere trascurati & # 8212; per esempio quando n = 500, il termine 4n & # 178; è 1000 volte più grande del termine 2n. Ignorare quest'ultimo avrebbe effetti trascurabili sul valore dell'espressione per la maggior parte degli scopi.

Ovviamente non l'ho mai usato ..

Dovresti essere in grado di valutare la complessità di un algoritmo. Questo combinato con una conoscenza di quanti elementi ci vorranno può aiutarti a determinare se non è adatto al suo compito.

Indica quante iterazioni ha un algoritmo nel peggiore dei casi.

per cercare un elemento in un elenco, è possibile attraversare l'elenco fino a quando non si ottiene l'elemento. Nel peggiore dei casi, l'articolo si trova nell'ultimo posto.

Diciamo che ci sono n elementi nella lista. Nel peggiore dei casi prendi n iterazioni. Nella notazione Big O è O (n).

Indica in realtà quanto sia efficiente un algoritmo.

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