Analisi degli algoritmi

Lo studio di un algoritmo è fondamentale per individuare errori concettuali e migliorare l’efficienza del codice. Il mondo della programmazione è in grado di offrirci sempre nuove sfide. Cerchiamo quindi di capire come progettare “buoni” algoritmi.

Cos’è un algoritmo?
L’informatica è la scienza che studia la RAPPRESENTAZIONE, l’ELABORAZIONE, la CONSERVAZIONE e la TRASMISSIONE delle informazioni mediante strumenti automatici. Programmare significa sviluppare programmi ed ognuno di essi richiede la soluzione di problemi. Questa soluzione, ovvero la strategia che indica come ottenere i risultati, è detta algoritmo.

Nonostante le risorse hardware a disposizione dei moderni pc siano abbondanti, ogni sviluppatore ricerca per le sue applicazioni la strategia migliore, quella cioè che:

• presenta la minore complessità computazionale
• risulta di facile codifica nel linguaggio di programmazione adottato

Lo strumento usato per l’analisi degli algoritmi consiste nell’associare, ad ogni algoritmo, una funzione f(n) che individua il tempo di esecuzione dello stesso in funzione della grandezza n dell’input.
.
Cos’è la complessità computazionale?
Ogni programma è in esecuzione su un calcolatore ed utilizza per le sue elaborazioni dati la memoria ram. Quando definisce ed inizializza una variabile, occupa un certo numero di byte in memoria (a seconda del linguaggio di programmazione e dello standard).
.
Più variabili e strutture dati utilizzerà il programma, maggiore sarà il suo “peso” sul sistema, soprattutto in termini di tempo di elaborazione. Pensiamo ad un software aziendale che gestisce giornalmente migliaia di clienti. Un programma del genere dovrà essere performante, cioè dovrà eseguire il minor numero di elaborazioni possibile.
.
Questo è il concetto di complessità computazionale, che viene indicata con la notazione O(n), dove n indica il numero di ripetizioni di un certo numero di istruzioni.
.
Studio della complessità computazionale?
Ad ogni istruzione (ogni riga) viene assegnato un valore da 1 a n, in funzione del tempo di elaborazione che richiede. Questo valore viene indicato con O(n). Per stabilire l’efficienza dell’algoritmo, al variare dell’input che dovrà gestire, si valutano i seguenti casi:

• Caso migliore
• Caso medio
• Caso peggiore

Complessità di un algoritmo
Un algoritmo non ricorsivo è scomponibile in un insieme di istruzioni sequenziali, di condizioni e di cicli. Esistono delle regole per calcolare la complessità asintotica per ciascuna delle suddette istruzioni.

1. Complessità di una selezione:
   • il tempo di esecuzione di un’istruzione di selezione ad un’uscita (if) è:
     O(cond(n) + BloccoIf(n)).
   • Il tempo di esecuzione di un’istruzione di selezione a doppia uscita (if-else) è:
     O(cond(n) + max(BloccoIf(n), BloccoElse(n))).
2. Complessità di un ciclo: Il tempo di esecuzione di un ciclo è il prodotto tra il numero massimo di iterazioni che può effettuare e il massimo valore tra il tempo di valutazione della condizione del ciclo e il tempo necessario all’elaborazione delle istruzioni presenti nel blocco. Cioè:
   O(nIteraz(n) * max(cond(n), BloccoCiclo(n))).
   • Casi particolari: quando il ciclo è a condizione iniziale o finale, oppure è un ciclo annidato nel quale quello più interno dipende dal contatore di quello più esterno o ancora quando il contatore del ciclo viene modificato anche dalle istruzioni del blocco, può essere difficile trovare il numero effettivo di iterazioni; in questi casi è necessario fare congetture matematiche.

Vediamo alcuni esempi commentati:

1
2
3
4
5
6
7
8
9
10

/* Studio della Complessità computazionale
   DevBlog - www.methack.it
*/
 
int myCFunction (int *b, int n) {
	int a[n], i; /* istruzione elementare. Complessità O(1) */
	for(i=0; i<n; i++) /* Il confronto i<n è O(1). Il ciclo for è O(n), perchè si ripete n volte */
		a[i] = b[i]; /* istruzione elementare. Complessità O(1) */
	return a; /* istruzione elementare. Complessità O(1) */
}

Questo algoritmo ha complessità totale O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/* Studio della Complessità computazionale
   DevBlog - www.methack.it
*/
/* Supponendo che f1() abbia complessità O(n)
				  f2() abbia complessità O(log(n))
				  f3() abbia complessità O(n*log(n))
*/
int myCFunction (int n) {
	int i;
	for(i=0; i<n; i++) /* Il confronto i<n è O(1). Il ciclo for è O(n), perchè si ripete n volte */
		if(f1()) /* f1() è O(n) */
			f2(); /* f2() è O(log(n)) */
		a[i] = b[i]; /* istruzione elementare. Complessità O(1) */
	return a; /* istruzione elementare. Complessità O(1) */
}

Seguendo le regole sopra esposte, questo algoritmo ha complessità totale O(n² + n*log(n)).

Dietro ad ogni algoritmo si possono nascondere calcoli matematici, studi e ottimizzazioni molto importanti, ed è bene saperlo!

Articoli popolari:

• Filmati Flash (.flv) nel tuo sito web
  Social network, blog, cms e forum. Le applicazioni web sono sempre più utilizzate dagli utenti che spesso vogliono condividere immagini e video nel loro spazio internet. In molti casi si tratta di sc...
• Creare un social network gratis come Facebook
  In Rete ci sono tanti strumenti per creare e gestire un sito internet: blog, cms e forum board. Sono piattaforme predisposte per essere subito operative e permettono agli utenti di inserire e aggiorna...
• Socket in Java e semplice chat
  Affrontiamo i socket nel linguaggio Java creando una semplice chat compatibile con tutti i sistemi operativi dotati di JVM. Questo articolo inoltre offre una breve panoramica delle applicazioni di ret...
• Come richiamare una funzione PHP tramite Javascript!
  Questo articolo fa eco a centinaia di richieste pubblicate nei forum di mezzo Internet. Vorrei dunque proporre ai lettori un comodo, step-by-step, procedimento per scoprire come richiamare funzioni la...
• La crescita degli esperti SEO, serie dei Fibonacci
  Sarà una moda, un lavoro stra-pagato o il business più semplice da condurre, ma gli esperti di marketing si stanno moltiplicando come conigli. Tutti i giorni su twitter, che è il social che seguo magg...
• Attacco ai siti web su Aruba, strano security_update e codice cifrato
  Molti siti web in hosting presso i server di Aruba sono stati infettati, nei giorni scorsi, da un malware (fortunatamente) innocuo per i visitatori, ma "nocivo" per i webmasters. Questo episodio ...