Análise de Algoritmos - Aula 08 (Guilherme)

Prévia do material em texto

Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Roteiro da Aula 8
1 Magia Negra: Counting e Radix Sort
2 k-e´simo e Mediana
k-e´simo usando partic¸a˜o
Tempo de pior caso
E quando a partic¸a˜o divide no meio?
3 Um resultado surpreendente!
Quicksort em tempo O(n logn)?
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Counting Sort
• Dado um vetor a = [v1, v2, . . . , vn], se sabemos que
1 ≤ vi ≤ K, todo 1 ≤ i ≤ n, podemos ordenar assim:
int c[K+1];
int a[n+1],b[n+1];
for( i = 1; i <= K; i++ ) c[i] = 0;
for( i = 1; i <= n; i++ ) c[a[i]]++;
for( i = 2; i <= K; i++ ) c[i] += c[i-1];
for( i = n; i >= 1; i--){
b[c[a[i]]] = a[i];
c[a[i]]--;
}
a = [3, 6, 4, 1, 3, 4, 1, 4]
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Ordenac¸a˜o em Tempo Linear
• Counting Sort ordena n elementos em tempo de pior caso
O(n + K);
• Se K for O(n), enta˜o Counting Sort roda em tempo linear!
Mas mostramos antes que Ω(n log n) e´ cota inferior
para ordenac¸a˜o. O que esta´ errado nessa histo´ria?
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Esta´vel e In-place
Ordenac¸a˜o In-place
Algoritmo na˜o utiliza memo´ria adicional (ou utiliza memo´ria
constante), para ordenar.
Exemplo: QuickSort, BubbleSort;
Ordenac¸a˜o Esta´vel
Algoritmo na˜o altera, para elementos com chaves iguais, a
ordem relativa na qual os elementos aparecem na entrada;
V = [31, 62, 43, 14, 35, 46, 17, 48]
Exemplo: CountingSort, BubbleSort, MergeSort;
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Radix Sort
329 720 720 329
457 355 329 355
657 436 436 436
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839
int a[n+1]; // elementos possuem d dı´gitos
...
for( i = 1; i <= d; i++){
sort( a, i ); // ordenac¸~ao esta´vel pelo i-e´simo dı´gito
}
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
k-e´simo e Mediana
Dado um vetor V = [5, 31, 2, 11, 9, 8, 4, 4, 7, 3, 13]
• Mediana: elemento que ocupa a posic¸a˜o ⌈n
2
⌉ quando o
vetor esta´ ordenado:
V = [2, 3, 4, 4, 5, 7, 8, 9, 11, 13, 31], mediana 7
• k-e´simo: elemento que ocupa a posic¸a˜o k quando o vetor
esta´ ordenado.
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
k-e´simo e Mediana
Dado um vetor V = [5, 31, 2, 11, 9, 8, 4, 4, 7, 3, 13]
• Mediana: elemento que ocupa a posic¸a˜o ⌈n
2
⌉ quando o
vetor esta´ ordenado:
V = [2, 3, 4, 4, 5, 7, 8, 9, 11, 13, 31], mediana 7
• k-e´simo: elemento que ocupa a posic¸a˜o k quando o vetor
esta´ ordenado.
Algoritmo: ordenar, usando mergeSort e
retornar V [⌈n
2
⌉] (ou V [k])
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
k-e´simo e Mediana
Dado um vetor V = [5, 31, 2, 11, 9, 8, 4, 4, 7, 3, 13]
• Mediana: elemento que ocupa a posic¸a˜o ⌈n
2
⌉ quando o
vetor esta´ ordenado:
V = [2, 3, 4, 4, 5, 7, 8, 9, 11, 13, 31], mediana 7
• k-e´simo: elemento que ocupa a posic¸a˜o k quando o vetor
esta´ ordenado.
Algoritmo: ordenar, usando mergeSort e
retornar V [⌈n
2
⌉] (ou V [k])
O(n logn)
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
k-e´simo usando partic¸a˜o
Relembrando o quickSort
int v[N];
...
quickSort( int *v, p, r ){
int q;
if ( p < r ) {
q = particiona( v, p, r );
quickSort( v, p, q );
quickSort( v, q+1, r );
}
}
• Custo de melhor caso: O(n logn)
• T (n) = 2 · T (n
2
) + n
• Custo de pior caso: O(n2)
• T (n) = T (n − 1) + n
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
k-e´simo usando partic¸a˜o
int v[N];
...
/* assume que k <= p-r+1 */
int kesimo( int *v, p, r, k ){
int q,ret;
if ( p == r ) return p;
else {
q = particiona( v, p, r );
if ( q-p+1 >= k ) ret = kesimo( v, p, q, k );
else ret = kesimo( v, q+1, r, k-(q-p+1) );
}
return ret;
}
...
mediana = v[kesimo( v, 1, n, n/2 )];
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
Tempo de pior caso
• kesimo( v, 1, n, k );
• No pior caso, a partic¸a˜o divide v em dois vetores de
tamanho 1 e n − 1;
• T (n) = T (n − 1)︸ ︷︷ ︸
pior caso da partic¸a˜o
+ n︸︷︷︸
custo da partic¸a˜o
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
Tempo de pior caso
• kesimo( v, 1, n, k );
• No pior caso, a partic¸a˜o divide v em dois vetores de
tamanho 1 e n − 1;
• T (n) = T (n − 1)︸ ︷︷ ︸
pior caso da partic¸a˜o
+ n︸︷︷︸
custo da partic¸a˜o
• O(n2)
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
E quando a partic¸a˜o divide no meio?
• kesimo( v, 1, n, k );
• Se a partic¸a˜o divide v em dois vetores de tamanhos iguais:
• T (n) = T (
n
2
)
︸ ︷︷ ︸
partic¸a˜o no meio
+ n︸︷︷︸
custo da partic¸a˜o
, T (1) = 1
T (n) = O(n)
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
k-e´simo usando partic¸a˜o
• O pior caso: T (n) = T (n − 1) + n = Θ(n2)
1 n
1 elemento menor que o pivot
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempo de pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
k-e´simo usando partic¸a˜o
• O pior caso: T (n) = T (n − 1) + n = Θ(n2)
1 n
1 elemento menor que o pivot
• O melhor caso: T (n) = T (n
2
) + n = Θ(n)
1 n
n
2
elementos menores que o pivot
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
k-e´simo usando
partic¸a˜o
Tempode pior
caso
E quando a
partic¸a˜o divide
no meio?
Um resultado
surpreendente!
k-e´simo usando partic¸a˜o
• O pior caso: T (n) = T (n − 1) + n = Θ(n2)
1 n
1 elemento menor que o pivot
• O melhor caso: T (n) = T (n
2
) + n = Θ(n)
1 n
n
2
elementos menores que o pivot
• Garantindo algo melhor que o pior: T (n) = T (n−8)+n =?
1 n
8 elementos menores que o pivot
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
Usaremos o mesmo algoritmo, pore´m
escolhendo o pivot de forma esperta!
/* assume que k <= p-r+1 */
int kesimoEsperto( int *v, p, r, k ){
int q,ret;
if ( p == r ) return p;
else {
q = particiona( v, p, r ); <--- vamos mudar aqui
if ( q-p+1 >= k ) ret = kesimoEsperto( v, p, q, k );
else ret = kesimoEsperto( v, q+1, r, k-(q-p+1) );
}
return ret;
}
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
p2p1 p3 p5p4 p6 p7
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
p2p1 p3 p5p4 p6 p7
p1 p2 p3 p4 p5 p6 p7
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
p2p1 p3 p5p4 p6 p7
p1 p2 p3 p4 p5 p6 p7
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
p2p1 p3 p5p4 p6 p7
p1 p2 p3 p4 p5 p6 p7
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
p2p1 p3 p5p4 p6 p7
p1 p2 p3 p4 p5 p6 p7
x
Mediana das medianas
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
p2p1 p3 p5p4 p6 p7
p5
Mediana das medianas
p2 p3p7 p4 p1p6
x
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
p2p1 p3 p5p4 p6 p7
p5p2 p3p7 p4 p1p6
x
Menores do que a mediana das medianas
A mediana das medianas x e´ o pivot
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
• Quantos elementos ha´ menores do que o pivot?
• Aproximadamente 3 elementos por bloco, para a metade
dos blocos:
• 3
(
1
2
· n
5
)
= 3n
10
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
• Quantos elementos ha´ menores do que o pivot?
• Aproximadamente 3 elementos por bloco, para a metade
dos blocos:
• 3
(
1
2
· n
5
)
= 3n
10
• Dessa forma, a partic¸a˜o sempre ira´ dividir v,
aproximadamente, em dois vetores de tamanhos: 3n
10
e 7n
10
;
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
• Quantos elementos ha´ menores do que o pivot?
• Aproximadamente 3 elementos por bloco, para a metade
dos blocos:
• 3
(
1
2
· n
5
)
= 3n
10
• Dessa forma, a partic¸a˜o sempre ira´ dividir v,
aproximadamente, em dois vetores de tamanhos: 3n
10
e 7n
10
;
• Enta˜o, a chamada recursiva ret = kesimoEsperto()
toma tempo de pior caso: T (7n
10
)
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Um resultado surpreendente!
/* assume que k <= p-r+1 */
int kesimoEsperto( int *v, p, r, k ){
int q,x,ret,vm[N];
if ( p == r ) return p;
else {
encontreAsMedianasComBubbleSort( v, n/5, vm );
q = x = kesimoEsperto( vm, 1, n/5, n/2 );
particiona( v, p, r, q ); /* pivot q */
if ( q-p+1 >= k ) ret = kesimoEsperto( v, p, q, k );
else ret = kesimoEsperto( v, q+1, r, k-(q-p+1) );
}
return ret;
}
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Ana´lise de Pior Caso
/* assume que k <= p-r+1 */
T(n) int kesimoEsperto( int *v, p, r, k ){
int q,x,ret,vm[N];
if ( p == r ) return p;
else {
O(n) encontreAsMedianasComBubbleSort( v, n/5, vm );
T(n/5) q = x = kesimoEsperto( vm, 1, n/5, n/2 );
O(n) particiona( v, p, r, q ); /* pivot q */
T(7n/10) if ( q-p+1 >= k ) ret = kesimoEsperto( v, p, q, k );
T(7n/10) else ret = kesimoEsperto( v, q+1, r, k-(q-p+1) );
}
return ret;
}
T (n) = T (n
5
) + T (7n
10
) + O(n)
T (n) ≤ T (n
5
) + T (7n
10
) + kn
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Mostrando por induc¸a˜o que T (n) = O(n)
• Por hipo´tese, para todo 1 ≤ i ≤ n − 1, vale T (i) ≤ ci;
Precisamos mostrar que sempre da´ para escolher
c tal que o passo da induc¸a˜o funcione!
T (n) ≤ c
n
5
+ c
7n
10
+ kn
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Mostrando por induc¸a˜o que T (n) = O(n)
• Por hipo´tese, para todo 1 ≤ i ≤ n − 1, vale T (i) ≤ ci;
Precisamos mostrar que sempre da´ para escolher
c tal que o passo da induc¸a˜o funcione!
T (n) ≤ c
n
5
+ c
7n
10
+ kn
≤ c
2n
10
+ c
7n
10
+ kn
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Mostrando por induc¸a˜o que T (n) = O(n)
• Por hipo´tese, para todo 1 ≤ i ≤ n − 1, vale T (i) ≤ ci;
Precisamos mostrar que sempre da´ para escolher
c tal que o passo da induc¸a˜o funcione!
T (n) ≤ c
n
5
+ c
7n
10
+ kn
≤ c
2n
10
+ c
7n
10
+ kn
≤ c
9n
10
+ kn
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Mostrando por induc¸a˜o que T (n) = O(n)
• Por hipo´tese, para todo 1 ≤ i ≤ n − 1, vale T (i) ≤ ci;
Precisamosmostrar que sempre da´ para escolher
c tal que o passo da induc¸a˜o funcione!
T (n) ≤ c
n
5
+ c
7n
10
+ kn
≤ c
2n
10
+ c
7n
10
+ kn
≤ c
9n
10
+ kn
Veja que funciona se c = 10k!
T (n) ≤ cn
Teoria da
Computac¸a˜o
113859
Aula 8
Roteiro
Magia Negra:
Counting e
Radix Sort
k-e´simo e
Mediana
Um resultado
surpreendente!
Quicksort em
tempo
O(n log n)?
Quicksort em tempo O(n log n)?
• Portanto, e´ poss´ıvel obter a mediana em tempo de pior
caso O(n);
• Com isso, veja que em teoria, o quickSort pode ser
modificado para tomar tempo de pior caso O(n logn)!
Como modificar o quickSort, para obter essa cota?
	Roteiro
	Magia Negra: Counting e Radix Sort
	k-ésimo e Mediana
	k-ésimo usando partição
	Tempo de pior caso
	E quando a partição divide no meio?
	Um resultado surpreendente!
	Quicksort em tempo O(nlogn)?