Complessità degli algoritmi

Ogni algoritmo è rappresentato con una procedura. Si usano operatori aritmetici come nel C e assegnamento <-. Per i commenti mono riga si usa ▷. Si hanno inoltre disponibili i costrutti di controllo while, for e if-else. Tutte le variabili sono locali alla procedura descritta, e il loro tipo non è esplicito. La notazione degli array è identica al C, con la differenza che gli indici iniziano da 1. Inoltre sono disponibili anche i sotto-array A[i..j. Sono presenti anche aggregati eterogenei (come gli struct in C), con la differenza che una variabile di tipo aggregato è un puntatore alla struttura. Il passaggio parametri ad una procedura è effettuato, per tipi non aggregati per copia, mentre per tipi aggregati per riferimento.

Lo pseudocodice è eseguito dalla macchina RAM, e assumiamo che un singolo statement di assegnamento tra tipi base è tradotto in un numero costante di istruzioni dell'assembly RAM.

Sono possibili 3 tecniche principali:

• Sostituzione
• Esame dell'albero di ricorsione
• Teorema dell'esperto (master theorem)

Usiamo come caso di studio la ricerca binaria, cioè il problema di cercare in un vettore lungo come quello di cercare nelle sue metà superiori e inferiori. Abbiamo che il costo della suddivisione è costante , il costo di ricombinazione è costante, cioè sappiamo che una delle due metà non contiene per certo l'elemento cercato . Quindi esprimiamo la complessità come:

Il metodo di sostituzione si articola in tre fasi:

• Intuire una possibile soluzione
• Sostituire la presunta soluzione nella ricorrenza
• Dimostrare per induzione che la presunta soluzione è tale per l'equazione/disequazione delle ricorrenze.

L'albero di ricorsione fornisce un aiuto per avere una congettura da verificare con il metodo di sostituzione, o un appiglio per calcolare la complessità esatta. È una rappresentazione delle chiamate ricorsive, con la loro complessità. Ogni chiamata costituisce un nodo in una sorta di albero genealogico: i chiamati appaiono come figli del chiamante. Ogni nodo contiene il costo della chiamata, senza contare quello dei discendenti.

Per esempio, l'albero :

L'albero ha la ramificazione a profondità massima posta all'estrema destra del disegno precedente. Sappiamo che essa ha profondità che ricaviamo ponendo . Facendo un po di algebra ricaviamo , e quindi . Quindi il costo pessimo per il contributo di un dato livello è l' del primo livello, e quindi .

Data una ricorrenza nella seguente forma: Confrontiamo . Se abbiamo che:

• costante
• sommata, non sottratta
• Legame tra e polinomiale

Nel caso per un qualunque , allora la complessità risultante: Nel caso , la complessità risultante: Nel caso per un qualunque , e vale per un qualunque , la complessità risultante:

InsertionSort(A)
	for i <- 2 to A.lenght
		tmp <- A[i]
		j <- i - 1
		while j >= 1 and A[j] > tmp
			A[j+1] <- A[j]
			j <- j - 1
		A[j + 1] <- tmp
Copy

Si ha che, seleziono un elemento e lo reinserisco nella porzione di vettore già ordinato, al suo posto. Si ha nel caso ottimo , nel caso pessimo e nel caso medio . La complessità spaziale . L'algoritmo è stabile.

Contando le azioni di confronto e scambio generiche di un vettore ricaviamo un albero con tante foglie quante permutazioni del vettore da ordinare. Assumendo che la struttura sia la più compatta possibile, la lunghezza del più lungo dei percorsi radice-foglia è il numero massimo di confronti che devo fare per ordinare un vettore, allora l'altezza dell'albero in questo caso è del numero delle sue foglie: Quindi la complessità migliore ottenibile è .

Merge(A,p,q,r)
	len1 <- q - p + 1
	len2 <- r - q
	Alloca(L[1..len1+1])
	Alloca(R[1..len2+1])
	
	for i <- 1 to len1
		L[i] <- A[p + i - 1]
	
	for i <- 1 to len2
		R[i] <- A[q + i]
	
	L[len1 + 1] <- ∞
	R[len2 + 1] <- ∞
	i <- 1
	j <- 1
	
	for k <- p to r
		if L[i] <= R[j]
			A[k] <- L[i]
			i <- i + 1
		else
			A[k] <- R[j]
			j <- j + 1

MergeSort(A,p,r)
	if p < r - 1
		q <- floor((p + r)/2)
		MergeSort(A,p,q)
		MergeSort(A,q+1,r)
		Merge(A,p,q,r)
	else
		if A[p] > A[r]
			tmp <- A[r]
			A[r] <- A[p]
			A[p] <- tmp
Copy

L'algoritmo Merge alloca due array ausiliari, grossi quanto le parti da fondere, più alcune variabili ausiliarie di numero fissato, quindi ha complessità spaziale .
Tralasciando le porzioni sequenziali, l'algoritmo Merge è composto da cicli, due per copiare le parti da fondere (), e uno che copia in gli elementi in ordine (). Quindi Merge è . Il costo quindi è:

Quicksort è un algoritmo di ordinamento senza spazio ausiliario, e applica un il principio divide-et-impera ad una slice A[lo..hi]. In questo caso scegliamo un elemento A[p] detto pivot come punto di suddivisianoe, e sposta gli elementi di A[lo..hi] in modo che tutti quelli di A[lo..p-1] siano minori o uguali al pivot, e quindi si ordina A[lo..p-1] e A[p+1..hi] con quicksort

QuickSort(A,lo,hi)
	if lo < hi
		p <- Partition(A,lo,hi)
		Quicksort(A,lo,p-1)
		Quicksort(A,p+1,hi)
Copy

Abbiamo diversi schemi di partizione:

PartitionLomuto(A,lo,hi)
	pivot <- A[hi]
	i <- lo - 1
	
	for j <- lo to hi - 1
		if A[j] <= pivot
			i <- i + 1
			Scambia(A[i],A[j])
	
	Scambia(A[i + 1], A[hi])
	return i + 1
	
PartitionHoare(A,lo,hi)
	pivot <- A[lo]
	i <- lo - 1
	j <- hi + 1
	
	while true
		repeat
			j <- j -1
		until A[j] <= pivot
		
		repeat
			i <- i + 1
		until A[i] >= pivot
		
		if i < j
			Scambia(A[i], A[j])
		else return j
Copy

In entrambi i casi il calcolo di Partition ha complessità temporale con lunghezza del vettore su cui deve operare la partizione. La complessità di Quick Sort risulta quindi: Dove dipende da "quanto bene" Partition ha suddiviso il vettore. Quindi ha come caso pessimo , caso ottimo e caso medio . Quick Sort non è stabile.

CountingSortNonStabile(A)
	Ist[0..k] <- 0
	
	for i<- 0 to A.length - 1
		Ist[A[i]] <- Ist[A[i]] + 1
	
	IdxA <- 0
	for i <- 0 to k
		while Ist[i] > 0
			A[idxA] <- i
			idxA <- idxA + 1
			Ist[i] <- Ist[i] - 1

CountingSortStabile(A)
	B[0..A.length - 1] <- 0
	Ist[0..k] <- 0
	
	for i <- 0 to A.length - 1
		Ist[A[i]] = Ist[A[i]] + 1
	
	sum <- 0
	for i <- 0 to k
		sum <- sum + Ist[i]
		Ist[i] <- sum
	
	for i <- A.length - 1 to 0
		idx <- Ist[A[i]]
		B[idx - 1] <- A[i]
		Ist[A[i]] <- Ist[A[i]] -1
Copy

Il Counting Sort è un algoritmo che non si basa sul confronto diretto di elementi di un vettore. Ne esiste una versione stabile e non stabile. Consideriamo valore massimo degli elementi. Si ha che la complessità temporale è dominata dall'ultimo ciclo: