[ALGORITMO] Calcolo della complessità di un algoritmo di ordinamento

[gaten]

Salve ragazzi ,
se risulto avere un algoritmo di "selection sort" oppure "exchange sort" o "merge sort", qualcuno sà dirmi come viene calcolata la complessità di questi algoritmi?
In generale, come viene calcolata la complessita computazionale di un algoritmo?

Grazie anticipatamente...

[YuYevon]

Su come si calcola la complessità di un algoritmo ci sono interi capitoli di appositi libri, riassumere i concetti anche per sommi capi diventa un'impresa quasi impossibile. Volendo provarci lo stesso, se si tratta di algoritmi *non ricorsivi* devi analizzare essenzialmente i cicli iterativi: quanti ne sono? Sono annidati? Quante iterazioni esegue ciascuno di essi? Il numero di iterazioni è sempre lo stesso o varia a seconda dell'input?

Magari posta qualche algoritmo come uno di quelli che hai elencato prima (in pseudocodice o in qualsiasi linguaggio di programmazione, purché sia pulito e chiaro) e se ne discute. Se poi ti interessa conoscere solo la loro complessità senza sapere come si calcola, sul web queste cose le trovi ovunque.

[gaten]

void sel_sort(float *A, int n){
int i, j, p;
float min;

for (i=0; i<n-1; i++) {
min = A[i];
p = i;
for (j=i+1; j<n; j++){
if (A[j]<min){
min = A[j];
p = j;
}
}
A[p] = A[i];
A[i] = min;
}
}

Ecco qui

[YuYevon]

Sì però esistono i tag code... non sei nuovo del forum, dovresti saperlo

Comunque, lì abbiamo due cicli for innestati. Quello esterno viene ripetuto n-1 volte, e ad ogni iterazione c'è un ciclo interno che viene ripetuto n - (i+1) volte. Quando i vale 0, abbiamo quindi n-1 iterazioni del ciclo interno; quando i vale 1, n-2 iterazioni; i = 2, n-3 iterazioni e così via fino a che i non vale proprio n-2 (ultimo valore assunto): in quel caso il ciclo interno viene ripetuto solo 1 volta.

In pratica quindi hai un numero di iterazioni totale pari a (n-1) + (n-2) + (n-3) + ... + 1; se n vale, ad esempio, 5, lì hai 4 + 3 + 2 + 1, cioè in pratica la somma dei primi n-1 numeri naturali. Come si calcola questa somma? Esiste la famosa formula di Gauss che in generale, per la somma dei primi n numeri naturali, è

n*(n+1)/2

ora noi dobbiamo sommare i primi n-1 numeri naturali, quindi abbiamo:

(n-1)*(n-1+1)/2 = (n-1)*(n)/2 = (n^2 - n)/2

questa quantità è quadratica, il suo ordine di grandezza è dato dal quadrato di n (il termine di primo grado è trascurabile rispetto a n^2), per tanto concludiamo dicendo che la complessità temporale asintotica dell'algoritmo è O(n^2), cioè è nell'ordine di n^2, il che non significa che il numero di iterazioni sia esattamente n^2.

In realtà parlavi di "complessità", non di "complessità asintotica", ma forse itendevi proprio questo...

[GliderKite]

L'ordinamento per selezione (Selection Sort) è un algoritmo quadratico, sia nel caso peggiore che in quello medio, in place, cioè non richiede memoria extra.

In particolare effettua circa N^2/2 confronti ed N scambi. Se esamini il codice dell'algoritmo in C (ad esempio):

/* SELECTION SORT */
void selectionSort( Item * const vector, const size_t size )
{
	unsigned i, j, small;

	for( i = 0; i != size-1; ++i )
	{
		small = i;

		for( j = i+1; j != size; ++j )
		{
			if( vector[ j ] < vector[ small ] )
				small = j;
		}

                // scambia gli elementi del vettore in posizione i e small
		swap( vector, small, i );
	}
}

Si nota come per ogni i c'è uno scambio e N-i confronti (dove N è il numero di elementi dell'array), per un totale di N-1 scambi e N(N-1)/2 confronti (quindi O(n^2)). Osservazioni che non dipendono dalla natura dei dati in ingresso.

L'unica cosa che dipende dalla tipo di input è il numero di volte che viene aggiornato il valore della variabile small, nel caso peggiore questo numero può essere quadratico, mentre nel caso medio (non saprei però dimostrartelo) vale O(N logN ).

[Hysoka]

sono 4 anni che faccio corsi di algoritmi all'università (3 corsi), e ancora ci fanno studiare sul cormen che, x chi non lo sapesse, si chiama Introduzione agli algoritmi.
Diciamo che l'argomento è leggermente più complesso di quel che sembra.