Complexidade de Algoritmos
Edson Prestes
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Divisão e conquista
 Divide um problema em subproblemas independentes, resolve-os e
combina as soluções obtidas em uma solução para o problema original.
 Isso resulta em um processo recursivo de decomposições e recombinações.
Pode ser aplicado em problemas de:
 buscas em tabelas, como buscas seqüencial e binária;
 classificação, como classificação por seleção (selectionsort), por
 intercalação (mergesort) e por particionamento (quicksort);
 multiplicação (de matrizes e de números binários, por exemplo);
 seleção (para determinar máximo e mínimo, etc.).
 posicionamento de braço manipuladores;
 planejamento de caminhos em robótica móvel, etc
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Somatório dos elementos de uma lista.
Considere uma lista L de elementos do tipo inteiro.
 Se L tem no máximo 1 elemento, a soma de seus elementos é trivial.
 Caso contrário, este somatório pode ser visto como sendo a soma dos elementos da
primeira metade de L, chamada L1, com os elementos da segunda metade, chamada L2.
somatorio(L):= se curta( L ) // Tem comprimento de no máximo 1 ?
então retorna ( L ) // retona zero se L é vazia, ou o próprio elemento.
senão retorna (soma(somatorio(sublist1(L)), somatorio(sublist2(L)))).
Onde soma(r1, r2) = r1+ r2
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Classificação de listas por intercalação de sublistas.
O algoritmo recebe como entrada uma lista L e devolve esta lista classificada.
 Se L tem comprimento no máximo 1, então L já está classificada.
 Caso contrário, a lista L é dividida em duas listas aproximadamente do mesmo tamanho,
L1 e L2 correspondendo a primeira e a segunda metades de L, respectivamente.
 L1 e L2 são recursivamente classificadas e intercaladas a fim de obter uma versão
classificada da lista de entrada.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Divisão e conquista
 se a entrada é simples, a saida é obtida diretamente;
 caso contrário, a entrada é decomposta e aplicado o mesmo processo.
 os resultados parciais são combinados para gerar uma saída para a entrada original.
Baseado nisto, podemos descrever a divisão e conquista binária como
Onde
- as funções part1 e part2 decompõem a entrada;
- a função cmbn_2 combina as saídas;
- o procedimento smpl testa se a entrada é simples ou não; e
- a função drt dá a saída para entradas simples.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
O algoritmo Mergesort pode ser obtido especializando a
formulação recursiva da divisão e conquista binária
Mergesort( d ) := Div_Conq_2 ( d )
smpl( d ) := compr( d ) ≤ 1
{teste smpl} ;
drt ( d )
{operação drt} ;
:= d
part1( d ) := Prim(d)
{primeira parte} ;
part2( d ) := Fin(d)
{segunda parte} ;
cmbn_2( r1 , r2 ) := Intercl( r1 , r2 )
{combinação}
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
O algoritmo Somatório pode ser visto como uma especialização da formulação recursiva
da divisão e conquista
somatorio(L):= se simples( L )
então retorna ( L )
senão retorna (soma(somatorio(sublist1(L)), somatorio(sublist2(L)))).
Div_Conq_2 ( d ) :=Somatório( L)
smpl( d )
:= simples(L)
drt ( d )
:= retorna(L)
part1( d )
:= sublist1(L)
part2( d )
:= sublist2(L)
cmbn_2( r1 , r2 ) := soma( r1 , r2 )
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A recursão na divisão e conquista pode ser visualizada, em três estágios :
1. Construção da árvore de dados: é construída da raiz em direção à folhas (por
decomposições repetidas das instâncias de dados) até que as folhas sejam simples.
2. Aplicação da função drt para transferir as folhas dados para o estágio de resultados.
3. Construção da árvore de resultados: é construída das folhas em direção à raiz.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A execução do algoritmo Mergesort sobre a entrada d := [ 4, 3, 2, 1 ]
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A formulação binária pode ser generalizada para uma versão m-ária.
Um exemplo imediato de divisão e conquista ternária (m = 3) pode ser obtido,
modificando o algoritmo Quicksort.
Essa nova versão divide a entrada em três partes a partir do pivô:
 a primeira com os elementos menores do que o pivô,
 a segunda com os elementos iguais ao pivô, e
 a terceira com os elementos maiores do que o pivô.
A combinação é feita através do processo de concatenação.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Podemos ter o caso de divisão e conquista unária (m = 1).
…
Neste caso , o termo divisão é substituido por redução
Exemplos: algoritmos de busca
- Na busca seqüencial, a pesquisa é direcionada a uma tabela com um elemento a menos,
caso o elemento procurado ainda não tenha sido encontrado.
- Na busca binária, a pesquisa é direcionada a uma das metades da tabela, dependendo da
comparação com o elemento procurado.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Projeto de Algoritmos por Divisão e Conquista
Considere a versão binária
Podemos ajustar esta função para gerar diferentes algoritmos de classificação.
Considere que smpl e a função unária drt correspondam, respectivamente, a
Smpl(d) = compr(d)≤ 1
Drt (d):=d
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
As decomposições e recombinações podem ser definidas da seguinte maneira
Versão 1
Part1 e Part2 : a primeira e a segunda metades da entrada d e
Cmbn_2(r1, r2) : a intercalação de r1 e r2 .
Dá origem ao algoritmo Mergesort
Versão 2
Part1 pode conter o menor valor da entrada d e Part2 pode ser a entrada d restante.
Cmbn_2(r1, r2) pode ser a concatenação de r1 seguida de r2 .
Dá origem ao algoritmo de Seleção
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Quais são as árvores de execução para a entrada [4,3,2,1]?
Algoritmo Seleção
Algoritmo Mergesort
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Quais são as árvores de execução para a entrada [2,1,0,3,5,4]?
Algoritmo Mergesort
Algoritmo Seleção
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
O que podemos concluir ?
Quanto mais balanceado for o particionamento do(s) dado(s) de entrada menores serão
as árvores de execução!
De acordo com o princípio da Equipartição, o desempenho do algoritmo é dependente
do balanceamento do particionamento.
Ele tende a melhorar a medida que o particionamento se torna equilibrado.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Mínimo &
Máximo em
Tabelas
Smpl
Identifique as
funções:
Drt, Smpl, Part e Drt
Cmbn.
Part1 : Tab[p…ps]
Part2 : Tab[qi…q]
Cmbn
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Árvores de Execução para a Entrada
[1,4,5,2,3,5]
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Ocorrência em
Tabela
(ch, tab[p…q])
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
As árvores de execução para a Entrada [10,41,25,2,3,5]
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Mínimo de Tabela por Divisão e Conquista
Dada uma tabela Tab o algoritmo deve determinar o menor elemento armazenado.
Se a entrada é pequena (|Tab| ≤ 1), a resposta é trivial.
Caso contrário, o primeiro elemento de Tab é eliminado e calculado o menor valor
existente no restante da tabela (SubTab).
Após ter este valor ter sido determinado, ele é comparado com o elemento previamente
eliminado.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
As árvores de execução para a entrada
(10,41,25,2,3,5)
divisão e conquista unária liberal.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Análise da complexidade : Ocorrência em Tabela
(ch, tab[p…q])
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
O Algoritmo
 recebe como entrada um par ordenado: uma chave de pesquisa e uma tabela tab
 retorna como saída um valor verdadeiro ou falso
O tamanho da entrada corresponde a dimensão n da tabela tab.
A operação fundamental é a comparação (Tab[p]=ch) da chave com os elementos da
tabela Tab
Quantas chamadas recursivas são realizadas ?
Quantas vezes a entrada d teve que ser particionada até smpl ser verdadeiro ?
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
smpl
drt
part1
cmbn
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
As chamadas recursivas recebem como entrada um dado cujo tamanho varia da seguinte
maneira
O que H(d) representa ? Quanto vale H(d) ?
Ele corresponde a altura da árvore de execução, a qual é no máximo n-1.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Qual é o desempenho do algoritmo Oc_Seq sobre a entrada d
Se smpl(d) (tam(d)≤1), logo
Desemp[Oc_seq] (d) = aval[smpl](d) + desemp[drt](d)
smpl
drt
part1
Se ~ smpl(d) (tam(d)>1), temos
Desemp[Oc_seq] (d) = aval[smpl](d) +
desemp[part1](d) +
Desemp[Oc_seq] (part1(d)) +
cmbn
Desemp[cmbn](Oc_seq(part1(d)))
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Em relação ao número de comparações realizadas
Se smpl(d) (tam(d)≤1), temos
Desemp[Oc_seq] (d) = aval[smpl](d) + desemp[drt](d) = 0+1 = 1
Se ~ smpl(d) (tam(d)>1), temos
Desemp[Oc_seq] (d) = aval[smpl](d) +
desemp[part1](d) +
Desemp[Oc_seq] (part1(d)) +
Desemp[cmbn](Oc_seq(part1(d)))
Desemp[Oc_seq] (d) = 0 + 1 + Desemp[Oc_seq] (part1(d)) + 0
= 1 + Desemp[Oc_seq] (part1(d))
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Logo, o desempenho do algoritmo é descrito pela recorrência
Portanto,
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Análise da complexidade : Classificação de listas usando Mergesort
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
O Algoritmo
 recebe como entrada uma lista d de Elementos
 retorna como saída a lista d ordenada
O tamanho da entrada corresponde à quantidade de elementos n da lista d.
A operação fundamental corresponde a comparação entre os elementos da lista
Quantas chamadas recursivas são realizadas ?
Quantas vezes a entrada d foi particionada até smpl ser verdadeiro ?
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A cada nível a entrada tem tamanho máximo de acordo com a seguinte tabela
Onde
A quantidade de chamadas H(d) é dependente de S(d)
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
O desempenho do algoritmo MergeSort sobre a entrada d é
Se smpl(d) (tam(d)≤1), logo
Desemp[MergeSort] (d) = aval[tam(d)≤1] + desemp[r ← d] = 0 + 0=0
Se ~ smpl(d) (tam(d)>1), temos
Desemp[MergeSort](d)=aval[tam(d)≤1]+
Desemp[d1←Prim(d)] + Desemp[d1← Fin(d)]+
Desemp[MergeSort](Prim(d))+ Desemp[MergeSort](Fin(d)) +
Desemp[Intercl](MergeSort (Prim(d)), MergeSort (Fin(d))).
=0+0+0+ Desemp[MergeSort](Prim(d))+
Desemp[MergeSort](Fin(d)) +
tam(MergeSort (Prim(d)))+ tam(MergeSort (Fin(d)))-1.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Como a quantidade de elementos se mantém constante durante toda a execução temos que
|Prim(d)| + |Fin(d)| = tam(d), logo
Desemp[MergeSort](d)=Desemp[MergeSort](Prim(d))+
Desemp[MergeSort](Fin(d)) +
tam(d)-1.
Portanto, o desempenho do algoritmo em função do número de comparações é
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A cota superior (CS) do Algoritmo é
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Portanto