Come trovare la complessità temporale di un algoritmo

La domanda

Come trovare la complessità temporale di un algoritmo?

Cosa ho fatto prima di pubblicare una domanda su SO?

Ho attraversato questo , questo e molti altri link

Ma non dove sono stato in grado di trovare una spiegazione chiara e diretta per come calcolare la complessità del tempo.

Cosa so ?

Dì per un codice semplice come quello qui sotto:

char h = 'y'; // This will be executed 1 time int abc = 0; // This will be executed 1 time 

Dì per un ciclo come quello qui sotto:

 for (int i = 0; i < N; i++) { Console.Write('Hello World !'); } 

int i = 0; Questo verrà eseguito solo una volta . Il tempo viene effettivamente calcolato in i=0 e non nella dichiarazione.

i <N; Questo verrà eseguito N + 1 volte

i ++; Questo verrà eseguito N volte

Quindi il numero di operazioni richieste da questo ciclo sono

{1+ (N + 1) + N} = 2N + 2

Nota: questo potrebbe essere ancora sbagliato, poiché non sono sicuro della mia comprensione del calcolo della complessità temporale

Ciò che voglio sapere ?

Ok, quindi questi piccoli calcoli di base credo di sapere, ma nella maggior parte dei casi ho visto la complessità del tempo come

O (N), O (n2), O (log n), O (n!) …. e molti altri ,

Qualcuno può aiutarmi a capire come si calcola la complessità temporale di un algoritmo? Sono sicuro che ci sono molti neofiti come me che vogliono sapere questo.

Come trovare la complessità temporale di un algoritmo

Si sumno il numero di istruzioni macchina che eseguirà in funzione della dimensione del suo input e quindi si semplificherà l’espressione al termine più grande (quando N è molto grande) e può includere qualsiasi fattore di semplificazione costante.

Ad esempio, vediamo come semplificare le istruzioni della macchina 2N + 2 per descrivere questo come solo O(N) .

Perché rimuoviamo i due 2 s?

Siamo interessati alle prestazioni dell’algoritmo quando N diventa grande.

Considera i due termini 2N e 2.

Qual è l’influenza relativa di questi due termini quando N diventa grande? Supponiamo che N sia un milione.

Quindi il primo termine è 2 milioni e il secondo termine è solo 2.

Per questo motivo, rilasciamo tutti tranne i termini più grandi per il grande N.

Quindi, ora siamo passati da 2N + 2 a 2N .

Tradizionalmente, ci interessano solo le prestazioni fino a fattori costanti .

Ciò significa che non ci interessa davvero se c’è un multiplo costante di differenze nelle prestazioni quando N è grande. In ogni caso, l’unità di 2N non è ben definita. Quindi possiamo moltiplicare o dividere per un fattore costante per arrivare all’espressione più semplice.

Quindi 2N diventa solo N

Questo è un articolo eccellente: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

La risposta qui sotto è copiata dall’alto (nel caso in cui l’eccellente collegamento fallisca)

La metrica più comune per il calcolo della complessità temporale è la notazione Big O. Ciò rimuove tutti i fattori costanti in modo che il tempo di esecuzione possa essere stimato in relazione a N quando N si avvicina all’infinito. In generale puoi pensare in questo modo:

 statement; 

È costante Il tempo di esecuzione della dichiarazione non cambierà in relazione a N.

 for ( i = 0; i < N; i++ ) statement; 

È lineare Il tempo di esecuzione del loop è direttamente proporzionale a N. Quando N raddoppia, lo stesso vale per il tempo di esecuzione.

 for ( i = 0; i < N; i++ ) { for ( j = 0; j < N; j++ ) statement; } 

È quadratico Il tempo di esecuzione dei due loop è proporzionale al quadrato di N. Quando N raddoppia, il tempo di esecuzione aumenta di N * N.

 while ( low <= high ) { mid = ( low + high ) / 2; if ( target < list[mid] ) high = mid - 1; else if ( target > list[mid] ) low = mid + 1; else break; } 

È logaritmico. Il tempo di esecuzione dell'algoritmo è proporzionale al numero di volte che N può essere diviso per 2. Questo perché l'algoritmo divide l'area di lavoro a metà con ciascuna iterazione.

 void quicksort ( int list[], int left, int right ) { int pivot = partition ( list, left, right ); quicksort ( list, left, pivot - 1 ); quicksort ( list, pivot + 1, right ); } 

È N * log (N). Il tempo di esecuzione è costituito da N loop (iterativi o ricorsivi) logaritmici, quindi l'algoritmo è una combinazione di lineare e logaritmico.

In generale, fare qualcosa con ogni object in una dimensione è lineare, fare qualcosa con ogni object in due dimensioni è quadratico, e la divisione dell'area di lavoro a metà è logaritmica. Ci sono altre misure di Big O come cubico, esponenziale e radice quadrata, ma non sono così comuni. La notazione O grande è descritta come O () dove è la misura. L'algoritmo di quicksort sarebbe descritto come O (N * log (N)).

Nota che nessuno di questi ha preso in considerazione le misure migliori, medie e peggiori. Ognuno avrebbe la sua notazione Big O. Si noti inoltre che questa è una spiegazione MOLTO semplicistica. Big O è il più comune, ma è anche più complesso che ho mostrato. Ci sono anche altre notazioni come il big omega, il piccolo o il grande theta. Probabilmente non li incontrerai al di fuori di un corso di analisi algoritmica. 😉

Preso da qui – Introduzione alla complessità del tempo di un algoritmo

1. Introduzione

Nell’informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegato da un algoritmo per funzionare in funzione della lunghezza della stringa che rappresenta l’input.

2. Notazione O grande

La complessità temporale di un algoritmo viene comunemente espressa utilizzando la notazione O grande, che esclude i coefficienti e i termini di ordine inferiore. Quando express in questo modo, si dice che la complessità temporale sia descritta asintoticamente, cioè, poiché la dimensione dell’input va all’infinito.

Ad esempio, se il tempo richiesto da un algoritmo su tutti gli input di dimensione n è al massimo 5n 3 + 3n, la complessità temporale asintotica è O (n 3 ). Maggiori informazioni in seguito.

Pochi altri esempi:

  • 1 = O (n)
  • n = O (n 2 )
  • log (n) = O (n)
  • 2 n + 1 = O (n)

3. O (1) Tempo costante:

Si dice che un algoritmo funzioni in un tempo costante se richiede la stessa quantità di tempo indipendentemente dalle dimensioni dell’input.

Esempi:

  • array: accesso a qualsiasi elemento
  • stack a dimensione fissa: metodi push e pop
  • coda a dimensione fissa: metodi di enqueue e dequeue

4. O (n) Tempo lineare

Si dice che un algoritmo funzioni in tempo lineare se la sua esecuzione temporale è direttamente proporzionale alla dimensione dell’input, cioè il tempo cresce in modo lineare man mano che la dimensione dell’ingresso aumenta.

Considera i seguenti esempi, di seguito Sto cercando linearmente un elemento, questo ha una complessità temporale di O (n).

 int find = 66; var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 }; for (int i = 0; i < numbers.Length - 1; i++) { if(find == numbers[i]) { return; } } 

Altri esempi:

  • Array: ricerca lineare, attraversamento, ricerca minima ecc
  • ArrayList: contiene il metodo
  • Coda: contiene il metodo

5. O (log n) Tempo logaritmico:

Si dice che un algoritmo funzioni in tempo logaritmico se la sua esecuzione temporale è proporzionale al logaritmo della dimensione di input.

Esempio: ricerca binaria

Ricorda il gioco delle "venti domande": il compito è indovinare il valore di un numero nascosto in un intervallo. Ogni volta che fai una supposizione, ti viene detto se la tua ipotesi è troppo alta o troppo bassa. Il gioco delle venti domande implica una strategia che usa il tuo numero di indovinare per dimezzare la dimensione dell'intervallo. Questo è un esempio del metodo generale di risoluzione dei problemi noto come ricerca binaria

6. O (n2) Quadratic Time

Si dice che un algoritmo funzioni in tempo quadratico se la sua esecuzione temporale è proporzionale al quadrato della dimensione di input.

Esempi:

  • Bubble Sort
  • Selezione Ordina
  • Inserimento Ordina

7. Alcuni link utili

  • Idee sbagliate di Big-O
  • Determinazione della complessità dell'algoritmo
  • Big O Cheat Sheet

Sebbene ci siano alcune buone risposte a questa domanda. Vorrei dare un’altra risposta qui con diversi esempi di loop .

  • O (n) : la complessità temporale di un loop è considerata come O (n) se le variabili di ciclo sono incrementate / decrementate di una quantità costante. Ad esempio le seguenti funzioni hanno una complessità temporale O (n) .

     // Here c is a positive integer constant for (int i = 1; i <= n; i += c) { // some O(1) expressions } for (int i = n; i > 0; i -= c) { // some O(1) expressions } 
  • O (n ^ c) : la complessità temporale dei cicli nidificati è uguale al numero di volte in cui viene eseguita l’istruzione più interna. Ad esempio i seguenti loop di esempio hanno una complessità temporale O (n ^ 2)

     for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some O(1) expressions } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // some O(1) expressions } 

    Ad esempio Selezione ordinamento e Inserimento ordinamento hanno O (n ^ 2) complessità temporale.

  • O (Logn) Tempo La complessità di un ciclo è considerata come O (Logn) se le variabili del ciclo sono divise / moltiplicate per una quantità costante.

     for (int i = 1; i <=n; i *= c) { // some O(1) expressions } for (int i = n; i > 0; i /= c) { // some O(1) expressions } 

    Ad esempio, la ricerca binaria ha una complessità temporale O (Logn) .

  • O (LogLogn) Tempo La complessità di un ciclo è considerata O (LogLogn) se le variabili di ciclo vengono ridotte / aumentate esponenzialmente di una quantità costante.

     // Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 0; i = fun(i)) { // some O(1) expressions } 

Un esempio di analisi della complessità temporale

 int fun(int n) { for (int i = 1; i <= n; i++) { for (int j = 1; j < n; j += i) { // Some O(1) task } } } 

Analisi :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

Quindi la complessità temporale totale dell'algoritmo di cui sopra è (n + n/2 + n/3 + … + n/n) , che diventa n * (1/1 + 1/2 + 1/3 + … + 1/n)

La cosa importante della serie (1/1 + 1/2 + 1/3 + … + 1/n) è uguale a O (Logn) . Quindi la complessità temporale del codice precedente è O (nLogn) .


Rif: 1 2 3

La complessità del tempo con esempi

1 – Operazioni di base (aritmetica, confronti, accesso agli elementi dell’array, assegnazione): il tempo di esecuzione è sempre costante O (1)

Esempio :

 read(x) // O(1) a = 10; // O(1) a = 1.000.000.000.000.000.000 // O(1) 

2 – Se poi altra affermazione: Solo prendendo il tempo massimo di esecuzione da due o più affermazioni possibili.

Esempio:

 age = read(x) // (1+1) = 2 if age < 17 then begin // 1 status = "Not allowed!"; // 1 end else begin status = "Welcome! Please come in"; // 1 visitors = visitors + 1; // 1+1 = 2 end; 

Quindi, la complessità dello pseudo codice sopra è T (n) = 2 + 1 + max (1, 1 + 2) = 6. Quindi, il suo big oh è ancora costante T (n) = O (1).

3 - Ciclo continuo (per, mentre, ripetizione): il tempo di esecuzione di questa istruzione è il numero di cicli moltiplicato per il numero di operazioni all'interno di quel ciclo.

Esempio:

 total = 0; // 1 for i = 1 to n do begin // (1+1)*n = 2n total = total + i; // (1+1)*n = 2n end; writeln(total); // 1 

Quindi, la sua complessità è T (n) = 1 + 4n + 1 = 4n + 2. Quindi, T (n) = O (n).

4 - Nested Loop (looping all'interno di looping): poiché c'è almeno un loop all'interno del loop principale, il tempo di esecuzione di questa istruzione è usato O (n ^ 2) o O (n ^ 3).

Esempio:

 for i = 1 to n do begin // (1+1)*n = 2n for j = 1 to n do begin // (1+1)n*n = 2n^2 x = x + 1; // (1+1)n*n = 2n^2 print(x); // (n*n) = n^2 end; end; 

Tempo di esecuzione comune

Ci sono alcuni tempi di esecuzione comuni durante l'analisi di un algoritmo:

  1. O (1) - Tempo costante Il tempo costante indica che il tempo di esecuzione è costante, non è influenzato dalla dimensione di input .

  2. O (n) - Tempo lineare Quando un algoritmo accetta n dimensioni di input, eseguirà anche n operazioni.

  3. O (log n) - Logarithmic Time Algorithm con tempo di esecuzione O (log n) è leggermente più veloce di O (n). Comunemente, l'algoritmo divide il problema in sotto-problemi con le stesse dimensioni. Esempio: algoritmo di ricerca binaria, algoritmo di conversione binaria.

  4. O (n log n) - Linearithmic Time Questo tempo di esecuzione si trova spesso negli "algoritmi divide & conquer" che dividono il problema in sotto-problemi in modo ricorsivo e quindi li uniscono in n time. Esempio: algoritmo Merge Sort.

  5. O (n 2 ) - algoritmo Quadratic Time Look Bubble Sort!

  6. O (n 3 ) - Cubic Time Ha lo stesso principio con O (n 2 ).

  7. O (2 n ) - Tempo esponenziale È molto lento quando l'input diventa più grande, se n = 1000.000, T (n) sarebbe 21000.000. L'algoritmo Brute Force ha questo tempo di esecuzione.

  8. O (n!) - Factorial Time THE SLOWEST !!! Esempio: Travel Salesman Problem (TSP)

Tratto da questo articolo . Molto ben spiegato dovrebbe dare una lettura.

In parole povere, la complessità temporale è un modo per riassumere come il numero di operazioni o il tempo di esecuzione di un algoritmo aumenta con l’aumentare della dimensione di input.

Come molte cose nella vita, un cocktail può aiutarci a capire.

SOPRA)

Quando arrivi alla festa, devi stringere la mano a tutti (fai un’operazione su ogni object). Man mano che aumenta il numero di partecipanti N , il tempo / lavoro che impiegherà a stringere la mano a tutti aumenta come O(N) .

Perché O(N) e non cN ?

C’è una variazione nella quantità di tempo necessaria per stringere la mano alle persone. Puoi fare una media di questo e catturarlo in una costante c . Ma l’operazione fondamentale qui — stringere la mano a tutti — sarebbe sempre proporzionale a O(N) , non importa quale c fosse. Quando discutiamo se dovremmo andare a un cocktail party, siamo spesso più interessati al fatto che dovremo incontrare tutti che nei minimi dettagli di come appaiono questi incontri.

O (N ^ 2)

L’ospite del cocktail party vuole che tu faccia un gioco stupido dove tutti incontrano tutti gli altri. Pertanto, devi incontrare N-1 altre persone e, poiché la persona successiva ti ha già incontrato, devono incontrare persone N-2 e così via. La sum di questa serie è x^2/2+x/2 . Man mano che aumenta il numero di partecipanti, il termine x^2 diventa molto veloce , quindi abbandoniamo tutto il resto.

O (N ^ 3)

Devi incontrare tutti gli altri e, durante ogni riunione, devi parlare di tutti gli altri nella stanza.

O (1)

L’host vuole annunciare qualcosa. Hanno un bicchiere da vino e parlano a voce alta. Tutti li sentono. Si scopre che non importa quanti partecipanti ci sono, questa operazione richiede sempre lo stesso tempo.

O (log N)

L’host ha disposto tutti al tavolo in ordine alfabetico. Dov’è Dan? Tu pensi che lui debba trovarsi da qualche parte tra Adam e Mandy (certamente non tra Mandy e Zach!). Detto questo, è tra George e Mandy? No. Deve essere tra Adam e Fred, e tra Cindy e Fred. E così via … possiamo localizzare in modo efficiente Dan guardando metà set e poi metà set. In definitiva, guardiamo a O (log_2 N) individui.

O (N log N)

Puoi trovare dove sederti al tavolo usando l’algoritmo sopra. Se un gran numero di persone si avvicinava al tavolo, uno alla volta, e lo facevano tutti, ciò avrebbe richiesto il tempo O (N log N) . Questo risulta essere il tempo necessario per ordinare qualsiasi raccolta di oggetti quando devono essere confrontati.

Caso migliore / peggiore

Arrivi alla festa e devi trovare Inigo: quanto tempo ci vorrà? Dipende da quando arrivi. Se tutti si aggirano, hai colto nel peggiore dei casi: ci vorra ‘ O(N) tempo. Tuttavia, se tutti sono seduti al tavolo, ci vorrà solo tempo O(log N) . O forse puoi sfruttare il potere urlante del wineglass dell’host e ci vorrà solo O(1) tempo.

Supponendo che l’host non sia disponibile, possiamo dire che l’algoritmo di Inigo-finding ha un limite inferiore di O(log N) e un limite superiore di O(N) , a seconda dello stato della parte al tuo arrivo.

Spazio e comunicazione

Le stesse idee possono essere applicate per capire come gli algoritmi usano lo spazio o la comunicazione.

Knuth ha scritto un bel articolo sul precedente intitolato “The Complexity of Songs” .

Teorema 2: esistono canzoni arbitrariamente lunghe di complessità O (1).

PROVA: (a causa di Casey e la Sunshine Band). Considera le canzoni Sk definite da (15), ma con

 V_k = 'That's the way,' U 'I like it, ' U U = 'uh huh,' 'uh huh' 

per tutti k.

Quando analizzi il codice, devi analizzarlo riga per riga, contando ogni operazione / riconoscendo la complessità del tempo, alla fine, devi sumrlo per ottenere un’immagine completa.

Ad esempio, puoi avere un ciclo semplice con complessità lineare , ma più avanti in quello stesso programma puoi avere un ciclo triplo con complessità cubica , quindi il tuo programma avrà una complessità cubica . L’ordine di crescita funzionale entra qui in gioco.

Diamo un’occhiata a quali sono le possibilità per la complessità temporale di un algoritmo, puoi vedere l’ordine di crescita che ho menzionato sopra:

  • Il tempo costante ha un ordine di crescita 1 , ad esempio: a = b + c .

  • Il tempo logaritmico ha un ordine di crescita LogN , di solito si verifica quando si divide qualcosa a metà (ricerca binaria, alberi, anche cicli) o si moltiplica qualcosa nello stesso modo.

  • Lineare , l’ordine di crescita è N , per esempio

     int p = 0; for (int i = 1; i < N; i++) p = p + 2; 
  • Linearitmico , l'ordine di crescita è n*logN , di solito si verifica negli algoritmi divide e conquista.

  • Cubico , ordine di crescita N^3 , l'esempio classico è un ciclo triplo in cui controlli tutte le terzine:

     int x = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) x = x + 2 
  • Esponenziale , l'ordine di crescita 2^N , di solito si verifica quando si esegue una ricerca esaustiva, ad esempio controllare i sottoinsiemi di alcuni set.

So che questa domanda fa un passo indietro e ci sono alcune risposte eccellenti qui, tuttavia ho voluto condividere un altro po ‘per le persone matematicamente mentali che inciamperanno in questo post. Il teorema del Maestro è un’altra cosa utile da sapere quando si studia la complessità. Non l’ho visto menzionato nelle altre risposte.

O (n) è una grande notazione O usata per scrivere la complessità temporale di un algoritmo. Quando sumte il numero di esecuzioni in un algoritmo otterrete un’espressione in risultato come 2N + 2, in questa espressione N è il termine dominante (il termine ha il più grande effetto sull’espressione se il suo valore aumenta o diminuisce). Ora O (N) è la combinazione di tempo mentre N sta dominando il termine. Esempio

 For i= 1 to n; j= 0; while(j<=n); j=j+1; 

qui il numero totale di esecuzioni per il ciclo interno sono n + 1 e il numero totale di esecuzioni per il ciclo esterno sono n (n + 1) / 2, quindi il numero totale di esecuzioni per l'intero algoritmo è n + 1 + n (n + 1/2 ) = (n ^ 2 + 3n) / 2. qui n ^ 2 è il termine dominante quindi la complessità temporale per questo algoritmo è O (n ^ 2)

Per avere un’idea di un algoritmo, lo faccio spesso sperimentalmente. Basta variare l’input N e vedere quanto dura il calcolo. Questo ha bisogno di un po ‘di riflessione, dato che big-O descrive la complessità temporale del caso peggiore dell’algoritmo, e trovare il caso peggiore può essere complicato.

Per farlo teoricamente, il tuo approccio mi sembra giusto: cammina attraverso il programma (scegliendo sempre il percorso più complesso nel tempo), aggiungi i tempi individuali e sbarazzati di tutte le costanti / fattori. Anelli annidati, salti, ecc. Possono renderlo abbastanza complesso ma non riesco a pensare a un proiettile d’argento per risolvere questo altrimenti.

Potresti anche essere interessato da http://en.wikipedia.org/wiki/Big_O_notation , nonostante sia abbastanza matematico.

Ho anche appena trovato http://en.wikipedia.org/wiki/Analisi_di_algoritmi