Skip to content

Latest commit

 

History

History
208 lines (149 loc) · 5.79 KB

9. Statistiche d'ordine.md

File metadata and controls

208 lines (149 loc) · 5.79 KB

Selezionare l' $i$esimo elemento più piccolo di $n$ elementi (L'elemento con rango $i$ )

Tip

  • $i=1$ minimo
  • $i=n$ massimo

Algoritmo "ingenuo" : ordinare e scegliere l'elemento di indice $i$, impiegherebbe un tempo di esecuzione peggiore di $\Theta(n \log n)$ usando [[5. Divide et impera#Merge Sort|merge sort]] o [[7. Heapsort|heapsort]].

Questo però non ci da la complessità intrinseca del problema.

[!example] Se vogliamo trovare l'elemento piccolo (o massimo) basta scorrere la lista e trovarli con gli algoritmi già studiati, impiegherebbe un tempo lineare.

Se vogliamo trovare il il secondo elemento più piccolo, basta trovare il più piccolo e rimuoverlo, cercando di nuovo l'elemento più piccolo sarà il secondo (e viceversa con il secondo elemento più grande). In questo caso il tempo di esecuzione è sempre lineare, in quanto impiegherebbe $2n$.

[!check] Utilizzando questo sistema la complessità dell'algoritmo è $in$

Questa complessità è lineare finché $i$ è una costante.

Quando $i=f(n)$

[!eexample] Mediana

  • $n$ dispari $f(n) = \frac {n+1}2$
  • $n$ pari $f(n) = \lfloor \frac {n+1}2 \rfloor \lceil \frac {n+1}2 \rceil$

La complessità diventa $f(n)n$, il caso peggiore avviene con la mediana.

Divide and Conquer Random

Rand-Select(A, p, q, i): => iesimo elemento più piccolo di A[p...q]
	if p > q: 
		return A[p]
	r = Rand-Partition(A,p,q)
	k = r - p - 1 => k = rank(A[r])
	if i == k: 
		return A[r]
	if i < k:
		return Rand-Select(A, p, r-1, i)
	else:
		return Rand-Select(A, r+1, q, i-k)

Ricerca Del Rango

[!question] Qual è il rango di $A[r] \in A$?

index 1 2 3 4 5 6 7 8
A 8 7 1 9 2 5 3 6

$rank(A[3]) = 1$

[!question] Qual è l'elemento di rango $i$? Trovo l'elemento più piccolo dell'array e ripeto con fino a che non diventa 1.

[!example] $$4;2;7;3;4;5;10;11\quad i=3$$ $$2|4;7;3;4;5;10;11\quad j=1$$ $$2;3|;7;4;4;5;10;11\quad j=2$$ $$2;3;4|;7;4;5;10;11\quad j=3$$ in questo caso l'elemento di rango 3 è 4

Partizionamento

Osserviamo che dato x, trovare il rank(x) è facile. Basta trovare quanti elementi sono < x, basta quindi usare [[6. Quicksort#Partizionamento|partition]]

partition(A, i, f, r):
	t = i
	perno = A[r]; scambia(A[i], A[r])
	for j = i+1 to f:
		if A[j] < perno:
			t = t+1
		scambia(A[t], A[j])
	scambia(A[t+1], A[i])
	return t+1

[!example] | i | 1|2|3|4|5|6|7|8| |---|---|---|---|---|---|---|---|---| |A|5|1|9|2|4|5|6|5| |A1|5|1|9|2|4|8|6|3| |A2|t|$$ ||||| |A3|5|1|2|9|4|8|6|3| |A4|5|1|2|4|3|8|6|9| $t=5$ partition(A, 1, 8, 6) = rank(A[6])

Idea

per cercare l'elemento di rango $i$ prima testo il rango di un qualunque elemento $x$

cerca(A, s, e, i):
	k = rank(x) in (A, S, e)
	if i == k:
		return i
	if  i < k:
		//cerco a sinistra tra i valori < x
	else:
		//cerco a destra tra i valori > x

[!tip] Tecnicalities Quando cerco a sinistra, cerco l'elemento di rango i. Quando cerco a destra, cerco l'elemento di rango i-k, perché se cerco a destra "escludo" elementi e quindi il rango decresce.

Worst Case

$$T(n) = max(t(left), t(right)) + \Theta(n)$$

Bisogna trovare un valore di $left$ e $right$ tale che $T(n) \in \Theta(n)\implies left+right=n-1$

$$left=\frac n2,\quad right=\frac n2-1$$

Ma va bene qualsiasi frazione di $n$

title: Esempio $k=\frac n7$

$$T(n)=max(T(\frac n7), T(\frac 67n)) + n$$

Ottimizzare Il Partizionamento

Abbiamo un algoritmo che costa $n$ sia nel caso medio che nel caso ottimo.

[!question] Esiste un algoritmo che nel caso pessimo impiega $n$? La scelta del perno non deve essere del tutto casuale. Devo garantire che il perno abbia "abbastanza" elementi sia a sinistra che a destra (una frazione di $n$)

posso formare $\lceil \frac n5 \rceil$ gruppi da 5 e li ordino.

![[Pasted image 20230302163347.png| center]]

Ottengo che la mediana di ogni gruppetto ha rango $k\geq 3$, di seguito cerco la mediana tra tutte le mediane (nell'esempio l'elemento di rango 4) .

![[Pasted image 20230302163504.png|center]]

Trovata la mediana creo un sottogruppo con l'angolo in basso a destra / in alto a sinistra e trovo ricorsivamente la mediana di quel sottogruppo.

Tutti gli elementi maggiori o uguali della mediana vanno a finire sotto, tutti quelli minori o uguali vanno a finire sopra.

Per la proprietà transitiva, tutti gli elementi del sottogruppo sono minori o uguali alla mediana (o maggiori o uguali).

selection(A, s, e, i):
	if s == e:
		return e
	//formo gruppi da 5
	//ordino ogni gruppo
	//cerco la MM
	k = partition(A, s, e, MM)
	z = rank(MM) = k - s + 1
	if z == i:
		return MM
	else:
		if z > i:
			return cerca(A, s, k, i)
		else:
			return cerca(A, k, e, i - z)

Alla destra di MM ci stanno al più $n - (\frac 3 {10} n)$ elementi, e alla sua destra ci stanno al più $n-(\frac 3{10}n-6)$ elementi

Important

Ricordare che la ricorsione avviene al più su $\frac 7{10}n+6$ elementi

$$T(n) = \substack{T(\frac n5)\\text{cerco MM}} + \substack{T(\frac 7{10} n + 6) \ \text{cerco a Sx o Dx}} + \substack{\Theta(n)\\text{partition}} $$

$$T(n) \in \Theta(n)$$

[!seealso] Gruppi da 7 Tempo ordinamento: $\frac n7 = \Theta(1)+n$ $$T(n) = T(\frac n7) + T(\frac {10}{14}n+8) + \Theta(n)$$

![[Pasted image 20230302164118.png|center]]

Occorrono tante operazioni

[!error] Con i gruppi da 3 non funziona

Quicksort

Mostriamo come rendere [[6. Quicksort]] ottimo

quicksort(A,i,f):
	if i < f:
		//aiuto a scegliere il pivot attraverso la selection
		x = selection(A, i, f, (i+f)/2 )
		q = partition(A,i,x)
		quicksort(A,i,q)
		quicksort(A,q+1,f)

Strange Quicksort

strange_quicksort(A, i , f):
if i < f:
	x = selection(A, i, f, 1)
	q = partition(A, i, f, x)
	strange_quicksort(A, i, q-1)
	strange_quicksort(A, q+1, f)