Big O, come calcoli / approssimativo?

La maggior parte delle persone con una laurea in CS saprà certamente cosa significa Big O. Ci aiuta a misurare quanto sia efficace un algoritmo e se sai in quale categoria il problema che stai cercando di risolvere è in te puoi capire se è ancora ansible spremere quella piccola prestazione extra. 1

Ma sono curioso, come calcoli o approssimi la complessità dei tuoi algoritmi?

1 ma come si suol dire, non esagerare, l’ottimizzazione prematura è la radice di tutto il male , e l’ottimizzazione senza una causa giustificata dovrebbe meritare anche quel nome.

Sono un assistente professore presso la mia università locale nel corso Data Structures and Algorithms. Farò del mio meglio per spiegarlo qui in termini semplici, ma ti avverto che questo argomento richiede ai miei studenti un paio di mesi per essere finalmente compreso. Puoi trovare maggiori informazioni sul capitolo 2 di Data Structures and Algorithms nel libro Java .


Non esiste una procedura meccanica che possa essere utilizzata per ottenere il BigOh.

Come “libro di cucina”, per ottenere il BigOh da un pezzo di codice devi prima rend contoere che stai creando una formula matematica per contare quanti passaggi di calcoli vengono eseguiti dato un input di una certa dimensione.

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

Ad 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 sum di tutti gli elementi dell'array e vogliamo creare una formula per contare la complessità computazionale di tale funzione:

 Number_Of_Steps = f(N) 

Quindi abbiamo f(N) , una funzione per contare il numero di passi computazionali. L'input della funzione è la dimensione della struttura da elaborare. Significa che questa funzione è chiamata come:

 Number_Of_Steps = f(data.length) 

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

Ci sono molti modi per calcolare il BigOh. Da questo punto in avanti assumeremo che ogni frase che non dipende dalla dimensione dei dati di input richiede un numero costante di passaggi di calcolo.

Stiamo per aggiungere il numero individuale di passaggi della funzione, e né la dichiarazione della variabile locale né l'istruzione di ritorno dipendono dalla dimensione dell'array di data .

Ciò significa che le righe 1 e 4 richiedono ciascuna una quantità di passi C e la funzione è in qualche modo simile a questa:

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

La parte successiva è definire il valore dell'istruzione for . Ricorda che stiamo contando il numero di passaggi computazionali, il che significa che il corpo dell'istruzione for viene eseguito N volte. È come aggiungere C , N volte:

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

Non esiste una regola meccanica per contare quante volte viene eseguito il corpo di for , è necessario contarlo osservando cosa fa il codice. Per semplificare i calcoli, ignoriamo l'inizializzazione delle variabili, le condizioni e le parti di incremento dell'istruzione for .

Per ottenere il BigOh effettivo abbiamo bisogno dell'analisi asintotica della funzione. Questo è grosso modo come questo:

  1. Porta via tutte le costanti C
  2. Da f() ottieni il polinomium nella sua standard form .
  3. Dividi i termini del polinomium e ordinali secondo il tasso di crescita.
  4. Mantiene quello che diventa più grande quando N avvicina infinity .

La nostra f() ha due termini:

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

Eliminando tutte le costanti C e le parti ridondanti:

 f(N) = 1 + N ^ 1 

Poiché l'ultimo termine è quello che aumenta quando f() avvicina all'infinito (pensa ai limiti ) questo è l'argomento BigOh, e la funzione sum() ha un BigOh di:

 O(N) 

Ci sono alcuni trucchi per risolvere alcuni difficili: usa le sumzioni ogni volta che puoi.

Ad esempio, questo codice può essere facilmente risolto usando le sumtorie:

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

La prima cosa che dovevi chiedere è l'ordine di esecuzione di foo() . Mentre il solito è essere O(1) , devi chiederlo ai tuoi professori. O(1) significa (quasi, per lo più) costante C , indipendentemente dalla dimensione N

L'affermazione for sulla frase numero uno è complicata. Mentre l'indice termina a 2 * N , l'incremento viene eseguito da due. Ciò significa che il primo for viene eseguito solo N passaggi, e abbiamo bisogno di dividere il conteggio per due.

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

La seconda frase è ancora più complicata in quanto dipende dal valore di i . Date un'occhiata: l'indice prende i valori: 0, 2, 4, 6, 8, ..., 2 * N, e il secondo for essere eseguito: N volte il primo, N - 2 il secondo, N - 4 il terzo ... fino allo stage N / 2, sul quale il secondo non viene mai eseguito.

Sulla formula, ciò significa:

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

Ancora una volta, stiamo contando il numero di passaggi . E per definizione, ogni sumrio dovrebbe sempre iniziare da uno e terminare con un numero maggiore o uguale a uno.

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

(Supponiamo che foo() sia O(1) e passi C ).

Abbiamo un problema qui: quando i il valore N / 2 + 1 verso l'alto, la sum interna termina con un numero negativo! Questo è imansible e sbagliato. Abbiamo bisogno di dividere la sumtoria in due, essendo il punto chiave nel momento in cui i 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 cruciale i > N / 2 , l'interno for non verrà eseguito, e stiamo assumendo una complessità di esecuzione C costante sul suo corpo.

Ora le sumtorie possono essere semplificate utilizzando alcune regole di identity framework:

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

Applicando dell'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²) 

Big O fornisce il limite superiore per la complessità temporale di un algoritmo. Di solito viene utilizzato insieme all’elaborazione di serie di dati (elenchi) ma può essere utilizzato altrove.

Alcuni esempi di come è usato nel codice C.

Diciamo che abbiamo una matrice di n elementi

 int array[n]; 

Se volessimo accedere al primo elemento dell’array, questo sarebbe O (1) poiché non importa quanto grande sia l’array, richiede sempre lo stesso tempo costante per ottenere il primo elemento.

 x = array[0]; 

Se volessimo trovare un numero nell’elenco:

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

Questo sarebbe O (n) poiché al massimo dovremmo esaminare l'intera lista per trovare il nostro numero. Il Big-O è ancora O (n) anche se potremmo trovare il nostro numero al primo tentativo ed eseguire il ciclo una volta perché Big-O descrive il limite superiore per un algoritmo (omega è per limite inferiore e theta è per limite stretto) .

Quando arriviamo a loop annidati:

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

Questo è O (n ^ 2) poiché per ogni passaggio del ciclo esterno (O (n)) dobbiamo passare di nuovo attraverso l'intera lista in modo che la n si moltiplica lasciandoci con n al quadrato.

Questo sta appena scalfendo la superficie, ma quando si arriva ad analizzare algoritmi più complessi entra in gioco la matematica complessa che coinvolge le prove. Spero che questo ti familiarizzi con le basi almeno.

Mentre sapere come calcolare il tempo di Big O per il tuo particolare problema è utile, conoscere alcuni casi generali può aiutare molto a prendere decisioni nel tuo algoritmo.

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

O (1) – Determinare se un numero è pari o dispari; utilizzando una tabella di ricerca o una tabella hash di dimensioni costanti

O (logn): ricerca di un elemento in un array ordinato con una ricerca binaria

O (n): ricerca di un elemento in un elenco non ordinato; aggiungendo due numeri ad una cifra

O (n 2 ) – Moltiplicando due numeri di n cifre con un semplice algoritmo; aggiungendo due matrici n × n; ordinamento di bolle o ordinamento di inserimento

O (n 3 ) – Moltiplicando due matrici n × n con un semplice algoritmo

O (c n ) – Trovare la soluzione (esatta) al problema del commesso viaggiatore usando la programmazione dynamic; determinare se due istruzioni logiche sono equivalenti usando la forza bruta

O (n!) – Risolvere il problema del commesso viaggiatore tramite la ricerca di forza bruta

O (n n ) – Spesso usato al posto di O (n!) Per derivare formule più semplici per la complessità asintotica

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

Ciò significa che tra un algoritmo in O (n) e uno in O (n 2 ), il più veloce non è sempre il primo (sebbene esista sempre un valore di n tale che per problemi di dimensione> n, il primo algoritmo sia il più veloce).

Nota che la costante nascosta dipende molto dall’implementazione!

Inoltre, in alcuni casi, il runtime non è una funzione deterministica della dimensione n dell’input. Prendi l’ordinamento usando l’ordinamento rapido per esempio: il tempo necessario per ordinare un array di n elementi non è una costante ma dipende dalla configurazione iniziale dell’array.

Esistono diverse complessità temporali:

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

Una buona introduzione è Un’introduzione all’analisi degli algoritmi di R. Sedgewick e P. Flajolet.

Come dici tu, premature optimisation is the root of all evil e, se ansible, la profilazione dovrebbe essere sempre utilizzata quando si ottimizza il codice. Può persino aiutarti a determinare la complessità dei tuoi algoritmi.

Vedendo le risposte qui, penso che possiamo concludere che la maggior parte di noi effettivamente approssima l’ordine dell’algoritmo guardandolo e usino il buonsenso invece di calcolarlo con, per esempio, il metodo master come ci si pensava all’università. Detto questo devo aggiungere che anche il professore ci ha incoraggiati (in seguito) a pensarci davvero invece di calcolarlo.

Inoltre vorrei aggiungere come è fatto per le funzioni ricorsive :

supponiamo di avere una funzione come ( codice dello schema ):

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

che calcola ricorsivamente il fattoriale del numero specificato.

Il primo passo è cercare di determinare le caratteristiche delle prestazioni per il corpo della funzione solo in questo caso, non viene fatto nulla di speciale nel corpo, solo una moltiplicazione (o il ritorno del valore 1).

Quindi le prestazioni per il corpo sono: O (1) (costante).

Quindi prova a determinarlo per il numero di chiamate ricorsive . In questo caso abbiamo chiamate ricorsive n-1.

Quindi le prestazioni per le chiamate ricorsive sono: O (n-1) (l’ordine è n, poiché gettiamo via le parti insignificanti).

Quindi metti questi due insieme e ottieni le prestazioni per l’intera funzione ricorsiva:

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


Peter , per rispondere ai tuoi problemi sollevati; il metodo che descrivo qui in realtà gestisce questo abbastanza bene. Ma tieni presente che questa è ancora un’approssimazione e non una risposta completa dal punto di vista matematico. Il metodo qui descritto è anche uno dei metodi che ci è stato insegnato all’università e, se ricordo bene, è stato usato per algoritmi molto più avanzati del fattoriale che ho usato in questo esempio.
Ovviamente tutto dipende da quanto è ansible stimare il tempo di esecuzione del corpo della funzione e il numero di chiamate ricorsive, ma questo è altrettanto vero per gli altri metodi.

Se il tuo costo è un polinomio, mantieni il termine più alto, senza il suo moltiplicatore. Per esempio:

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

Questo non funziona per serie infinite, attenzione. Non esiste una singola ricetta per il caso generale, sebbene, per alcuni casi comuni, si applichino le seguenti disuguaglianze:

O (log N ) N ) N log N ) N 2 ) N k ) n ) n !)

Ci penso in termini di informazioni. Qualsiasi problema consiste nell’imparare un certo numero di bit.

Il tuo strumento di base è il concetto di punti decisionali e la loro entropia. L’entropia di un punto di decisione è l’informazione media che ti darà. Ad esempio, se un programma contiene un punto di decisione con due rami, l’entropia è la sum della probabilità di ciascun ramo di moltiplicare il log 2 della probabilità inversa di quel ramo. Questo è quanto impari eseguendo quella decisione.

Ad esempio, un’istruzione if con due rami, entrambi ugualmente probabili, ha un’entropia di 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Quindi la sua entropia è 1 bit.

Supponi di cercare una tabella di N elementi, come N = 1024. Questo è un problema a 10 bit perché log (1024) = 10 bit. Quindi, se puoi cercarlo con istruzioni IF che hanno risultati ugualmente probabili, dovrebbe prendere 10 decisioni.

Questo è quello che ottieni con la ricerca binaria.

Supponiamo che tu stia facendo una ricerca lineare. Guardi il primo elemento e chiedi se è quello che vuoi. Le probabilità sono 1/1024 che è, e 1023/1024 che non lo è. 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. Ecco perché la ricerca lineare è così lenta. In effetti è esponenziale nel numero di bit che devi imparare.

Supponiamo che stai facendo indicizzazione. Supponiamo che la tabella sia preordinata in un sacco di contenitori, e tu usi alcuni di tutti i bit nella chiave per indicizzare direttamente alla voce della tabella. Se ci sono 1024 bin, l’entropia è 1/1024 * log (1024) + 1/1024 * log (1024) + … per tutti i 1024 possibili risultati. Questo è 1/1024 * 10 volte 1024 esiti, o 10 bit di entropia per quella operazione di indicizzazione. Ecco perché l’indicizzazione della ricerca è veloce.

Ora pensa all’ordinamento. Hai N elementi e hai una lista. Per ogni articolo, devi cercare dove l’elemento va nella lista, e poi aggiungerlo alla lista. Quindi l’ordinamento richiede circa N volte il numero di passaggi della ricerca sottostante.

Quindi gli ordinamenti basati su decisioni binarie che hanno risultati quasi ugualmente probabili richiedono tutti passi O (N log N). Un algoritmo di ordinamento O (N) è ansible se si basa sulla ricerca di indicizzazione.

Ho scoperto che quasi tutti i problemi di prestazioni algoritmiche possono essere esaminati in questo modo.

Iniziamo dall’inizio.

Prima di tutto, accetta il principio che alcune semplici operazioni sui dati possono essere eseguite in tempo O(1) , cioè nel tempo che è indipendente dalla dimensione dell’input. Queste operazioni primitive in C consistono in

  1. Operazioni aritmetiche (es. + O%).
  2. Operazioni logiche (es. &&).
  3. Operazioni di confronto (es. < =).
  4. Operazioni di accesso alla struttura (ad esempio indicizzazione di array come A [i] o puntatore successivo con l’operatore ->).
  5. Assegnazione semplice come copiare un valore in una variabile.
  6. Chiamate alle funzioni di libreria (ad esempio, scanf, printf).

La giustificazione di questo principio richiede uno studio dettagliato delle istruzioni della macchina (passi primitivi) di un tipico computer. Ciascuna delle operazioni descritte può essere eseguita con un numero limitato di istruzioni della macchina; spesso sono necessarie solo una o due istruzioni. Di conseguenza, diversi tipi di istruzioni in C possono essere eseguite in tempo O(1) , cioè in un intervallo di tempo costante indipendente dall’input. Questi semplici includono

  1. Dichiarazioni di assegnazione che non implicano chiamate di funzione nelle loro espressioni.
  2. Leggi le dichiarazioni.
  3. Scrivere affermazioni che non richiedono chiamate di funzione per valutare gli argomenti.
  4. Le istruzioni jump interrompono, continuano, goto e restituiscono un’espressione, dove expression non contiene una chiamata di funzione.

In C, molti for-loops si formano inizializzando una variabile di indice su un valore e aumentando quella variabile di 1 ogni volta attorno al ciclo. Il ciclo chiuso termina quando l’indice raggiunge un certo limite. Ad 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 indice i. Aumenta di 1 unità ogni volta attorno al ciclo e le iterazioni si fermano quando raggiungo n - 1.

Tuttavia, per il momento, concentrati sulla semplice forma di for-loop, in cui la differenza tra il valore finale e quello iniziale, diviso per l'importo con cui viene incrementata la variabile indice, ci dice quante volte facciamo il giro del ciclo . Questo conteggio è esatto, a meno che non ci siano modi per uscire dal ciclo tramite un'istruzione di salto; in ogni caso è un limite superiore al numero di iterazioni.

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

Nel caso più semplice, in cui il tempo trascorso nel corpo del ciclo è lo stesso per ogni iterazione, possiamo moltiplicare il limite superiore del big-oh per il corpo per il numero di volte attorno al ciclo . A rigor di termini, dobbiamo aggiungere il tempo O (1) per inizializzare l'indice del ciclo e il tempo O (1) per il primo confronto dell'indice del ciclo con il limite , perché testiamo ancora una volta rispetto al ciclo. Tuttavia, a meno che non sia ansible eseguire il ciclo zero volte, il tempo per inizializzare il ciclo e testare il limite una volta è un termine di ordine basso che può essere eliminato dalla regola di sumtoria.


Considerare ora questo esempio:

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

Sappiamo che la riga (1) richiede O(1) tempo. Chiaramente, facciamo il giro n volte, come possiamo determinare sottraendo il limite inferiore dal limite superiore trovato sulla linea (1) e quindi aggiungendo 1. Poiché il corpo, linea (2), richiede O (1) tempo, possiamo trascurare il tempo di incrementare j e il tempo di confrontare j con n, entrambi dei quali sono anche O (1). Pertanto, il tempo di esecuzione delle righe (1) e (2) è il prodotto di n e O (1) , che è O(n) .

Allo stesso modo, possiamo limitare il tempo di esecuzione del ciclo esterno costituito da 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) richiede il tempo O (n). Quindi, possiamo trascurare il tempo O (1) per incrementare i e per verificare se i

L'inizializzazione i = 0 del ciclo esterno e il (n + 1) st test della condizione i O(n^2) .


Un esempio più pratico.

inserisci la descrizione dell'immagine qui

Se si desidera stimare l’ordine del codice in modo empirico piuttosto che analizzando il codice, è ansible inserire una serie di valori crescenti di n e cronometrare il codice. Traccia i tuoi tempi su una scala di registro. Se il codice è O (x ^ n), i valori dovrebbero cadere su una linea di pendenza n.

Questo ha diversi vantaggi rispetto allo studio del codice. Per prima cosa, puoi vedere se ti trovi nell’intervallo in cui il tempo di esecuzione si avvicina al suo ordine asintotico. Inoltre, potreste scoprire che un codice che pensavate fosse un ordine O (x) è in realtà ordine O (x ^ 2), ad esempio, a causa del tempo trascorso nelle chiamate in biblioteca.

Fondamentalmente la cosa che affiora il 90% delle volte è solo un’analisi dei loop. Avete loop singoli, doppi, a triplo annidamento? Hai tempo di esecuzione O (n), O (n ^ 2), O (n ^ 3).

Molto raramente (a meno che non si stia scrivendo una piattaforma con un’estesa libreria di base (come ad esempio, .NET BCL o STL di C ++) si incontrerà qualcosa di più difficile del semplice guardare i propri loop (per le istruzioni, mentre, goto, eccetera…)

Suddividi l’algoritmo in pezzi che conosci la grande notazione O e combinali con i grandi operatori O. È l’unico modo che conosco.

Per ulteriori informazioni, consultare la pagina di Wikipedia sull’argomento.

La notazione Big O è utile perché è facile lavorarci e nasconde complicazioni e dettagli inutili (per alcune definizioni di inutili). Un buon modo per elaborare la complessità degli algoritmi divide e conquista è il metodo ad albero. Diciamo che hai una versione di quicksort con la procedura mediana, quindi dividi la matrice in sottotasti perfettamente bilanciati ogni volta.

Ora costruisci un albero corrispondente a tutti gli array con cui lavori. Alla radice hai la matrice originale, la radice ha due figli che sono i sottoarray. Ripeti fino a quando non hai array di elementi singoli nella parte inferiore.

Dato che possiamo trovare la mediana nel tempo O (n) e dividere l’array in due parti nel tempo O (n), il lavoro svolto su ciascun nodo è O (k) dove k è la dimensione dell’array. Ogni livello dell’albero contiene (al massimo) l’intero array in modo che il lavoro per livello sia O (n) (le dimensioni dei subarray si sumno in n, e dato che abbiamo O (k) per livello possiamo aggiungere questo) . Ci sono solo i livelli log (n) nell’albero ogni volta che dimezziamo l’input.

Quindi possiamo limitare il limite di lavoro di O (n * log (n)).

Tuttavia, Big O nasconde alcuni dettagli che a volte non possiamo ignorare. Prendi in considerazione il calcolo della sequenza di Fibonacci con

 a=0; b=1; for (i = 0; i  

e lascia solo supporre che a e b siano BigInteger in Java o qualcosa che possa gestire numeri arbitrariamente grandi. La maggior parte delle persone direbbe che questo è un algoritmo O (n) senza battere ciglio. Il ragionamento è che hai n iterazioni nel ciclo for e O (1) lavora nel lato del ciclo.

Ma i numeri di Fibonacci sono grandi, il n-esimo numero di Fibonacci è esponenziale in n, quindi solo la memorizzazione avrà l'ordine di n byte. L'esecuzione dell'aggiunta con i grandi numeri interi richiederà O (n) quantità di lavoro. Quindi la quantità totale di lavoro svolto in questa procedura è

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

Quindi questo algoritmo funziona in tempo quadruplo!

Familiarità con gli algoritmi / strutture dati che uso e / o analisi rapida occhiata di nidificazione di iterazione. La difficoltà è quando si chiama una funzione di libreria, probabilmente più volte – spesso si può essere incerti se si sta chiamando la funzione inutilmente a volte o quale implementazione stanno utilizzando. Forse le funzioni della libreria dovrebbero avere una misura di complessità / efficienza, che sia Big O o qualche altra metrica, che sia disponibile nella documentazione o anche in IntelliSense .

Meno utile in generale, penso, ma per completezza c’è anche un Big Omega Ω , che definisce un limite inferiore sulla complessità di un algoritmo, e un Big Theta Θ , che definisce sia un limite superiore che uno inferiore.

Per quanto riguarda “come si calcola” Big O, questo fa parte della teoria della complessità computazionale . Per alcuni (molti) casi speciali potresti essere in grado di venire con delle semplici euristiche (come moltiplicare i conteggi dei cicli per i cicli annidati), esp. quando tutto ciò che vuoi è una stima superiore, e non ti dispiace se è troppo pessimista – che credo sia probabilmente la tua domanda.

Se vuoi davvero rispondere alla tua domanda per qualsiasi algoritmo, il meglio che puoi fare è applicare la teoria. Oltre all’analisi semplicistica del “caso peggiore”, ho trovato l’ analisi ammortizzata molto utile nella pratica.

Per il primo caso, il ciclo interno viene eseguito ni volte, quindi il numero totale di esecuzioni è la sum per cui vado da 0 a n-1 (perché inferiore a, non inferiore o uguale) del ni . Otterrai finalmente n*(n + 1) / 2 , quindi O(n²/2) = O(n²) .

Per il secondo ciclo, i è compreso tra 0 e n incluso per il ciclo esterno; quindi il ciclo interno viene eseguito quando j è strettamente maggiore di n , che è quindi imansible.

Oltre a utilizzare il metodo master (o una delle sue specializzazioni), collaudo sperimentalmente i miei algoritmi. Questo non può dimostrare che una particolare class di complessità sia raggiunta, ma può fornire rassicurazione sul fatto che l’analisi matematica sia appropriata. Per aiutare con questa rassicurazione, uso gli strumenti di copertura del codice in congiunzione con i miei esperimenti, per garantire che sto esercitando tutti i casi.

Come un esempio molto semplice, diciamo che volevi fare un controllo di integrità sulla velocità dell’ordinamento della lista di .NET framework. È ansible scrivere qualcosa come il seguente, quindi analizzare i risultati in Excel per assicurarsi che non superino una curva n * log (n).

In questo esempio misuro il numero di confronti, ma è anche prudente esaminare il tempo effettivo richiesto per ogni dimensione del campione. Tuttavia, devi essere ancora più attento a misurare semplicemente l’algoritmo e a non includere gli artefatti dall’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 lst = new List(n); for( int i=0; ib)?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 di considerare anche le complessità spaziali che possono anche essere motivo di preoccupazione se si dispone di risorse di memoria limitate. Quindi, ad esempio, potresti sentire qualcuno che vuole un algoritmo di spazio costante che è fondamentalmente un modo per dire che la quantità di spazio preso dall’algoritmo non dipende da alcun fattore all’interno del codice.

A volte la complessità può derivare da quante volte viene chiamato qualcosa, quanto spesso viene eseguito un ciclo, quanto spesso viene allocata memoria, e così via è un’altra parte per rispondere a questa domanda.

Infine, il big O può essere utilizzato per casi peggiori, casi migliori e casi di ammortamento, dove generalmente è il caso peggiore che viene utilizzato per descrivere quanto può essere cattivo un algoritmo.

Ciò che spesso viene trascurato è il comportamento previsto dei tuoi algoritmi. Non cambia il Big-O del tuo algoritmo , ma si riferisce alla frase “ottimizzazione prematura …”

Il comportamento atteso dell’algoritmo è – molto stupido – quanto velocemente ci si può aspettare che l’algoritmo funzioni sui dati che è più probabile che si vedano.

Ad esempio, se stai cercando un valore in un elenco, è O (n), ma se sai che la maggior parte degli elenchi che vedi hanno il tuo valore in primo piano, il comportamento tipico dell’algoritmo è più veloce.

To really nail it down, you need to be able to describe the probability distribution of your “input space” (if you need to sort a list, how often is that list already going to be sorted? how often is it totally reversed? how often is it mostly sorted?) It’s not always feasible that you know that, but sometimes you do.

great question!

If you’re using the Big O, you’re talking about the worse case (more on what that means later). Additionally, there is capital theta for average case and a big omega for best case.

Check out this site for a lovely formal definition of Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.


Ok, so now what do we mean by “best-case” and “worst-case” complexities?

This is probably most clearly illustrated through examples. For example if we are using linear search to find a number in a sorted array then the worst case is when we decide to search for the last element of the array as this would take as many steps as there are items in the array. The best case would be when we search for the first element since we would be done after the first check.

The point of all these adjective -case complexities is that we’re looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm’s complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you’re looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classs.

Sorry this is so poorly written and lacks much technical information. But hopefully it’ll make time complexity classs easier to think about. Once you become comfortable with these it becomes a simple matter of parsing through your program and looking for things like for-loops that depend on array sizes and reasoning based on your data structures what kind of input would result in trivial cases and what input would result in worst-cases.

For code A, the outer loop will execute for n+1 times, the ‘1’ time means the process which checks the whether i still meets the requirement. And inner loop runs n times, n-2 times…. Thus, 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

For code B, though inner loop wouldn’t step in and execute the foo(), the inner loop will be executed for n times depend on outer loop execution time, which is O(n)

I don’t know how to programmatically solve this, but the first thing people do is that we sample the algorithm for certain patterns in the number of operations done, say 4n^2 + 2n + 1 we have 2 rules:

  1. If we have a sum of terms, the term with the largest growth rate is kept, with other terms omitted.
  2. If we have a product of several factors constant factors are omitted.

If we simplify f(x), where f(x) is the formula for number of operations done, (4n^2 + 2n + 1 explained above), we obtain the big-O value [O(n^2) in this case]. But this would have to account for Lagrange interpolation in the program, which may be hard to implement. And what if the real big-O value was O(2^n), and we might have something like O(x^n), so this algorithm probably wouldn’t be programmable. But if someone proves me wrong, give me the code . . . .