Si tratta di una "Regola" corretta per l'identificazione della notazione "Big O" di un algoritmo?

29

Ho imparato di più su Big O Notation e su come calcolarlo in base a come viene scritto un algoritmo. Mi sono imbattuto in un interessante insieme di "regole" per il calcolo di un algoritmo di notazione Big O e volevo vedere se sono sulla strada giusta o fuori strada.

Notazione O grande: N

function(n) {
    For(var a = 0; i <= n; i++) { // It's N because it's just a single loop
        // Do stuff
    }
}

Notazione O grande: N 2

function(n, b) {
    For(var a = 0; a <= n; a++) {
        For(var c = 0; i <= b; c++) { // It's N squared because it's two nested loops
            // Do stuff
        }
    }
}

Notazione O grande: 2N

function(n, b) {
    For(var a = 0; a <= n; a++) {
        // Do stuff
    }
    For(var c = 0; i <= b; c++) { // It's 2N the loops are outside each other
        // Do stuff
    }
}

Notazione O grande: NLogN

function(n) {
    n.sort(); // The NLogN comes from the sort?
    For(var a = 0; i <= n; i++) {
        // Do stuff
    }
}

I miei esempi e la successiva notazione sono corretti? Ci sono ulteriori notazioni di cui dovrei essere a conoscenza?

    
posta Levi Hackwith 09.04.2013 - 15:51
fonte

5 risposte

26

Formalmente, la notazione O grande descrive il grado di complessità.

Per calcolare la notazione O grande:

  1. identifica la formula per la complessità dell'algoritmo. Diciamo, per esempio, due anelli con un altro annidato all'interno, poi altri tre anelli non nidificati: 2N² + 3N
  2. rimuovi tutto tranne il termine più alto: 2N²
  3. rimuovi tutte le costanti:

In altre parole due anelli con un altro nidificato all'interno, quindi altri tre loop non nidificati è O (N²)

Questo ovviamente presuppone che ciò che hai nei tuoi loop sono semplici istruzioni. Se per esempio c'è sort() all'interno del ciclo, dovrai moltiplicare la complessità del ciclo per la complessità dell'implementazione sort() utilizzata dalla tua lingua / libreria sottostante.

    
risposta data 09.04.2013 - 16:08
fonte
6

Se vuoi analizzare questi algoritmi devi definire // dostuff, in quanto ciò può davvero cambiare il risultato. Supponiamo che dostuff richieda un numero O (1) di operazioni costante.

Ecco alcuni esempi con questa nuova notazione:

Per il tuo primo esempio, l'attraversamento lineare: questo è corretto!

O (N):

for (int i = 0; i < myArray.length; i++) {
    myArray[i] += 1;
}

Perché è lineare (O (n))? Quando aggiungiamo ulteriori elementi all'input (array) la quantità di operazioni che si verificano aumenta proporzionale al numero di elementi che aggiungiamo.

Quindi se ci vuole un'operazione per incrementare un intero da qualche parte nella memoria, possiamo modellare il lavoro che il ciclo fa con f (x) = 5x = 5 operazioni aggiuntive. Per 20 elementi aggiuntivi, eseguiamo 20 operazioni aggiuntive. Un singolo passaggio di un array tende ad essere lineare. Così sono algoritmi come bucket sort, che sono in grado di sfruttare la struttura dei dati per fare un ordinamento in un singolo passaggio di un array.

Anche il tuo secondo esempio sarebbe corretto e assomiglia a questo:

O (N ^ 2):

for (int i = 0; i < myArray.length; i++) {
    for (int j = 0; j < myArray.length; j++) {
        myArray[i][j] += 1;
    }
}

In questo caso, per ogni elemento aggiuntivo nel primo array, io, dobbiamo elaborare TUTTO di j. Aggiungere 1 a I aggiunge effettivamente (lunghezza di j) a j. Quindi, hai ragione! Questo modello è O (n ^ 2), o nel nostro esempio è in realtà O (i * j) (o n ^ 2 se i == j, che è spesso il caso con operazioni a matrice o una struttura dati quadrata.

Il tuo terzo esempio è dove le cose cambiano a seconda dei dostuff; Se il codice è scritto e fa roba è una costante, in realtà è solo O (n) perché abbiamo 2 passaggi di una matrice di dimensione n e 2n si riduce a n. Gli anelli che si trovano l'uno all'esterno dell'altro non sono il fattore chiave che può produrre codice 2 ^ n; ecco un esempio di una funzione che è 2 ^ n:

var fibonacci = function (n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    else {
        return (fibonacci(n-2) + fibonacci(n-1));
    }
}

Questa funzione è 2 ^ n, poiché ogni chiamata alla funzione produce DUE chiamate aggiuntive alla funzione (Fibonacci). Ogni volta che chiamiamo la funzione, la quantità di lavoro che dobbiamo fare raddoppia! Cresce molto velocemente, come se si tagli la testa da un'idra e ne spuntassero due nuovi ogni volta!

Per il tuo esempio finale, se stai usando un ordinamento nlgn come merge-sort hai ragione che questo codice sarà O (nlgn). Tuttavia, è possibile sfruttare la struttura dei dati per sviluppare ordinamenti più rapidi in situazioni specifiche (ad esempio, oltre un intervallo di valori noto e limitato come 1-100). È corretto pensare, tuttavia, che il codice di ordine più elevato prevalga; quindi se un ordinamento O (nlgn) è vicino a qualsiasi operazione che richiede meno di tempo O (nlgn), la complessità temporale totale sarà O (nlgn).

In JavaScript (almeno in Firefox) l'ordinamento predefinito in Array.prototype.sort () è infatti MergeSort, quindi stai guardando O (nlgn) per lo scenario finale.

    
risposta data 06.04.2016 - 01:52
fonte
1

Il tuo secondo esempio (anello esterno da 0 a n , anello interno da 0 a b ) sarebbe O ( nb ), non O ( n 2 ). La regola è che stai calcolando qualcosa n volte, e per ognuno di questi stai calcolando qualcos'altro b volte, quindi la crescita di questa funzione dipende unicamente dalla crescita di n * b .

Il tuo terzo esempio è solo O ( n ) - puoi rimuovere tutte le costanti dal momento che non crescono con n e la crescita è ciò che la notazione Big-O è tutta circa.

Come per il tuo ultimo esempio, sì, la tua notazione Big-O verrà certamente dal metodo sort che sarà, se è basato sul confronto (come è tipicamente il caso), nella sua forma più efficiente, O (< i> n * logn ).

    
risposta data 09.04.2013 - 22:47
fonte
0

Ricorda che questa è una rappresentazione approssimativa del tempo di esecuzione. La "regola del pollice" è approssimativa perché è imprecisa ma fornisce una buona approssimazione del primo ordine a scopo di valutazione.

Il tempo di esecuzione effettivo dipenderà dalla quantità di spazio su heap, dalla velocità del processore, dal set di istruzioni, dall'uso di operatori di incremento di prefissi o post-fix, ecc., yadda. Un'analisi corretta in fase di esecuzione consentirà la determinazione dell'accettazione, ma la conoscenza delle nozioni di base consente di programmare fin dall'inizio.

Sono d'accordo sul fatto che sei sulla strada giusta per capire come Big-O viene razionalizzato da un libro di testo a un'applicazione pratica. Questo potrebbe essere il difficile ostacolo da superare.

Il tasso di crescita asintotico diventa importante su insiemi di dati di grandi dimensioni e programmi di grandi dimensioni, pertanto per esempi tipici si dimostra che non è importante per la sintassi e la logica corrette.

    
risposta data 09.04.2013 - 19:25
fonte
-1

Big oh, per definizione significa: per una funzione f (t) esiste una funzione c * g (t) dove c è una costante arbitraria tale che f (t) < = c * g (t) per t > n dove n è una costante arbitraria, quindi f (t) esiste in O (g (t)). Si tratta di una notazione matematica che viene utilizzata in informatica per analizzare algoritmi. Se ti confonderai ti consiglierei di esaminare le relazioni di chiusura, in questo modo puoi vedere in una visione più dettagliata come questi algoritmi ottengono questi valori big oh.

Alcune conseguenze di questa definizione: O (n) è in realtà congruente a O (2n).

Inoltre ci sono molti diversi tipi di algoritmi di ordinamento. Il valore minimo di Big-Oh per un tipo di confronto è O (nlogn), tuttavia c'è un sacco di generi con il peggiore big-oh. Ad esempio, l'ordinamento della selezione ha O (n ^ 2). Qualche ordinamento senza confronto potrebbe mai avere valori big-oh migliori. Un ordinamento a benna, per esempio, ha O (n).

    
risposta data 10.04.2013 - 00:44
fonte

Leggi altre domande sui tag