Cap. 4 Divide e Conquista

Prévia do material em texto

DIVIDE E CONQUISTA
Capítulo IV
30-07-2015 04:14 1
Sumário
4.1 Introdução
4.2 Teorema de Mestre
4.3 Mergesort
4.4 Quicksort
4.5 Busca Binária
4.6 Árvore binária de travessia e suas propriedades
4.7 Multiplicação de inteiros grande e multiplicação matricial 
de Strassen
4.8 Problemas de Par de Pontos Próximos e Cobertura 
Convexa
30-07-2015 04:14 2
Introdução 
 Divide e conquista (D&C) é provavelmente a técnica 
geral de algoritmo mais conhecida. 
 Os algoritmos com estratégia divide e conquista 
seguem os seguintes passos:
1. A instância do problema é dividida em pequenas 
instâncias do problema (preferencialmente com o 
mesmo tamanho)
2. As instâncias pequenas do problemas são 
resolvidas(tipicamente recursivamente, alem de que, 
muitas vezes um algoritmo diferentes é empregado 
quando as instancias tornam-se muito pequenas)
3. Se necessário, as soluções obtidas para instancias 
pequenas do problema são combinadas para se obter 
solução original.
30-07-2015 04:14 3
Divide e Conquista (D&C)
Problema de tamanho n
Subproblema 1de tamanho n/2 Subproblema 2de tamanho n/2
Solução do subproblema 1 Solução do subproblema 2
Solução do problema original
30-07-2015 04:14 4
Quando usar Divide e Conquista?
 Geralmente, não devemos nos limitar na divisão do 
problema em 2 partes. 
◦ Podemos obter quanto tantos subproblemas que 
quisermos por cada problema. 
◦ Generalmente, dividimos por dois. 
 D&C é ideal para problemas em que cada subproblema 
possa ser resolvido simultâneamente pelo seu processador. 
◦ i.e. – computação paralela
30-07-2015 04:14 5
Exemplos de Divide e Conquista
 Ordenação: mergesort e quicksort
 Árvore binária de travessia
 Pesquisa binária (?)
 Multiplicação de grandes inteiros
 Multiplicação de Matrizes: o algoritmo de Strassen
 Algoritmos de par de pontos mais próximos e 
cobertura convexa
30-07-2015 04:14 6
A Relação Geral de Divide e Conquista
 Um problema de tamanho n pode ser dividido em várias 
instâncias de tamanho n/b, com a deles precisando ser 
resolvido. (Aqui, a e b são constantes; a≥1 e b>1). Assumindo 
que o tamanho n é uma potência de b, para simplificar 
nossa análise, temos a recorrência a seguir para o tempo 
de execução T(n):
T(n)=aT(n/b) + f(n) (4.1) 
Onde f(n) é a função que conta o número de vezes que é 
efectuada a divisão do problema em pequenos problemas e 
a combinação das suas soluções.
30-07-2015 04:14 7
Relação Geral de D&C
4.2 Teorema de Mestre
 Obviamente, a ordem de crescimento de sua solução T(n) 
depende dos valores das constantes a e b e a ordem de 
crescimento da função f(n).
 A análise de eficiência dos algoritmos de tipo divide e conquista 
é simplificada pelo seguinte algoritmo:
Teorema:
Se f(n)(nd) onde d ≥0 na equação de recorrência 
T(n)=aT(n/b) + f(n) , então
Este resultado também é valido para as notações de O e .
d
d
d
a
d
d
ba
ba
ba
Se
Se
Se
n
nn
n
nT
b 











)(
)log(
)(
)(
log
30-07-2015 04:14 8
Exemplo
 Consideremos o problema de cálculo da soma de números
a0, …, an–1. Se n>1, podemos dividir o problema em duas
instâncias do mesmo problema:
◦ Calcular a soma dos primeiros n/2 e do restantes n/2
números.
◦ Se n = 1, retornamos simplesmente a0
◦ Depois do calculo de cada soma podemos adiciona-los
para se obter a soma total:
a0+ a1+…+an–1 = (a0+ … +an/2–1 ) + (a n/2+ … +an–1 )
30-07-2015 04:14 9
Exemplo
 Como por exemplo, tendo enconta a relação 
geral de divide e conquista, a recorrência 
para o número de adições A(n) pelo 
algoritmo divide e conquista do cálculo da 
soma com tamanho de entrada n=2k é
A(n)=2A(n/2)+1
Assim, a=2, b=2 e d=0 então a>bd,
A(n)(nlogb
a) = (nlog2
2)=(n).
30-07-2015 04:14 10
4.3 Mergesort (ordenação intercalação)
 Mergesort é um exemplo perfeito de aplicação com sucesso da 
estratégia divide-e-conquista. Este ordena um dado vector 
A[0.. n–1] da seguinte maneira:
1. divide o mesmo em duas partes A[0..n/2 –1] e A[n/2 .. n–1] 
2. Ordenada cada uma delas recursivamente
3. Una os dois pequenos vectores ordenados num único.
Algoritmo Mergesort(A[0..n–1])
…
se n > 1 então
copia A[0 .. n/2–1] para B[0..n/2 –1] 
copia A[ n/2 .. n–1] para C[0 .. n/2 –1] 
Mergesort(B[0 .. n/2–1] )
Mergesort(C[0 .. n/2–1] )
Merge(B, C, A)
30-07-2015 04:14 11
Algoritmo Merge(B[0..p–1], C[0..q–1], A[0..p+q–1])
…
i0, j0, k0;
enquanto i<p E j<q faça
se B[i] <= C[j] então
A[k] B[i]
i i+1
senão
A[k] C[j];
j j+1;
fimse
k k+1
se i=p então
copia C[j..q–1] para A[k..p+q–1]
senão
copia B[i..p–1] para A[k..p+q–1]
fimse
fimenquanto
…
30-07-2015 04:14 12
8 3 2 9 7 1 5 4
7 1 5 48 3 2 9
2 98 3
8 3
3 8
2 9
2 9
2 3 8 9
5 47 1
7 1
1 7
5 4
4 5
1 4 5 7
1 2 3 4 5 7 8 9
30-07-2015 04:14 13
Eficiência para Mergesort
 Assumindo que n é uma potência 2, a relação de recorrência para o 
número de comparações C(n) é
C(n)=2C(n/2)+Cmerge(n) para n>1, 
C(1)=0.
 Vamos analisar Cmerge(n), o número de comparações feitas durante a 
etapa da intercalação. Em cada etapa, exactamente uma comparação é 
feita, após o qual o número total de elementos de duas matrizes ainda 
precisando de ser processado é reduzido a um. No pior dos casos, 
nenhum dos dois vectores torna-se vazia antes do outro conter apenas 
um elemento (exemplo, pequenos elementos podem ser provenientes 
de vectores alternadas). Assim, para o pior caso, Cmerge(n)=n–1 e a 
recorrência fica:
Cpior(n) = 2Cpior(n/2) + n – 1 para n>1, Cpior(1) = 0
Usando o teorema anterior temos:
Cpior(n) = nlog2n – n +1
30-07-2015 04:14 14
4.4 Quicksort (Ordenação rápida)
 O Quicksort, tal como o Mergesort, se baseia no 
princípio da divisão e conquista mas por possuir uma 
abordagem diferente não necessita de espaço de 
memória adicional, o que pode vir a justificar o motivo 
de ser mais utilizado que o Mergesort.
Sua desvantagem ocorre quando a divisão do vector 
(que é baseada em comparação) fica muito 
desbalanceada (Isto ocorre quando: o vector está quase 
ordenado/desordenado ou estar completamente 
ordenado/desordenado).
Mesmo com essa desvantagem é provado que em média 
seu tempo tende a ser muito rápido [Cormen, 2002], 
por isso o nome, Ordenação-Rápida (ou Quick-Sort em 
inglês).
30-07-2015 04:14 15
Quicksort
 Ao contrário do mergesort, que divide seus elementos de 
entrada, de acordo com sua posição no vector, quicksort os 
divide de acordo com seu valor. Especificamente, ele reorganiza 
elementos de um dado vector A[0..n–1] para encontrar a sua 
partição, uma situação onde todos os elementos antes de 
alguma posição s são menores ou iguais a A[s] e todos os 
elementos após a posição s são maiores ou iguais a A[s]
A[0] … A[s–1] A[s] A[s+1] …A[n–1]
todos são  A[s] todos são ≥ A[s]
 Obviamente, depois de uma partição tenha sido feita, A[s] estará 
em sua posição final no vector ordenado, e podemos continuar 
ordenar os dois subvectores dos elementos anteriores e 
posteriores de A[s] de forma independente.
30-07-2015 04:14 16
Quicksort - Algoritmo
Algoritmo quicksort(A[l .. r])
//ordena subvector usando quicksort
//Entrada: A subvector A[l .. r] de A[0 .. n–1],
//definida pelos seus índices a esquerda l e a direita r
//Saida: O subvector A[l .. r] ordenada em ordem crescente
se l < r então
s  particao(A[l .. r])
quicksort(A[l .. s–1])
quicksort(A[s+1.. r])
…
30-07-2015 04:14 17
Quicksort (Funcionamento)
 A partição de A[0.. n–1] e, mais genericamente, dos seus subvectores 
A[l .. r] (0  l < r  n–1) pode ser obtida pelo algoritmo a seguir:
◦ Primeiro, seleccione um elemento cujo valor a partir da qual será 
divido os subvectores. Por causa de seu papel orientador, 
chamamos esse elemento pivô. Existem diversas estratégias para 
seleccionar um pivô. Por agora, nós usamos a estratégia mais 
simples i.e., seleccionamos o primeiro elemento da subvector 
p=A[l].
◦ Usamos um método eficiente, baseado em duas varreduras do 
subvector: 
 um é da esquerda para a direita e outro de direita para a 
esquerda, cada um comparando os elementos do subvector com 
o pivô. 
30-07-2015 04:14 18
Funcionamento(cont.)
o A varredura da esquerda para a direita inicia-se com o
segundo elemento. Como queremos que os elementos
menores que o pivô para a primeira parte do subvector,
esta verificação salta todos os elementos que são menores
que o pivô e pára ao se deparar com o primeiro elemento
maior ou igual ao pivô.
o A varredura da direita para a esquerda começa com o
último elemento do subvector. Como os elementos maiores
que o pivô devem estar na segunda parte do subvector,
esta verificação salta todos elementos que são maiores que
o pivô e pára ao se deparar com o primeiro elemento
menor ou igual ao pivô.
30-07-2015 04:14 19
Quicksort
 Três situações podem ocorrer, dependendo da existência ou não do cruzamento 
dos índices de varredura:
◦ Se índices de varredura i e j não se cruzarem, ou seja, i<j, simplesmente troca-se A[i] e A[j] 
e retoma-se as varreduras, incrementando i e decrementando j, respectivamente. 
◦ Se os índices de varredura se cruzarem, ou seja, i>j, o subvector é particionado depois da 
troca do pivô com A[j]. 
◦ Finalmente, se os índices de varredura pararem apontando para o mesmo elemento, ou seja, 
i=j, o valor apontado deve ser igual a p. Assim, temos o subvector particionada: Podemos 
considerar o último caso com o caso de cruzamento de índices (i>j) trocando o pivô com o 
A[j] para qualquer i>j.
◦ .
i j
p todos são  p ≥ p …  p todos são ≥ p
j i
p todos são  p  p ≥ p todos são ≥ p
i=j
p todos são  p = p todos são ≥ p
30-07-2015 04:14 20
Algoritmo de partição
Algoritmo particao(A[e..d])
//partição de subvector usando o primeiro elemento como pivô
//Entrada: O subvector A[e..d] de A[0..n–1], definida pela esquerda e 
// direita pelos seus índices e e d ( e<d) respectivamente.
//Saida: A partição de A[e..d]
pA[e]
ie;
jd+1
repet
repet ii+1 ate que A[i]≥p
repet jj–1 ate que A[j]p
troca(A[i], A[j])
ate que i ≥ j
troca(A[i], A[j]) //desfaz a última troca se i ≥ j
troca(A[l], A[j])
retorna j
30-07-2015 04:14 21
Exemplo
i j
5 3 1 9 8 2 4 7
i j
5 3 1 9 8 2 4 7
i j
5 3 1 4 8 2 9 7
i j
5 3 1 4 8 2 9 7
i j
5 3 1 4 2 8 9 7
j i
5 3 1 4 2 8 9 7
2 3 1 4 5 8 9 7
Ordena a lista 5,3,1,9,8,2,4,7 em ordem crescente
i j
2 3 1 4 5 8 9 7
i j i j
2 3 1 4 8 9 7
i j i j
2 1 3 4 8 7 9
j i j i
2 1 3 4 8 7 9
1 2 3 4 7 8 9
ij
1 3 4 7 9
j i
3 4
4
1 2 3 4 5 7 8 9
30-07-2015 04:14 22
Complexidade
 Pode-se notar que o número de comparações feitas 
antes da realização da partição é n+1 se a varredura 
de índices se cruzam e n se eles coincidem. Se a 
separação acontecer no meio do subvector teremos 
o melhor caso. O número de comparações no 
melhor caso, Cml ira satisfazer a recorrência
Cml(n)=2Cml(n/2)+n para n>1,
Cml(1)=0
 Segundo o teorema de Mestre, Cml(n)Θ(nlog2n)
 Resumo
◦ Melhor Caso: Θ(n log2 n);
◦ Caso Médio: Tende a ser Θ(n log2 n); (TPC)
◦ Pior Caso: Θ(n²). (TPC)
30-07-2015 04:14 23
4.5 Busca binária
 A busca binária é um eficiente algoritmo para pesquisa numa lista ordenada.
 Funcionamento
◦ Compara a chave da busca k com elemento médio da lista A[m]. Se eles 
coincidem o algoritmo pára, senão, a mesma operação é repetida 
recursivamente para primeira metade da lista se k<A[m] e segunda metade 
se k>A[m];
k
A[0]…A[m-1] A[m] A[m+1]…A[n–1]
pesquisa-se neste 
lado de k<A[m]
pesquisa-se neste 
lado de k>A[m]
30-07-2015 04:14 24
Exemplo
 Aplique a busca binária para pesquisar k=70 na lista 
3,14,27,31,39,42,55,70,74,81,85,93,98
 Solução:
índice 0 1 2 3 4 5 6 7 8 9 10 11 12
Valores 3 14 27 31 39 42 55 70 74 81 85 93 98
Iteração 1 e m d
Iteração 2 e m d
Iteração 3 e,m d
30-07-2015 04:14 25
Algoritmo
Algoritmo BuscaBinaria(A[0..n–1], k )
//implementação não recursiva de busca binária
//Entrada: O vector A[0..n–1],em ordem crescente e a chave de 
busca k
//Saída: retorna o índice do elemento no vector igual a k ou -1 caso 
contrário
e0
dn –1
enquanto e d faca
m (e+d)/2
se k=A[m] então
retorna m
senão se k <A[m] então
dm–1
senão
em+1
retorna -1
30-07-2015 04:14 26
Eficiencia
 A forma padrão de análise de eficiencia do algoritmo de busca 
binária é a contagem de número de vezes que a chave de busca 
é comparada com os elementos na lista. Portanto, para 
simplificar este processo, utilizemos a comparação em 3 
sentidos (<, > ou =). Isto quer dizer que depois da comparação 
de k com A[m], o algoritmo pode dizer se k é menor, ou igual, 
ou maior que A[m]
 Quantos comparações são executadas no algoritmo? A resposta 
não depende somente de n mas tambem na especificação 
particular da instância do problema.
 Seja C(n) o número de comparação executadas no algoritmo no 
pior caso. As entradas para pior caso inclui todo vector que não 
contem a chave(obviamente, alguns casos a busca com 
sucesso). Como depois da comparação o algoritmo faz o mesmo 
para outra metade, obtemos a seguinte relação de recorrencia:
C(n) = C(n/2) +1 para n>1, C(1) = 1
30-07-2015 04:14 27
4.6 Árvore binária. Travessias e suas 
Propriedades
 Uma árvore binária AB é definido como um conjunto finito 
de nós que pode ser vazia ou consiste de uma raiz e duas 
árvores binária disjuntas SAE e SAD chamados, 
respectivamente, a subárvore a esquerda e a direita da 
raíz.
 A altura é definido como o comprimento do caminho mais 
longo a partir da raiz para uma folha.
 A altura da árvore vazia é -1
SAE SAD
30-07-2015 04:14 28
Exemplos
30-07-2015 04:14 29
a) Árvore Binária
b) A extensão de árvore binária. Nós internos são 
apresentados através de circulos enquanto que os 
externos são apresentados através de quadrados.
Algoritmo
Uma vez que a própria definição divide a árvore binária em duas 
estruturas menores do mesmo tipo, a subárvore esquerda e a subárvore 
direita, muitos problemas sobre árvores binárias podem ser resolvido 
aplicando a técnica de divide e conquista. Como um exemplo, vamos 
considerar um algoritmo recursivo para calcular a altura de uma árvore 
binária.
ALGORITIMO altura(ab )
//Calcula recursivamente a altura de uma arvore binária
//Entrada: A árvore binária ab
//Saida: A altura da árvore binária ab
Se ab = ∅
retorna −1
Senão 
retorna max{altura(sae), altura(sad)} + 1
30-07-2015 04:14 30
Eficiência
 Medimos o tamanho da instância do problema, o 
número de nós em uma determinada árvore 
binária.
 Obviamente, o número de comparações feitas 
para calcular o valor mínimo de dois números e o 
número de adições feitas pelo algoritmo são o 
mesmo. temos a seguinte relação de recorrência 
para A(n(T)).
A(n(T)) = A(n(TL))+A(n(TR))+1 para n(T)>0
A(0)=0.
 m
30-07-2015 04:14 31
Travessias
 Os mais importante algoritmos de divide-e-conquista para 
árvores binárias são as três travessias clássicas: preordem, 
inordem e pós-ordem. Todas as três travessias visitam os 
nós de uma árvore binária de forma recursiva, ou seja,visitando raiz da árvore e de suas sub-árvores esquerda e 
direita. Eles diferem apenas pelo tempo da visita da raíz:
 Na pré-ordem, a raiz é visitada antes das subárvores 
esquerda e direita (nessa ordem). (r s d)
 No inordem, a raiz é visitada depois de visitar sua 
subárvore esquerda, mas antes de visitar a subárvore 
direita. (s r d)
 No pós-ordem, a raiz é visitada depois de visitar as 
subárvores esquerda e direita (nessa ordem). (s d r)
30-07-2015 04:14 32
Travessias
a
b
g
d e
c
f
Pré-Ordem (< r s d >) a, b, d, g, e, c, f
In-ordem (< s r d >) d, g, b, e, a, f, c
Pos-Ordem (< s d r >) g, d, e, b, f, c, a
30-07-2015 04:14 33
Multiplicação de inteiros grande
 Considere o problema de multiplicão de dois (grande) n-dígitos 
inteiros representados por um vector de dígitos como:
A = 12345678901357986429 
B = 87654321284820912836
 Algoritmo da escola primária:
a1 a2 … an
b1 b2 … bn
(d10) d11d12 … d1n
(d20) d21d22 … d2n
… … … … … … …
(dn0) dn1dn2 … dnn
 Eficiência: n2 multiplicação de cada dígito
30-07-2015 04:14 34
Usando o algoritmo de D&C 
 Um pequeno exemplo:
A ∗ B onde A = 2135 e B = 4014
A = [21(102 )+ 35], B = [40(102 )+ 14]
Então, A ∗ B = [21(102 )+ 35]∗ [40 (102 )+ 14]
= (21 ∗ 40 )104 + [(21 ∗ 14) + (35 ∗ 40)]102 + 35 ∗ 14
 Em geral, se A = A1A2 e B = B1B2 (onde A e B são n-digitos,
A1, A2, B1,B2 são n/2-dígitos numéricos),
A ∗ B = (A1 ∗ B1)10
n + (A1 ∗ B2 + A2 ∗ B1) 10
n/2 + A2 ∗ B2
 A Recorrência para o número de multiplicações de n-dígitos M(n):
◦ M(n) = 4M(n/2), M(1) = 1
◦ Solução: M(n) = n2
30-07-2015 04:14 35
A ∗ B =(A1 ∗ B1)10
n + (A1 ∗ B2 + A2 ∗ B1) 10
n/2 + A2 ∗ B2
Objectivo é reduzir o nº de multiplicações de 4 para 3:
(A1 + A2 ) ∗ (B1 + B2 ) = A1 ∗ B1 + (A1 ∗ B2 + A2 ∗ B1) + A2 ∗ B2,
I.e., (A1 ∗ B2 + A2 ∗ B1) = (A1 + A2 ) ∗ (B1 + B2 ) - A1 ∗ B1 - A2 ∗ B2,
O que requer somente 3 multiplicações a custo de 4-1 
adição/subtracção. 
A Recorrência para o número de multiplicações M(n):
M(n) = 3M(n/2), M(1) = 1
Solução : M(n) = 3log 2n = nlog 23 ≈ 1.585n
Usando o algoritmo de Divide-e-Conquista 
30-07-2015 04:14 36
Multiplicação matricial de Strassen’s
 Strassen observou [1969] que o producto de duas matrizes
pode ser calculada como seguinte:
30-07-2015 04:14 37


















1110
0100
1110
0100
1110
0100
BB
BB
AA
AA
CC
CC









423142
537541
MMMMMM
MMMMMM
)(*)( 110011001 BBAAM 
0011102 *)( BAAM 
)(* 1101003 BBAM 
)(* 0010114 BBAM 
1101005 *)( BAAM 
)(*)( 010000106 BBAAM 
)(*)( 111011017 BBAAM 
Onde:
Analise de algoritmo de Strassen
 Se n não é uma potência de 2, matrizes podem ser 
preenchidos com zeros.
 Numero de multiplicações:
M(n) = 7M(n/2), M(1) = 1
 Solução: 
M(n) = 7log2n = nlog2 7 ≈ n2.807 vs. n3 de força bruta
 Algoritmos com melhor eficiência assintoticas são 
conhecidas mas são bastantes complexas.
30-07-2015 04:14 38
Par de pontos mais proximos
Algoritmo:
Sejam P1(x1,y1),…, Pn(xn,yn) o conjunto de n pontos no plano, onde n é uma potência de 
2. Assumimos que os pontos estão em ordem ascendente em relação as 
coordenadas de x.
1. Divida os pontos dados em dois subconjuntos S1 e S2 por uma linha vertical x=c
de modo que a metade dos pontos ficam à esquerda ou na linha e a outra 
metade ficam para a direita ou sobre a linha.
2. Encontre recursivamente os pares mais próximos para os subconjuntos 
esquerdo e direito.
3. Pondo d = min {d1, d2}
Podemos limitar a nossa atenção para os pontos na faixa vertical simétrica 
de largura 2d possível par mais próximo. Seja C1 e C2 subconjuntos de pontos 
no subconjunto a esquerda S1 e do subconjunto a direita S2, 
respectivamente, que se encontram nesta faixa vertical. Os pontos em C1 e 
C2 são armazenados em ordem crescente de suas coordenadas y, que é 
mantido por meio da fusão durante a execução do passo seguinte.
30-07-2015 04:14 39
Problemas de par de pontos mais próximos
4. Para cada ponto P(x, y) em C1, inspecionamos pontos em C2 que podem 
estar mais perto de P que d. Não pode haver mais de 6 pontos (porque 
d ≤ d2)!
30-07-2015 04:14 40
d2
d1
dd
x = c 
S1
S2
Par de pontos mais próximos
O pior cenário é descrito abaixo:
Os seis pontos que talvez precisem ser examinado para o ponto P.
30-07-2015 04:14 41
d
d
d
p
Eficiencia de algoritmo de par de pontos mais
próximos
Tempo de execução do algoritmo é descrito por
T(n) = 2T(n/2) + M(n), onde M(n) ∈ O(n)
Pelo teorema de Mestre (com a = 2, b = 2, d = 1)
T(n) ∈ O(n log n)
30-07-2015 04:14 42
Problema de Cobertura Convexa
 Há, de facto, vários algoritmos de divide e 
conquista para o problema de cobertura convexa: 
“encontrar o menor polígono convexo que contém n pontos dados no 
plano.”
 Um dos algoritmos simples, embora não o mais 
eficiente entre outros existentes, é o quickhull. 
Esse nome deste algoritmo deve se ao facto que as 
suas operações se assemelham as da quicksort.
30-07-2015 04:14 43
Algoritmo Quickhull
 Seja P1=(x1, y1), P2=(x2, y2), …, Pn=(xn, yn) um conjunto 
S de n pontos no plano. Assumimos que os pontos estão 
em ordem crescentes segundos as coordenadas de X 
em relação as coordenadas Y. É fácil provar 
geométricamente que o ponto mais esquerda P1 e o 
ponto mais a direita Pn pertecem a cobertura convexa.
30-07-2015 04:14 44
P1
Pn
Onde P1Pn a linha recta que liga os pontos P1 e Pn Esta linha 
separa os pontos em dois subconjuntos S1 e S2.
S2
S1
Algoritmo Quickhull
 Convexa: menor conjunto convexo que inclui os pontos dados.
 Assumem que os pontos são ordenados em relação aos valores das 
coordenadas x.
 Identificar os pontos extremos P1 e P2
 Calcule cobertura superior de forma recursiva:
◦ encontrar o ponto Pmax que está mais distante da linha P1P2
◦ calcular a cobertura superior dos pontos para a esquerda da linha P1Pmax
◦ calcular a cobertura superior dos pontos para a esquerda da linha PmaxP2
30-07-2015 04:14 45
P1
Pn
Pmax
 Calcule cobertura inferior de uma maneira semelhante
Eficiencia de algoritmo Quickhull
 Encontrar ponto mais distante da linha P1P2
pode ser feito em tempo linear
 Eficiência de Tempo:
◦ pior caso: Θ(n2) (como quicksort)
◦ caso médio: Θ(n) (sob hipóteses razoáveis sobre 
a distribuição de pontos de dados)
 Se os pontos não são inicialmente 
ordenadas por valor de coordenada x, isso 
pode ser feito em tempo O(nlog n)
 Vários O(nlog n) algoritmos para convexa são 
conhecidos
30-07-2015 04:14 46