Complessità di un algoritmo

> Tutorial LeekScript

Idea generale

Per stimare la quantità di operazioni che consumerà una funzione o un algoritmo, è utile avere un'idea della relazione tra la dimensione degli argomenti ad essa dati, o la dimensione di un parametro, e il numero massimo di operazioni eseguite . Questa si chiama complessità algoritmica.

Iniziamo con un semplice esempio: un ciclo for.

for (var i=0; i N, si ha f(n) < K xg(n).*

Va bene, ecco qua, ho pronunciato i paroloni. Cosa significa concretamente questa definizione? Che la funzione f cresce "non più velocemente" di g al crescere di n. f può essere maggiore di g, ma il rapporto tra i due è sempre minore di un certo numero (il K della definizione). Applichiamo questo al codice: prendiamo come funzione (matematica) f il numero massimo di operazioni eseguite da un dato pezzo di codice, data la dimensione del suo input. Cerchiamo di trovare una semplice funzione g tale che f(n)=O(g(n)). Si tratta, all'incirca, di misurare il maggior numero di volte che le istruzioni di base verranno ripetute nel codice (il costo di queste istruzioni viene così nascosto sotto il tappeto: è la K della definizione).

Esempi

Accidenti. Passiamo agli esempi, vedremo più chiaramente. Torniamo al nostro ciclo for di prima:

for (var i=0; i<n; i++){ say("Sono una carota"); }

Se annotiamo f il numero massimo di operazioni eseguite da questo pezzo di codice, abbiamo visto che f(n) era approssimativamente uguale a 30 x n, più il piccolo costo del ciclo. In effetti, l'istruzione say viene ripetuta n volte, il che ha un costo costante di 30 operazioni. Possiamo quindi dire che f è dominata dalla funzione g(n)=n. Quindi, abbiamo f(n)=O(n). Diciamo anche che questo pezzo di codice è "in O(n)".

E la funzione di intersezione di array di dimensione n? Abbiamo visto che consuma approssimativamente n² x (numero di operazioni push + costo del confronto tra due elementi). Assumendo che il costo push sia costante (il che è falso, ma non voglio entrare subito nel dettaglio), abbiamo, ponendo K = (numero di operazioni push + costo del confronto tra due elementi), che il costo di la funzione di intersezione è dominata da n²: diciamo che la funzione di intersezione è "in O(n²)".

Pertanto, la notazione O consente di misurare la crescita del costo in funzione della dimensione dell'input: la funzione di intersezione avrà un costo che cresce "alla stessa velocità" di n² (con n la dimensione degli array).

Interesse per Leekwars

Questa nozione è interessante perché spesso possiamo stimare abbastanza facilmente un O(g(n)), e quindi sapere se una funzione comincerà a costare molto quando l'input aumenterà. È per esempio uti