// c’è tutto ma vorrei spiegare un po’ meglio alcuni passaggi

divide-et-impera

Il divide et impera è un approccio di risoluzione di problemi che si basa sulla divisione di un problema in sotto-problemi indipendenti, che vengono risolti ricorsivamente. In generale, è formato da 2+1 step:

  1. divide: il problema viene suddiviso in più sotto-problemi simili a quello originale, che vengono a loro volta suddivisi ricorsivamente finché possibile
  2. impera: si risolvono ricorsivamente i sotto-problemi
  3. (combina: i risultati vengono combinati fino a formare una soluzione del problema di partenza)

problema della selezione

Data una lista di interi distinti e un intero , con , vogliamo sapere quale elemento occuperebbe la posizione se il vettore venisse ordinato.

casi particolari

  • sarà il minimo di
  • sarà il massimo di
  • sarà il mediano di

algoritmo naïf

Un possibile algoritmo in è questo:

def selezione1(A, k):
	A.sort()
	return A[k-1]

Utilizzando la tecnica del divide et impera, il problema può però risolversi in .

  • si dimostra quindi che il problema della selezione è computazionalmente più semplice di quello dell’ordinamento

algoritmo divide et impera

  • si sceglie nella lista l’elemento in posizione (perno)
  • a partire da , si costruiscono due liste e , la prima contenente gli elementi minori del perno e la seconda contenente gli elementi maggiori del perno
  • per trovare l’elemento di rango :
    • se , l’elemento è nel vettore
    • se , l’elemento è il perno
    • se , l’elemento è l’elemento di con rango
def selezione(A, k):
	if len(A) == 1:
		return A[0]
		
	pivot = A[0]
	A1, A2 = [], []
	
	for i in range(1,len(A)):
		if A[i] < pivot:
			A1.append(A[i])
		else:
			A2.append(A[i])
			
	if len(A1) >= k:
		return selezione(A1,k)
	elif len(A1) == k-1:
		return pivot
	return selezione(A2, k-len(A1)-1)

La procedura che tripartisce la lista in e può restituire una partizione massimamente sbilanciata in cui ad esempio e se il perno è l’elemento minimo nella lista. Qualora succedesse sistematicamente per tutte le partizioni eseguite dall’algoritmo, allora la complessità dell’algoritmo sarebbe:

In generale, la complessità superiore della procedura è catturata dalla ricorrenza

dove .

bilanciamento

Se avessimo una regola di scelta del perno in grado di garantire una partizione bilanciata, ovvero , allora la complessità sarebbe .

Ma potremmo anche accontentarci di avere partizioni non perfettamente bilanciate, ma semplicemente non troppo sbilanciate, come quelle per cui . In questo caso si avrebbe .

In generale, finché è una frazione di , la ricorrenza dà sempre .

scelta equiprobabile di

Se scegliamo a caso in modo equiprobabile tra gli elementi della lista, non si creerà necessariamente una partizione bilanciata ma la complessità rimane lineare in .

def selezioneR(A,k):
	if len(A)==1:
		return A[0]
		
	pivot = A[randint(0, len(A)-1)]
	A1, A2 = [], []
	
	for x in A:
		if x<pivot:
			A1.append(x)
		elif x>pivot:
			A2.append(x)
			
	if len(A1) >= k:
		return selezioneR(A1,k)
	elif len(A1) == k-1:
		return pivot
	return selezioneR(A2, k-len(A1)-1)

Analisi formale del caso medio

Con la randomizzazione introdotta per la scelta del pivot possiamo assumere che uno qualunque degli elementi del vettore, con uguale probabilità , diventi pivot e, poiché la scelta dell’elemento di rango produce e , per il tempo atteso dell’algoritmo va studiata la ricorrenza:

Possiamo dimostrare che per questa ricorrenza vale tramite il metodo di sostituzione.

Dimostriamo per una qualunque costante Per abbiamo che è vera ad esempio per .

Sfruttando l’ipotesi induttiva per abbiamo

da cui ricaviamo

dove l’ultima diseguaglianza segue prendendo in modo che ; basta ad esempio prendere .

Abbiamo quindi dimostrato che il tempo dell’algoritmo selezioneR è con alta probabilità.

  • ovviamente, nel caso peggiore (quando si verifica che il perno scelto a caso risulta sempre vicino al massimo o al minimo della lista), la complessità dell’algoritmo rimane ; questo accade però con probabilità molto piccola

algoritmo deterministico in

Riuscire a selezionare un perno che garantisca che nessuna delle due sottoliste e abbia più di elementi per una qualche costante porta ad una complessità di .

Esiste un metodo chiamato mediano dei mediani che permette di selezionare un perno che garantisce sempre due sottoliste e con ciascuna non più di elementi.

algoritmo

  • si divide l’insieme contenente elementi in gruppi da 5 elementi ciascuno (l’ultimo gruppo potrebbe avere meno di 5 elementi).
  • si considerano solo i primi gruppi, ciascuno composto esattamente da 5 elementi.
  • si trova il mediano di ciascuno di questi gruppi
  • si calcola il mediano dei mediani ottenuti al passo precedente, e si usa come pivot per

esempio:

center

proprietà

Se la lista contiene almeno 120 elementi e il perno viene scelto in base alla regola, si può dire per certo che la dimensione delle due sottoliste sarà limitata da .

dimostrazione ha la proprietà di trovarsi in posizone nella lista degli mediani selezionati. Ci sono dunque mediani di valore inferiore a e .

prova per

Consideriamo i mediani di valore inferiore a . Ognuno di questi appartiene ad un gruppo di 5 elementi in . Ci sono dunque in altri 2 elementi inferiori a per ogni mediano. In totale abbiamo quindi

elementi di in .

Quindi,

(dove perché ).

prova per

Ci sono invece

mediani di valore superiore a . Ognuno di questi appartiene ad un gruppo di 5 elementi in . Ci sono quindi in altri due elementi superiori a per ogni mediano. In totale abbiamo quindi almeno elementi di che finiranno in .

Abbiamo quindi

(dove perché )

implementazione:

from math import ceil
 
def selezione(A,k):
	if len(A)<=120: # costo costante 120 log 120
		A.sort()
		return A[k-1]
	
	# inizializza B con i mediani dei len(A)//5 gruppi di 5 elementi di A
	# (sorta i gruppi di 5 e prende il terzo elemento)
	B = [sorted(A[5*1 : 5*i+5])[2] for i in range(len(A)//5)] #
	
	# individua il pivot p con la regola del mediano dei mediani
	pivot = selezione(B, ceil(len(A)/10))
	A1, A2 = [], []
	
	for x in A:
		if x<pivot:
			A1.append(x)
		elif x>pivot:
			A2.append(x)
			
	if len(A1) >= k:
		return selezione(A1,k)
	elif len(A1) == k-1:
		return pivot
	return selezione(A2, k-len(A1)-1)

sappiamo che:

  • ordinare 120 elementi richiede
  • ordinare una lista di elementi in gruppi da 5 richiede
  • selezionare i mediani dei mediani di gruppi da 5 da una lista in cui gli elementi sono stati ordinati in gruppi da 5 richiede

Sappiamo che per , si ha e l quindi per la complessità dell’algoritmo si ha:

equazione di ricorrenza

La ricorrenza è del tipo

con , e questo tipo di ricorrenze hanno tutte come soluzione .

dimostriamolo (metodo dell'albero)

Il fatto che gioca un ruolo fondamentale nella prova.

Consideriamo l’albero delle chiamate ricorsive e analizziamone il costo per livelli:

center

  • al primo livello abbiamo un costo , al secondo un costo , al terzo un costo e così via

Il tempo di esecuzione totale è la somma dei costi dei vari livelli:

(dove nel calcolare la serie si sfrutta il fatto che e la serie geometrica con converge a )

Abbiamo quindi dimostrato che il problema della selezione può essere risolto in tempo lineare., con un algoritmo che risolve il problema in al caso pessimo. Tuttavia, a causa delle grandi costanti moltiplicative nascoste dall’, nella pratica l’algoritmo randomizzato che ha tempo con alta probabilità si comporta molto meglio.