Big O, come si calcola/approssimativo?

https://stackoverflow.com/questions/3255

08-06-2019
|

Domanda

La maggior parte delle persone con una laurea in CS saprà certamente cosa Grande O sta per.Essa ci aiuta a misurare il grado di (in)efficienza di un algoritmo è, e se si sa in in quale categoria il problema che si sta tentando di risolvere pone in si può capire se è ancora possibile spremere il massimo delle prestazioni.¹

Ma io sono curioso, come fare si calcolare o approssimare la complessità di algoritmi?

¹ _{ma, come si dice, non esagerare, precoce l'ottimizzazione è la radice di tutti i mali, e ottimizzazione senza un giustificato motivo dovrebbe meritare questo nome.}

Soluzione

Farò del mio meglio per spiegare qui in termini semplici, ma essere avvertito che questo argomento prende i miei studenti un paio di mesi e, infine, cogliere.Potete trovare ulteriori informazioni nel Capitolo 2 del Strutture di dati e Algoritmi in Java libro.

Non c'è procedimento meccanico che può essere utilizzato per ottenere il BigOh.

Come un "libro di ricette", per ottenere il BigOh da un pezzo di codice è necessario prima di rendersi conto che si sta creando una formula matematica per contare il numero di passaggi dei calcoli vengono eseguiti dato un input di una certa dimensione.

Lo scopo è semplice:per confrontare gli algoritmi da un punto di vista teorico, senza la necessità di eseguire il codice.Minore è il numero di passi, il più veloce algoritmo.

Per esempio, supponiamo di avere questo pezzo di codice:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

Questa funzione restituisce la somma di tutti gli elementi della matrice, e si desidera creare una formula per contare il complessità computazionale della funzione:

Number_Of_Steps = f(N)

Così abbiamo f(N), una funzione per contare il numero di passi computazionali.L'input della funzione è la dimensione della struttura di processo.Significa che questa funzione è definita come:

Number_Of_Steps = f(data.length)

Il parametro N prende il data.length valore.Ora abbiamo bisogno l'effettiva definizione della funzione f().Questo viene fatto dal codice sorgente, in cui ogni linea interessante è numerato da 1 a 4.

Ci sono molti modi per calcolare il BigOh.Da questo punto in avanti stiamo andando a supporre che ogni frase che non dipende dalla dimensione dei dati in ingresso richiede una costante C il numero di passi computazionali.

Stiamo per aggiungere il numero di passaggi della funzione, né la dichiarazione di variabile locale né l'istruzione return dipende dalla dimensione del data array.

Il che significa che le linee 1 e 4 C quantità di passaggi, e la funzione è un po ' come questo:

f(N) = C + ??? + C

La parte successiva è quello di definire il valore della for istruzione.Ricordate che stiamo contando il numero di passi computazionali, il che significa che il corpo del for istruzione viene eseguita N volte.Che è la stessa come l'aggiunta di C, N tempi:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

Non c'è meccanico regola di contare quante volte il corpo del for viene eseguita, è necessario per il conteggio guardando a quello che fa il codice che fare.Per semplificare i calcoli, siamo ignorando la variabile di inizializzazione, condizione e di incremento parti del for istruzione.

Per ottenere il reale BigOh abbiamo bisogno di Asintotica analisi della funzione.Questo è più o meno come questo:

Togliere tutte le costanti C.
Da f() ottenere i polynomium nella sua standard form.
Dividere i termini della polynomium e ordina il tasso di crescita.
Tenere quello che cresce più grande, quando N approcci infinity.

Il nostro f() dispone di due termini:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Per togliere tutti i C le costanti e le parti ridondanti:

f(N) = 1 + N ^ 1

Dal momento che il termine ultimo è quello che cresce più grande, quando f() che tende a infinito (si pensi su limiti) questo è il BigOh argomento, e il sum() la funzione ha un BigOh di:

O(N)

Ci sono alcuni trucchi per risolvere alcuni difficili quelli:utilizzare sommatorie ogni volta che si può.

Come esempio, questo codice può essere facilmente risolto utilizzando sommatorie:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

La prima cosa che doveva essere fatta è l'ordine di esecuzione di foo().Mentre il solito sta per essere O(1), è necessario chiedere al vostro professori su di esso. O(1) significa (quasi quasi) costante C, indipendentemente dalla grandezza N.

Il for dichiarazione sulla sentenza numero uno è difficile.Mentre l'indice termina a 2 * N, l'incremento è fatto da due.Che significa che il primo for viene eseguito solo N passi, e abbiamo bisogno di dividere il conto di due.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

La frase numero due è ancora più complicato in quanto dipende dal valore di i.Date un'occhiata:l'indice assume valori:0, 2, 4, 6, 8, ..., 2 * N, e la seconda for eseguito:N volte il primo, N - 2 la seconda, N - 4, il terzo...fino a N / a 2 stadi, in cui il secondo for non viene mai eseguito.

Sulla formula, che significa:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

Ancora una volta, siamo di conteggio il numero di passi.E, per definizione, ogni somma deve sempre cominciare a uno, e termina in un numero maggiore o uguale a uno.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Stiamo supponendo che foo() è O(1) e prende C passaggi).

Abbiamo un problema qui:quando i assume il valore N / 2 + 1 verso l'alto, l'interno Sommatoria termina in corrispondenza di un numero negativo!E ' impossibile e sbagliato.Abbiamo bisogno di dividere la somma in due, essendo il punto fondamentale momento i prende N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

Dal momento che il momento cruciale i > N / 2, l'interno for non vengono eseguiti, e stiamo assumendo una costante C di esecuzione complessità sul suo corpo.

Ora la sommatoria può essere semplificato utilizzando alcune regole d'identità:

Sommatoria(w da 1 a N)( C ) = N * C
Sommatoria(w da 1 a N) A (+/-) B ) = Sommatoria(w da 1 a N)( A ) (+/-) la Somma(w da 1 a N)( B )
Sommatoria(w da 1 a N)( w * C ) = C * Sommatoria(w da 1 a N)( w ) (C è una costante, indipendente w)
Sommatoria(w da 1 a N)( w ) = (N * (N + 1)) / 2

L'applicazione di alcune algebra:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

E il BigOh è:

O(N²)

Altri suggerimenti

O grande dà il limite superiore per il tempo la complessità di un algoritmo.Di solito è usato in combinazione con l'elaborazione di set di dati (liste) ma può essere utilizzato altrove.

Alcuni esempi di come viene utilizzato nel codice C.

Supponiamo di avere un array di n elementi

int array[n];

Se volessimo accedere al primo elemento dell'array questo sarebbe O(1) dal momento che non importa quanto grande sia la matrice è sempre la stessa costante di tempo per ottenere il primo elemento.

x = array[0];

Se volessimo trovare un numero in elenco:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

Questo sarebbe O(n), dal momento che ci sarebbe da far scorrere l'intero elenco a trovare il nostro numero.Il Big-O è ancora in tempo O(n), anche se possiamo trovare il nostro numero prima provare a correre attraverso il ciclo una volta perché il Big-O descrive il limite superiore di un algoritmo (omega è per il limite inferiore e theta è legato).

Quando si arriva a cicli annidati:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

Questo è O(n^2) dal momento che ad ogni passaggio del ciclo esterno ( O(n) ) dobbiamo passare attraverso l'intero elenco di nuovo in modo che il n moltiplicare lasciando a noi con n al quadrato.

Questo è a malapena graffiare la superficie, ma quando si arriva ad analizzare più complessi algoritmi matematici complessi che coinvolgono le prove che entra in gioco.Spero che questo consente di familiarizzare con le nozioni di base di almeno però.

Pur sapendo come capire il Grande O il tempo per il vostro problema particolare è utile conoscere alcune generali dei casi può andare un lungo cammino per aiutare a prendere decisioni in un algoritmo.

Ecco alcuni dei casi più comuni, sollevato da http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1) - di Determinare se un numero è pari o dispari;utilizzando una dimensione costante ricerca di tabella o tabella hash

O(logn) - la Ricerca di un elemento in un array ordinato con un binario di ricerca

O(n) - la Ricerca di un elemento in un elenco non ordinato;l'aggiunta di due n-numeri a due cifre

O(n²) - Moltiplicazione di due n-numeri a due cifre da un semplice algoritmo;l'aggiunta di due n×n matrici;bubble sort o di ordinamento per inserzione

O(n³) - Moltiplicazione di due n×n matrici semplice algoritmo

O(cⁿ) - Trovare l' (esatta) soluzione per il problema del commesso viaggiatore che utilizza la programmazione dinamica;determinare se due logiche istruzioni sono equivalenti usando la forza bruta

O(n!) - Risolvere il problema del commesso viaggiatore tramite brute-force di ricerca

O(nⁿ) - Spesso usato al posto di O(n!) per ricavare semplici formule per la complessità asintotica

Piccolo promemoria:il big O la notazione è usata per indicare il asintotica la complessità (che è, quando la dimensione del problema, che cresce all'infinito), e si nasconde una costante.

Questo significa che tra un algoritmo O(n) e O(n²), il più veloce non è sempre il primo (anche se esiste sempre un valore di n tale che, per problemi di dimensione >n, il primo algoritmo è il più veloce).

Nota che il nascosto costante dipende molto da come la realizzazione!

Inoltre, in alcuni casi, il runtime non è una funzione deterministica del dimensioni n dell'input.Prendere l'ordinamento utilizza quick sort per esempio:il tempo necessario per ordinare un array di n elementi non è costante, ma dipende dalla configurazione iniziale dell'array.

Ci sono diversi tempo di complessità:

Caso peggiore (di solito il più semplice da capire, anche se non sempre molto significativa)
Caso medio (di solito molto più difficile da capire...)
...

Una buona introduzione è Un'Introduzione all'Analisi di Algoritmi R.Sedgewick e P.Flajolet.

Come dici tu, premature optimisation is the root of all evil, e (se possibile) profiling in realtà dovrebbe essere sempre utilizzato quando l'ottimizzazione del codice.Si può anche aiutare a determinare la complessità di algoritmi.

A vedere le risposte qui, credo, possiamo concludere che la maggior parte di noi, infatti, approssimativo ordine di un algoritmo cercando e usare il buon senso invece di calcolare con, per esempio, il master metodo come siamo stati pensati all'università.Detto questo devo aggiungere che anche il professore ci ha incoraggiato (più tardi) effettivamente pensare su di esso invece di calcolo.

Inoltre vorrei aggiungere, come si fa per le funzioni ricorsive:

supponiamo di avere una funzione simile (schema di codice):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

che ricorsivamente calcola il fattoriale di un numero dato.

Il primo passo è quello di cercare di determinare la prestazione caratteristica per il corpo della funzione solo in questo caso, nulla di speciale è fatto nel corpo, solo una moltiplicazione (o il ritorno del valore 1).

Così il prestazioni per il corpo:O(1) (costante).

Accanto provare a determinare questo per il il numero di chiamate ricorsive.In questo caso abbiamo n-1 chiamate ricorsive.

Così il le prestazioni per le chiamate ricorsive è:O(n-1) (ordine n, come abbiamo buttare via l'insignificante parti).

Poi messo quei due insieme e poi hai la performance per tutta la funzione ricorsiva:

1 * (n-1) = O(n)

Pietro, per rispondere il tuo sollevato questioni; il metodo che ho descritto qui effettivamente gestisce abbastanza bene.Ma tenete a mente che questo è ancora un approssimazione e non è un full matematicamente corretta risposta.Il metodo qui descritto è anche uno dei metodi ci hanno insegnato all'università, e se non ricordo male è stato utilizzato per molto più avanzati algoritmi di fattoriale che ho usato in questo esempio.
Ovviamente tutto dipende da quanto bene si può stimare il tempo di esecuzione del corpo della funzione e il numero di chiamate ricorsive, ma che è altrettanto vero per gli altri metodi.

Se il costo è un polinomio, basta tenere il più alto ordine di termine, senza il suo moltiplicatore.E. g.:

O((n/2 + 1)*(n/2)) = O(n²/4 + n/2) = O(n²/4) = O(n²)

Questo non funziona per una serie infinita, è la mente.Non esiste un'unica ricetta per il caso generale, anche se in alcuni casi comuni, le seguenti disuguaglianze applicare:

O(log N) < O(N) < O(N registro N) < O(N²) < O(N^k) < O(eⁿ) < O(n!)

Penso che su di esso in termini di informazioni.Ogni problema è di imparare un certo numero di bit.

Il tuo strumento di base è il concetto di punti di decisione e la loro entropia.L'entropia di un punto di decisione è la media delle informazioni che si possono ottenere.Per esempio, se un programma contiene un punto di decisione con due rami, è l'entropia è la somma delle probabilità di ciascun ramo volte il log₂ dell'inverso della probabilità di quel ramo.Questo è quanto si impara da l'esecuzione di tale decisione.

Per esempio, un if dichiarazione di avere due rami, entrambi ugualmente probabile, ha un'entropia di 1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1.Così la sua entropia è di 1 bit.

Supponiamo che siete alla ricerca di una tabella di N elementi, come N=1024.Che è un 10-bit problema perché il log(1024) = 10 bit.Quindi, se è possibile cercare con SE le istruzioni che sono ugualmente probabili risultati, si dovrebbe prendere 10 decisioni.

Che è quello che si ottiene con la ricerca binaria.

Supponiamo che si sta facendo la ricerca lineare.Si guarda il primo elemento e chiedere se è quello che si desidera.Le probabilità sono 1/1024 che è, e 1023/1024 che non è così.L'entropia di tale decisione è 1/1024*log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * circa 0 = circa 01 bit.Hai imparato molto poco!La seconda decisione non è molto meglio.Che è il motivo per cui la ricerca lineare è così lento.In realtà è esponenziale del numero di bit necessari per imparare.

Supponiamo che si sta facendo di indicizzazione.Supponiamo che la tabella è pre-ordinati in un sacco di bidoni, e usare un po ' di tutti i bit della chiave di indice direttamente la voce della tabella.Se ci sono 1024 bidoni, l'entropia è 1/1024 * log(1024) + 1/1024 * log(1024) + ...per tutti 1024 possibili esiti.Questo è 1/1024 * 10 volte 1024 risultati, o 10 bit di entropia per una operazione di indicizzazione.Che è il motivo per cui l'indicizzazione di ricerca è veloce.

Ora pensa di ordinamento.Si ha N elementi, e si dispone di un elenco.Per ogni elemento, devi cercare la voce che va in lista, e quindi aggiungere alla lista.Così l'ordinamento prende circa N volte il numero di passi di ricerca sottostante.

Così ordinamento in base alle decisioni binarie avere più o meno equamente probabili esiti prendere di O(N log N) passi.Un O(N) algoritmo di ordinamento è possibile se si basa su di indicizzazione di ricerca.

Ho scoperto che quasi tutte algoritmica di problemi di prestazioni, può essere visto in questo modo.

Iniziamo dal principio.

Prima di tutto, accettare il principio che alcune semplici operazioni sui dati può essere fatto in O(1) il tempo, che è, nel tempo che è indipendente dalla dimensione dell'input.Queste operazioni primitive in C consistono in

Le operazioni aritmetiche (ad es.+ o %).
Operazioni logiche (ad esempio, &&).
Le operazioni di confronto (ad esempio, <=).
Struttura di accesso alle operazioni (ad es.indicizzazione matrice come Un[i], o il puntatore fol- che si abbassi con l' -> operatore).
Semplice assegnazione, ad esempio la copia di un valore in una variabile.
Chiamate a funzioni di libreria (ad esempio, scanf, printf).

La motivazione di questo principio richiede uno studio dettagliato di istruzioni per la macchina (primitive gradini) di un tipico computer.Ognuna delle operazioni descritte può essere fatto con un ridotto numero di istruzioni macchina;spesso solo uno o due sono necessarie istruzioni.Di conseguenza, vari tipi di istruzioni in C può essere eseguito in O(1) il tempo, che è, in qualche quantità costante di tempo indipendente di ingresso.Queste semplici includono

Istruzioni di assegnazione, che non comportano chiamate di funzione nelle loro espressioni.
Istruzioni di lettura.
Istruzioni di scrittura che non necessitano di chiamate di funzione per valutare gli argomenti.
Il salto istruzioni break, continue, goto, e il ritorno di espressione, dove espressione non contiene una chiamata di funzione.

In C, per molti anelli sono formati da inizializzare una variabile di indice di un qualche valore, e incremento della variabile di 1 ogni volta tutto il ciclo.Il ciclo for termina quando l'indice raggiunge un limite.Per esempio, il ciclo for

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

utilizza la variabile di indice i.Incrementa i di 1 ogni volta che il giro del circuito, e le iterazioni interrompere quando mi raggiunge n − 1.

Tuttavia, per il momento, concentrarsi sulla forma semplice del ciclo for, in cui il differenza tra il finale e il valore iniziale, diviso per la quantità che la variabile indice viene incrementato ci dice quante volte siamo andati in giro per il ciclo.Il conteggio è esatto, a meno che non ci sono modi per uscire dal loop attraverso un salto di istruzione;si tratta di un limite superiore al numero di iterazioni in ogni caso.

Per esempio, il per-ciclo di iterazione ((n − 1) − 0)/1 = n − 1 times, poiché 0 è il valore iniziale i, n − 1 è il valore più alto raggiunto da i (cioè, quando ho raggiunge n−1, il ciclo si interrompe e non iterazione si verifica con i = n−1), e 1 è aggiunto per io ad ogni iterazione del ciclo.

Nel caso più semplice, in cui il tempo trascorso nel corpo del ciclo è la stessa per ogni iterazione, si può moltiplicare il big-oh limite superiore per il corpo, per il numero di volte il giro del loop.A rigor di termini, dobbiamo quindi aggiungere O(1) tempo di inizializzazione l'indice del ciclo e O(1) il tempo per il primo confronto dell'indice del ciclo con il limite, perché ci prova ancora una volta che siamo andati in giro per il ciclo.Tuttavia, a meno che non è possibile eseguire il ciclo di zero, il tempo per inizializzare il ciclo e test il limite di una volta è un ordine inferiore a termine che può essere eliminato dalla sommatoria regola.

Ora si consideri questo esempio:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

Sappiamo che linea (1) prende O(1) tempo.Chiaramente, siamo andati in giro per il ciclo di n volte, come siamo in grado di determinare sottraendo il limite inferiore limite superiore limite trovato on line (1) e l'aggiunta di 1.Dal momento che il corpo, linea (2), avviene in O(1) ora, possiamo trascurare il il tempo di incremento di j e il tempo per confrontare i j n, entrambi i quali sono O(1).Così, il tempo di esecuzione di linee (1) e (2) è la prodotto di n e di O(1), che è O(n).

Allo stesso modo, possiamo vincolato il tempo di esecuzione del ciclo esterno, composto di linee (2) a (4), che è

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

Abbiamo già stabilito che il ciclo di linee (3) e (4) prende tempo O(n).Quindi, possiamo trascurare i O(1) tempo per incrementare i e per verificare se i < n ogni iterazione, concludendo che ogni iterazione del ciclo esterno, prende tempo O(n).

L'inizializzazione i = 0 del ciclo esterno e la (n + 1)st test della condizione io < n ugualmente prendere O(1) tempo e può essere trascurato.Infine, osserviamo che andiamo tutto l'anello esterno per n volte, prendendo tempo O(n) per ogni iterazione, per un totale O(n^2) il tempo di esecuzione.

Un pratico esempio.

enter image description here

Se si vuole stimare l'ordine di codice empiricamente piuttosto che analizzando il codice, si potrebbe bastone in una serie di valori crescenti di n e l'ora del codice.Tracciare i tuoi tempi su una scala logaritmica.Se il codice è O(x^n), i valori dovrebbero cadere su una linea di pendenza, n.

Questo ha diversi vantaggi, solo studiare il codice.Per una cosa, si può vedere se sei nel range in cui il tempo di esecuzione si avvicina al suo asintotica ordine.Inoltre, si potrebbe scoprire che il codice che hai pensato è stato di ordine O(x) è davvero di ordine O(x^2), per esempio, a causa del tempo trascorso in chiamate di libreria.

Fondamentalmente la cosa che salta fuori il 90% del tempo è solo l'analisi dei cicli.Hai singolo, doppio, triplo loop annidati?L'avete O(n) O(n^2), O(n^3) tempo di esecuzione.

Molto raramente (a meno che non si sta scrivendo una piattaforma con una vasta libreria di base (come ad esempio, l' .NET BCL, o C++, STL) si andrà incontro a qualcosa che è più difficile che solo guardando il tuo loop (dichiarazioni, mentre, goto, ecc...)

Abbattere l'algoritmo in pezzi si conosce la notazione O grande, e si combinano attraverso la grande O operatori.Questo è l'unico modo che io conosca.

Per ulteriori informazioni, controllare il Pagina di Wikipedia sul soggetto.

Notazione O grande è utile perché è facile da lavorare e si nasconde complicazioni inutili e dettagli (per una definizione di inutili).Un bel modo di capire la complessità di dividere e conquistare algoritmi è il metodo dell'albero.Diciamo che tu hai una versione di quicksort con la mediana procedura, in modo da dividere l'array in perfettamente bilanciato subarray ogni volta.

Costruire un albero corrispondente a tutte le matrici con cui si lavora.Alla radice si ha la matrice originale, la radice ha due figli che sono la subarray.Ripetere questa operazione fino al singolo elemento di array in fondo.

Dal momento che possiamo trovare la mediana in tempo O(n) e dividere l'array in due parti, in tempo O(n), il lavoro svolto in ciascun nodo è O(k), dove k è la dimensione della matrice.Ogni livello dell'albero contiene (al massimo) l'intero array in modo che il lavoro per ogni livello è O(n) (le dimensioni del subarray aggiungere fino a n, e dal momento che abbiamo O(k) per ogni livello possiamo aggiungere questo).Ci sono solo log(n) livelli nella struttura ad albero, dal momento che ogni volta che ci dimezzare l'ingresso.

Quindi possiamo limite superiore alla quantità di lavoro da O(n*log(n)).

Tuttavia, la Grande O nasconde alcuni dettagli che a volte abbiamo la non si può ignorare.Considerare il calcolo della sequenza di Fibonacci con

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

e diamo per scontato la a e la b sono BigIntegers in Java o qualcosa in grado di gestire arbitrariamente grandi numeri.La maggior parte delle persone sarebbe dire che questo è un O(n) algoritmo senza batter ciglio.Il ragionamento è che si dispone di n iterazioni del ciclo for e O(1) a lato del loop.

Ma i numeri di Fibonacci sono di grandi dimensioni, l'n-esimo numero di Fibonacci è esponenziale in n modo che solo conservando si svolgerà anche l'ordine di n byte.Eseguire l'addizione con i numeri interi grandi prenderà O(n) quantità di lavoro.Quindi la quantità totale di lavoro fatto in questa procedura è

1 + 2 + 3 + ...+ n = n(n-1)/2 = O(n^2)

Quindi, questo algoritmo viene eseguito in quadradic tempo!

La familiarità con gli algoritmi/strutture di dati che uso e/o rapida occhiata analisi di iterazione di nidificazione.La difficoltà è quando si chiama una funzione di libreria, possibilmente più volte - spesso si può essere sicuri di se si chiama la funzione inutilmente, a volte o cosa applicazione che si sta utilizzando.Forse libreria di funzioni dovrebbe avere una complessità/misura di efficienza, sia che si tratti di Grandi O o qualche altro sistema, che è disponibile nella documentazione o anche IntelliSense.

Meno utile in generale, credo, ma per completezza c'è anche un Grande Omega Ω, che definisce un basso-legati da un algoritmo di complessità, e un Grande Theta Θ, che definisce un limite superiore e limite inferiore.

Quanto al "come si fa a calcolare" O Grande, questo è parte del Teoria della complessità.Per alcuni (molti) casi particolari si può essere in grado di venire con qualche semplice euristica (come la moltiplicazione loop conta per cicli nidificati), esp.quando tutti si desidera è alcun limite superiore di stima, e non mente, se si è troppo pessimista - che credo che è probabilmente ciò che la tua domanda è di circa.

Se si vuole davvero rispondere alla tua domanda, per qualsiasi algoritmo il meglio che puoi fare è quello di applicare la teoria.Oltre semplicistico "caso peggiore" analisi ho trovato Ammortizzato analisi molto utile nella pratica.

Per il 1 ° caso, il ciclo interno viene eseguito n-i volte, in modo che il numero totale di esecuzioni è la somma per i andando da 0 per n-1 (perché inferiore, non minore di o uguale a), del n-i.Si ottiene infine n*(n + 1) / 2, così O(n²/2) = O(n²).

Per il 2 ° ciclo, i è tra 0 e n incluso per il ciclo esterno;quindi il ciclo interno viene eseguito quando j è strettamente maggiore di n, che è poi impossibile.

Oltre a utilizzare il metodo master (o una delle sue specializzazioni), testare il mio algoritmi sperimentalmente.Questo non può dimostrare che qualsiasi particolare complessità della classe è raggiunto, ma in grado di fornire rassicurazione che l'analisi matematica è appropriato.Per aiutare con questa rassicurazione, io uso il codice di copertura di strumenti in collaborazione con i miei esperimenti, per assicurare che mi sto esercitando tutti i casi.

Come un esempio molto semplice dire che si voleva fare una verifica sulla velocità .NET framework lista di sorta.Si potrebbe scrivere qualcosa di simile, quindi, analizzare i risultati in Excel per assicurarsi che non si superi il n*log(n) curva.

In questo esempio ho misurare il numero di confronti, ma è anche prudente esaminare il tempo effettivo necessario per ogni dimensione del campione.Però poi si deve essere ancora più attenta che sono solo di misura algoritmo e non, compresi i manufatti dalla vostra infrastruttura di test.

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

Non dimenticare, inoltre, consentono di spazio complessità che può anche essere un motivo di preoccupazione se uno ha limitate risorse di memoria.Così, per esempio, si può sentire qualcuno che vuole uno spazio costante algoritmo che è fondamentalmente un modo di dire che la quantità di spazio occupato dall'algoritmo non dipende da fattori all'interno del codice.

A volte la complessità può venire da quante volte è qualcosa che si chiama, come spesso è un ciclo eseguito, come spesso è la memoria allocata, e così via è un'altra parte per rispondere a questa domanda.

Infine, grande O può essere utilizzata anche per il caso peggiore, caso migliore e gli ammortamenti casi in cui, generalmente, è il caso peggiore che viene utilizzato per descrivere quanto male un algoritmo può essere.

Ciò che spesso viene trascurato è il previsto il comportamento di algoritmi. Non cambia il Big-O del tuo algoritmo, ma fa riferimento all'affermazione "prematura di ottimizzazione...."

Il comportamento previsto del vostro algoritmo è molto dumbed down-in quanto tempo si può aspettare il vostro algoritmo di lavorare sui dati, si è più probabile vedere.

Per esempio, se siete alla ricerca di un valore in un elenco, è O(n), ma se si sa che la maggior parte delle liste che vedi sono proprio valore di fronte, tipico comportamento di un algoritmo è più veloce.

Per unghie davvero giù, è necessario essere in grado di descrivere la distribuzione di probabilità del vostro "spazio input" (se hai bisogno di ordinare un elenco, come spesso è che la lista già sta per essere ordinati?come spesso è totalmente invertito?come spesso è per lo più ordinato?) Non è sempre fattibile che voi lo sapete, ma a volte sì.

ottima domanda!

Disclaimer:questa risposta contiene dichiarazioni false, vedere i commenti qui sotto.

Se si utilizza il Big O, stai parlando di caso peggiore (più su che cosa significa dopo).Inoltre, c'è la capitale theta per caso medio e grande omega per il caso migliore.

Check out questo sito per una bella definizione formale di Grande O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) significa che esistono due costanti positive c e k, tale che 0 ≤ f(n) ≤ cg(n) per ogni n ≥ k.I valori di c e k deve essere fisso per la funzione f e non devono dipendere dal n.

Ok, così ora che cosa si intende per "migliore" e "peggiore" complessità?

Questo è probabilmente più chiaramente illustrato attraverso esempi.Per esempio, se si utilizza la ricerca lineare a trovare un numero in un array ordinato quindi il caso peggiore è quando decidiamo di la ricerca per l'ultimo elemento dell'array come questo sarebbe più passi ci sono elementi nella matrice.Il caso migliore quando si ricerca per la primo elemento dal momento che si sarebbe fatto dopo il primo controllo.

Il punto di tutti questi aggettivo-caso complessità è che stiamo cercando un modo per rappresentare graficamente la quantità di tempo che un ipotetico programma viene eseguito fino al completamento in termini di dimensione del particolare variabili.Tuttavia, per molti algoritmi si può sostenere che non c'è una sola volta per un particolare formato di input.Si noti che questo è in contrasto con il requisito fondamentale di una funzione, qualsiasi input deve avere più di uno di uscita.Così ci troviamo con più funzioni per descrivere un algoritmo di complessità.Ora, anche se la ricerca di un array di dimensione n può richiedere diverse quantità di tempo, a seconda di quello che stai cercando in un array e a seconda proporzionale a n, siamo in grado di creare un'informativa descrizione dell'algoritmo usando il best-case, media case, e nel caso peggiore classi.

Ci dispiace, questo è così mal scritto e manca molto di informazioni tecniche.Ma spero che ti rendono la complessità delle classi più facile da pensare.Una volta che si diventa agio con questi diventa una semplice questione di analisi attraverso il vostro programma e alla ricerca di cose come per-loop che dipendono dalla matrice di dimensioni e di ragionamento basato su strutture di dati che tipo di input sarebbe risultato banale casi e quello di ingresso che sarebbe risultato nel peggiore dei casi.

Non so come risolvere a livello di programmazione, ma la prima cosa che la gente non è che siamo di esempio, l'algoritmo per alcuni modelli, il numero di operazioni fatte, dire 4n^2 + 2n + 1 ci sono 2 regole:

Se abbiamo una somma di termini, il termine con il maggior tasso di crescita è tenuto, con altri termini omesso.
Se si dispone di un prodotto di diversi fattori fattori costanti sono omessi.

Se vogliamo semplificare f(x), dove f(x) è la formula per il numero di operazioni fatte, (4n^2 + 2n + 1 spiegato sopra), si ottiene il big-O valore [O(n^2) in questo caso].Ma questo dovrà rendere conto per l'interpolazione di Lagrange in programma, che può essere difficile da implementare.E se il vero big-O valore O(2^n), e si potrebbe avere qualcosa di simile O(x^n), in modo che questo algoritmo probabilmente non essere programmabile.Ma se qualcuno si dimostra che mi sbagliavo, mi danno il codice ....

Per il codice, il ciclo esterno, verrà eseguito per n+1 volte, '1' tempo: il processo che controlla la se ho ancora soddisfa il requisito.E il ciclo interno viene eseguito n volte, n-2 volte....Così,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Per il codice B, anche se inner loop non passo ed eseguire i foo(), il ciclo interno sarà eseguito per n volte dipendono dal ciclo esterno, tempo di esecuzione, che è O(n)

Vorrei spiegare il Big-O un po ' diverso aspetto.

Big-O è solo per confrontare la complessità dei programmi, il che significa veloce come sono crescente quando gli ingressi sono in aumento e non il tempo esatto che si spendono per fare l'azione.

IMHO nel big-O formule, è meglio non usare più complesse equazioni (si potrebbe semplicemente attenersi a quelli nel grafico seguente.) Tuttavia è ancora possibile utilizzare altri più precisa formula (3^n, n^3, ...), ma più di questo, a volte può essere fuorviante!Quindi meglio tenerlo il più semplice possibile.

Vorrei sottolineare ancora una volta che qui non si desidera ottenere una formula esatta per il nostro algoritmo.Vogliamo solo mostrare come esso cresce quando gli ingressi sono in crescita e confrontare con gli altri algoritmi in che senso.Altrimenti sarebbe meglio utilizzare metodi diversi, come bench-marking.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow