Análise de Algoritmos - Aula 07 (Guilherme)

Prévia do material em texto

Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Roteiro da Aula 7
1 Problemas, Algoritmos e Cotas
2 Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
3 Cotas Inferiores
Linear
Super-linear
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Problemas, Algoritmos e Cotas
Cota superior: O(s(n))
Cota inferior: Ω(ℓ(n))
Algoritmo A1
fA1 (n)
Algoritmo A2
fA2 (n)
Algoritmo A3
fA3 (n)
Problema P1
Cota superior: fA1 (n) = O(s1(n))
Cota inferior: fA1 (n) = Ω(ℓ1(n))
Cota superior: fA2 (n) = O(s2(n))
Cota inferior: fA2 (n) = Ω(ℓ2(n))
Cota superior: fA3 (n) = O(s3(n))
Cota inferior: fA3 (n) = Ω(ℓ3(n))
Em que tempo e´ poss´ıvel resolver?
Qual e´ o tempo m´ınimo poss´ıvel para resolver?
O que significa tudo isso?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Ordenac¸a˜o
• Entrada: um vetor v de n elementos;
• Sa´ıda: o vetor v ordenado: i < j ⇒ v[i] ≤ v[j].
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Ordenac¸a˜o
• Entrada: um vetor v de n elementos;
• Sa´ıda: o vetor v ordenado: i < j ⇒ v[i] ≤ v[j].
Da definic¸a˜o de um problema,
sempre extra´ımos um algoritmo forc¸a bruta!
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Forc¸a Bruta
int v[N];
...
forcaBrutaSort( int *v ){
int i,flag = 1;
while( flag ){
flag = 0;
proximaPermutacao( v );
for( i = 0; i < N-1; i++ )
if (v[i] > v[i+1]) flag = 1;
}
}
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Forc¸a Bruta
int v[N];
...
forcaBrutaSort( int *v ){
int i,flag = 1;
while( flag ){
flag = 0;
proximaPermutacao( v );
for( i = 0; i < N-1; i++ )
if (v[i] > v[i+1]) flag = 1;
}
}
fforcaBrutaSort(n) = Θ(n · n!)
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Bubble Sort
int v[N];
...
bubbleSort( int *v ){
int i,flag = 1;
while( flag ){
flag = 0;
for( i = 0; i < N-1; i++ )
if (v[i] > v[i+1]){
swap( &v[i], &v[i+1] );
flag = 1;
}
}
}
fbubbleSort(n) = n
2 − n
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Bubble Sort
int v[N];
...
bubbleSort( int *v ){
int i,flag = 1;
while( flag ){
flag = 0;
for( i = 0; i < N-1; i++ )
if (v[i] > v[i+1]){
swap( &v[i], &v[i+1] );
flag = 1;
}
}
}
fbubbleSort(n) = n
2 − n
fbubbleSort(n) = Θ(n
2)
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
O que temos ate´ agora?
bubbleSort
Cota inferior: fforcaBrutaSort(n) = Ω(n · n!)
Cota superior: fbubbleSort(n) = O(n
2)
Cota inferior: fbubbleSort(n) = Ω(n
2)
Cota superior: fforcaBrutaSort(n) = O(n · n!)
forcaBrutaSort
fbubbleSort(n)
Cota superior: O(n2)
Cota inferior: ?
Ordenac¸a˜o
Em que tempo e´ poss´ıvel resolver?
Qual e´ o tempo m´ınimo poss´ıvel para resolver?
fforcaBrutaSort(n)
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Quick Sort
V : 5 3 2 6 4 1 3 7
• Particionar o vetor V [1, n] em dois vetores: V [1, q] e
V [q + 1, n], tal que:
Qualquer elemento de V [1, q] e´ menor ou igual a qualquer
elemento de V [q + 1, n];
• A partic¸a˜o e´ feita em torno de um pivot (escolhemos o
valor de V [1]);
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Quick Sort
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 );
}
}
• Qual e´ o custo de quickSort( v, 1, n )?
• Quanto custa particiona( v, 1, n )?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Quick Sort
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 );
}
}
• Qual e´ o custo de quickSort( v, 1, n )?
• Quanto custa particiona( v, 1, n )?
T (n) = n + T (q) + T (n− q)
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Quick Sort
• Qual e´ o pior caso?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Quick Sort
• Qual e´ o pior caso?
• q = p, quer dizer, o pivot particiona V em dois vetores de
tamanho 1 e n− 1;
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Quick Sort
• Qual e´ o pior caso?
• q = p, quer dizer, o pivot particiona V em dois vetores de
tamanho 1 e n− 1;
• com isso, temos, T (n) = n + T (1) + T (n− 1), com
T (1) = 0;
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Quick Sort
• Qual e´ o pior caso?
• q = p, quer dizer, o pivot particiona V em dois vetores de
tamanho 1 e n− 1;
• com isso, temos, T (n) = n + T (1) + T (n− 1), com
T (1) = 0;
Mas sabemos que:
T (n) = T (n− 1) + n, T (1) = 0
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Quick Sort
• Qual e´ o pior caso?
• q = p, quer dizer, o pivot particiona V em dois vetores de
tamanho 1 e n− 1;
• com isso, temos, T (n) = n + T (1) + T (n− 1), com
T (1) = 0;
Mas sabemos que:
T (n) = T (n− 1) + n, T (1) = 0
fquickSort(n) = Θ(n
2)
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
O que temos ate´ agora?
Cota inferior: fforcaBrutaSort(n) = Ω(n · n!)
Cota superior: fforcaBrutaSort(n) = O(n · n!)
forcaBrutaSort
Cota superior: O(n2)
Cota inferior: ?
Ordenac¸a˜o
Em que tempo e´ poss´ıvel resolver?
Qual e´ o tempo m´ınimo poss´ıvel para resolver?
fforcaBrutaSort(n)
bubbleSort
Cota superior: fbubbleSort(n) = O(n
2)
Cota inferior: fbubbleSort(n) = Ω(n
2)
fbubbleSort(n)quickSort
Cota superior: fquickSort(n) = O(n
2)
Cota inferior: fquickSort(n) = Ω(n
2)
fquickSort(n)
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Merge Sort
V : 5 3 2 6 4 1 3 7
• Dividir o vetor V [1, n] em dois vetores de tamanho igual:
V [1, n
2
] e V [n
2
, n];
• Ordenar, recursivamente, os dois vetores de tamanho n
2
;
• Fazer o merge dos dois vetores;
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Merge Sort
int v[N];
...
mergeSort( int *v, p, r ){
if ( p < r ) {
q = floor((p+r)/2);
mergeSort( v, p, q );
mergeSort( v, q+1, r );
merge( v, p, q, r );
}
}
• Qual e´ o custo de mergeSort( v, 1, n )?
• Quanto custa merge( v, 1, n/2, n )?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
Merge Sort
int v[N];
...
mergeSort( int *v, p, r ){
if ( p < r ) {
q = floor((p+r)/2);
mergeSort( v, p, q );
mergeSort( v, q+1, r );
merge( v, p, q, r );
}
}
• Qual e´ o custo de mergeSort( v, 1, n )?
• Quanto custa merge( v, 1, n/2, n )?
T (n) = 2T (n
2
) + n, T (1) = 1
fmergeSort(n) = Θ(n log n)
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Forc¸a Bruta
Bubble Sort
Quick Sort
Merge Sort
Cotas
Inferiores
O que temos ate´ agora?
Cota inferior: fforcaBrutaSort(n) = Ω(n · n!)
Cota superior: fforcaBrutaSort(n) = O(n · n!)
forcaBrutaSort
Cota superior: O(n logn)
Cota inferior: ?
Ordenac¸a˜o
Qual e´ o tempo m´ınimo poss´ıvel para resolver?
fforcaBrutaSort(n)
bubbleSort
Cota superior: fbubbleSort(n) = O(n
2)
Cota inferior: fbubbleSort(n) = Ω(n
2)
fbubbleSort(n)
quickSort
Cota superior: fquickSort(n) = O(n
2)
Cota inferior: fquickSort(n) = Ω(n
2)
fquickSort(n)
mergeSort
Cota superior: fmergeSort(n) = O(n logn)
Cota inferior: fmergeSort(n) = Ω(n log n)
fmergeSort(n)
Em que tempo e´ poss´ıvel resolver?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cotas Inferiores
• Vamos simplificar admitindo apenas entradas de tamanho
par.
E´ poss´ıvel um algoritmo que ordene corretamente
um vetor v[n] usando menos do que
n
2
comparac¸o˜es?
• Suponha que exista o tal algoritmo: alg( int *v )
Mas a´ı temos uma contradic¸a˜o!
alg( int *v ) e´ necessariamente errado!
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cotas Inferiores
Portanto Ω(n) e´ uma cota inferior
para o problema da ordenac¸a˜o
pois mostramos que a func¸a˜o de custo de tempo de pior caso
de qualquer algoritmo para ordenar n nu´meros
sera´ Ω(n)
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
O que temos ate´ agora?
Cota inferior: fforcaBrutaSort(n) = Ω(n · n!)
Cota superior: fforcaBrutaSort(n) = O(n · n!)
forcaBrutaSort
Cota superior: O(n logn)
Cota inferior: Ω(n)
Ordenac¸a˜o
Qual e´ o tempo m´ınimo poss´ıvel para resolver?
fforcaBrutaSort(n)
bubbleSort
Cota superior: fbubbleSort(n) = O(n
2)
Cota inferior: fbubbleSort(n) = Ω(n
2)
fbubbleSort(n)
quickSort
Cota superior: fquickSort(n) = O(n
2)
Cota inferior: fquickSort(n) = Ω(n
2)
fquickSort(n)
mergeSort
Cota superior: fmergeSort(n) = O(n logn)
Cota inferior: fmergeSort(n) = Ω(n log n)
fmergeSort(n)
Em que tempo e´ poss´ıvel resolver?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cota Inferior para Ordenac¸a˜o
int v[N];
...
bubbleSort( int *v ){
int i,flag = 1;
while( flag ){
flag = 0;
for( i = 0; i < N-1; i++ )
if (v[i] > v[i+1]){
swap( &v[i], &v[i+1] );
flag = 1;
}
}
}
Vamos desenhar uma a´rvore para [5, 3, 9] e [1, 4, 7]
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cota Inferior para Ordenac¸a˜o
• Qualquer algoritmo que resolva o problema da ordenac¸a˜o
usando comparac¸o˜es pode ser representado como uma
a´rvore de decisa˜o bina´ria;
• Cada no´ da a´rvore corresponde a` uma comparac¸a˜o ≤.
Dependendo do resultado, o algoritmo vai seguir um de
dois caminhos, gerando assim a a´rvore;
• Note enta˜o que o pior caso em nu´mero de comparac¸o˜es
sera´ a altura da a´rvore, o tamanho do maior caminho
entre a raiz e uma folha.
Mas, a´ı, da´ para concluir algo interessante...
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
A´rvore de Execuc¸a˜o
4 3 9 8 134
3 841 9
≤
≤ ≤
≤ ≤
≤ ≤
≤ ≤
34
Qual e´ o nu´mero m´ınimo de folhas nessa a´rvore?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cota Inferior para Ordenac¸a˜o
• A a´rvore tem que ter pelo menos n! folhas, pois se estiver
faltando uma permutac¸a˜o sequer, podemos mostrar que o
algoritmo esta´ errado!
Como mostrar isso?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cota Inferior para Ordenac¸a˜o
• A a´rvore tem que ter pelo menos n! folhas, pois se estiver
faltando uma permutac¸a˜o sequer, podemos mostrar que o
algoritmo esta´ errado!
Como mostrar isso?
Se a permutac¸a˜o [v3, v1, v6, v5, v4, v2] na˜o estiver na a´rvore,
veja que a resposta para a entrada [5, 31, 2, 30, 11, 6]
sera´ necessariamente errada!
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cota Inferior para Ordenac¸a˜o
• Qual e´ a altura m´ınima para uma a´rvore com n! folhas?
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cota Inferior para Ordenac¸a˜o
• Qual e´ a altura m´ınima para uma a´rvore com n! folhas?
• ... e´ log n!
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Cota Inferior para Ordenac¸a˜o
• Qual e´ a altura m´ınima para uma a´rvore com n! folhas?
• ... e´ log n!
• mas isso ja´ vimos que e´ Θ(n log n)
Portanto, Ω(n log n) e´ cota inferior para ordenac¸a˜o
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Ordenac¸a˜o
Cota inferior: fforcaBrutaSort(n) = Ω(n · n!)
Cota superior: fforcaBrutaSort(n) = O(n · n!)
forcaBrutaSort
Cota superior: O(n logn)
Cota inferior: Ω(n log n)
fforcaBrutaSort(n)
bubbleSort
Cota superior: fbubbleSort(n) = O(n
2)
Cota inferior: fbubbleSort(n) = Ω(n
2)
fbubbleSort(n)
quickSort
Cota superior: fquickSort(n) = O(n
2)
Cota inferior: fquickSort(n) = Ω(n
2)
fquickSort(n)mergeSort
Cota superior: fmergeSort(n) = O(n logn)
Cota inferior: fmergeSort(n) = Ω(n logn)
fmergeSort(n)
Em que tempo e´ poss´ıvel resolver?
Tempo m´ınimo poss´ıvel para resolver?
Ordenac¸a˜o
Ana´lise de
Algoritmos
113859
Aula 7
Roteiro
Problemas,
Algoritmos e
Cotas
Ordenac¸a˜o
Cotas
Inferiores
Linear
Super-linear
Algoritmo O´timo
Algoritmo O´timo
Dados um problema P e um algoritmo A para P , dizemos que
A e´ o´timo, se fA = O(f(n)) e Ω(f(n)) e´ cota inferior para P ;
onde fA e´ a func¸a˜o de custo de tempo de pior caso de A.
Quer dizer, se A na˜o custa mais do que o custo m´ınimo.
	Roteiro
	Problemas, Algoritmos e Cotas
	Ordenação
	Força Bruta
	Bubble Sort
	Quick Sort
	Merge Sort
	Cotas Inferiores
	Linear
	Super-linear