Come misurare la complessità degli algoritmi

" Complessità " in termini di algoritmi si riferisce a come il involvedness della struttura dell'algoritmo influisce sulla velocità di esecuzione dell'algoritmo dopo l'introduzione dei dati . Per valutare la complessità degli algoritmi , matematici e informatici utilizzano Big Oh notazione , che è una tecnica matematica che permette di calcolare quantitativamente la velocità di marcia ( la complessità ) dell'algoritmo . Istruzioni
1

Scrivi l'algoritmo nella sua forma funzionale per tempo di esecuzione . Ogni algoritmo è diverso in questo senso , e si avrà mai la sua vera forma --- solo una stima . È possibile ottenere la stima guardando il codice dell'algoritmo stesso e contando il numero di unità di tempo necessario per l'algoritmo per terminare il calcolo di un ingresso di dimensioni "n ". Scrivere questa funzione come "f ( n) . " Ad esempio, un " ciclo for ", che inizia a 1 e finisce al n avrà la funzione f ( n) = n la sua stima del tempo di esecuzione.
2

Stimare un limite superiore per f ( n ) . Un limite superiore è un numero che f ( n) non può passare dopo un valore sufficientemente grande di n . Ad esempio , se f ( n) = n ^ 3 + 10n + 3 , una scelta logica per una stima limite superiore sarebbe c * n ^ 3 , dove c è una costante maggiore di 1 . Questa è una scelta ragionevole dal c * n ^ 3 è più grande della più grande termine in f ( n) .
3

Scrivi il limite superiore in notazione matematica . Scrivere f ( n) < limite superiore . Per l'esempio precedente , questo è n ^ 3 + 10n + 3 < c * n ^ 3 .
4

Dimostrare che questa disuguaglianza vale per grandi valori di n . Di solito , si tratta di risolvere la disuguaglianza per c e controllando se il risultato vale . Nell'esempio precedente , utilizzando l'algebra produce la disuguaglianza c > 1 + 10 * n ^ -2 + 3 * n ^ -3 . Per n grande , i valori con esponenti negativi vanno a zero, lasciando c > 1 . Questa disuguaglianza è vero perché si affermava che era vero quando fu scelto c .

Se la disuguaglianza , la complessità dell'algoritmo è O ( stimato limite superiore senza il costante) . Ad esempio, poiché la disuguaglianza tenuta , la complessità è O ( n ^ 3 ) . Se la disuguaglianza non regge , è necessario stimare un nuovo limite superiore ed eseguire nuovamente il processo .