Analise de Algoritmos
Problemas, instâncias,algoritmos e tempo
–p. 1/32
Análise de Algoritmos
A Análise de Algoritmos estuda problemascomputacionais recorrentes, ou seja, problemasque aparecem, sob diversos disfarces, em umagrande variedade de aplicações e contextos.
– p. 2/32
Análise de Algoritmos
A Análise de Algoritmos estuda problemascomputacionais recorrentes, ou seja, problemasque aparecem, sob diversos disfarces, em umagrande variedade de aplicações e contextos.
A análise de um algoritmo para um dado problematrata de
provar que o algoritmo está correto, e
estimar o tempo de execução do algoritmo.
– p. 2/32
Análise de Algoritmos
Dados dois algoritmos para um mesmo problema,a análise permite decidir qual dos dois é maiseficiente.
– p. 3/32
Análise de Algoritmos
Dados dois algoritmos para um mesmo problema,a análise permite decidir qual dos dois é maiseficiente.
A estimativa do espaço de memória usado peloalgoritmo também é importante em muitos casos.
– p. 3/32
Análise de Algoritmos
Pode-se dizer que a Análise de Algoritmos é umadisciplina de engenharia, pois ela procura prever ocomportamento de um algoritmo antes que eleseja efetivamente implementado e colocado “emprodução”.
– p. 4/32
Análise de Algoritmos
Num nível mais abstrato, a análise de algoritmosprocura identificar aspectos estruturais comunsaos algoritmos e estudar paradigmas de projeto dealgoritmos (como divisão e conquista,programação dinâmica, etc.)
– p. 5/32
Análise de Algoritmos
No restante desta introdução, faremos uma rápidarevisão de conceitos básicos e fixaremos anotação e a terminologia empregadas no texto.
– p. 6/32
Analise de Algoritmos
Problemas e suas instâncias
–p. 7/32
Instâncias
Todo problema computacional é uma coleção de“casos particulares” que chamaremos instancias. Apalavra instância é empregada aqui no sentido deexemplo, exemplar, espécime, amostra, ilustração.
– p. 8/32
Instâncias - Exemplos
Problema da multiplicacao de numeros naturais:dados números naturais x e y, determinar oproduto x.y.
– p. 9/32
Instâncias - Exemplos
Problema da multiplicacao de numeros naturais:dados números naturais x e y, determinar oproduto x.y.Cada instância do problema é definida pordois números naturais. Por exemplo, osnúmeros 2 e 3 definem uma instância.
– p. 9/32
Instâncias
Problema da ordenacao: rearranjar (ou seja,permutar) os elementos de um vetor A[1 . . . n]de números naturais de modo que ele se tornecrescente.
– p. 10/32
Instâncias
Problema da ordenacao: rearranjar (ou seja,permutar) os elementos de um vetor A[1 . . . n]de números naturais de modo que ele se tornecrescente.Cada instância do problema é definida porum número natural n e um vetor A[1 . . . n].Por exemplo, o número 5 e o vetor(876, 145, 323, 112, 221) definem umainstância do problema.
– p. 10/32
Instâncias
Problema do circuito hamiltoniano: encontrar umcircuito hamiltoniano em um grafo.
– p. 11/32
Instâncias
Problema do circuito hamiltoniano: encontrar umcircuito hamiltoniano em um grafo.Cada instância do problema é definida porum grafo.
– p. 11/32
Tamanho de uma instância
O tamanho de uma instância de um problema é aquantidade de dados necessária para descrever ainstância, ou seja, é o “espaço” necessário paraespecificar a instância. Em geral, o tamanho deuma instância é descrito por um único númeronatural, mas às vezes é mais conveniente usar umpar, um terno, etc., de números naturais.
– p. 12/32
Tamanho de uma instância
No problema da multiplicação de dois númerosnaturais, toda instância tem tamanho 2 (poisconsiste em dois números). Dependendo dascircunstâncias, entretanto, pode ser maisapropriado dizer que o tamanho de umainstância do problema é o número decaracteres (ou de dígitos) necessário paraespecificar os dois números.
– p. 13/32
Tamanho de uma instância
O tamanho de uma instância do problema deordenação é n. (Mas poderia também serdefinido como o número total de caracteresnecessário para escrever os valores doselementos de A[1 . . . n].)
– p. 14/32
Tamanho de uma instância
O tamanho de uma instância do problema deordenação é n. (Mas poderia também serdefinido como o número total de caracteresnecessário para escrever os valores doselementos de A[1 . . . n].)
O tamanho de uma instância do problema docircuito hamiltoniano em um grafo com n
vértices e m arestas é um par (m,n).
– p. 14/32
Algoritmos para problemas
Dizemos que um algoritmo resolve um problema se,ao receber qualquer instância do problema,devolve uma solução da instância ou informa que ainstância não tem solução.
– p. 15/32
Tempo gasto
O tempo gasto (ou complexidade, ou consumo detempo) por um algoritmo é o número de operaçõesconsideradas relevantes realizadas pelo algoritmoe expressa-se esse número como uma função dotamanho da entrada. Essas operações podem sercomparações, operações aritméticas, movimentode dados, etc.
– p. 16/32
Tempo gasto
O tempo gasto (ou complexidade, ou consumo detempo) por um algoritmo é o número de operaçõesconsideradas relevantes realizadas pelo algoritmoe expressa-se esse número como uma função dotamanho da entrada. Essas operações podem sercomparações, operações aritméticas, movimentode dados, etc.
Estamos sempre mais interessados em medir otempo gasto pelos algoritmos no pior caso.
– p. 16/32
Consumo de tempo assintótico
Seja A um algoritmo para um problema P . Otempo de relógio (minutos e segundos) que A
consome para processar uma dada instância de P
depende da máquina usada para executar A. Maso efeito da máquina se resume a uma constantemultiplicativa, ou seja, se A consome tempo t
numa determinada máquina, consumirá tempo 2t
numa máquina duas vezes mais lenta e t/2 numamáquina duas vezes mais rápida.
– p. 17/32
Consumo de tempo assintótico
Para eliminar o efeito da máquina, discutiremos oconsumo de tempo de A a menos de constantesmultiplicativas. A notação assintótica (O,!,") éideal para fazer isso.
– p. 18/32
Analise de Algoritmos
Exemplos de algoritmos
–p. 19/32
Apresentação dos algoritmos
Instrucoesi ! 1;
x ! y;
Se . . . então . . .
Se . . . então . . . senão . . .
Enquanto . . . faça . . .
Para i ! 1 até n faça . . .
– p. 20/32
Apresentação dos algoritmos
Algoritmo: . . .Entrada: . . .Saída: . . .
Inícioinstrução
...instrução
Fim
–p. 21/32
Analise de Algoritmos
Algoritmos de busca
–p. 22/32
Busca sequencial
Algoritmo: Busca sequencialEntrada: Um vetor M1,M2, . . . ,Mn e um elemento xSaída: (“sim”, i) ou “não”
– p. 23/32
Busca sequencial
Algoritmo: Busca sequencialEntrada: Um vetor M1,M2, . . . ,Mn e um elemento xSaída: (“sim”, i) ou “não”
Inícioi ! 1;
Enquanto (i " n) e (x #= Mi) faça i ! i+ 1;
– p. 23/32
Busca sequencial
Algoritmo: Busca sequencialEntrada: Um vetor M1,M2, . . . ,Mn e um elemento xSaída: (“sim”, i) ou “não”
Inícioi ! 1;
Enquanto (i " n) e (x #= Mi) faça i ! i+ 1;Se (i " n) então imprima (“sim”, i) senão imprima “não”
Fim
– p. 23/32
Busca sequencial
Algoritmo: Busca sequencialEntrada: Um vetor M1,M2, . . . ,Mn e um elemento xSaída: (“sim”, i) ou “não”
Inícioi ! 1;
Enquanto (i " n) e (x #= Mi) faça i ! i+ 1;Se (i " n) então imprima (“sim”, i) senão imprima “não”
Fim
Qual o tempo (pior caso) gasto pelo algoritmo?
– p. 23/32
Busca sequencial
Algoritmo: Busca sequencialEntrada: Um vetor M1,M2, . . . ,Mn e um elemento xSaída: (“sim”, i) ou “não”
Inícioi ! 1;
Enquanto (i " n) e (x #= Mi) faça i ! i+ 1;Se (i " n) então imprima (“sim”, i) senão imprima “não”
Fim
Qual o tempo (pior caso) gasto pelo algoritmo?Resposta: O(n)
– p. 23/32
Busca binária
– p. 24/32
Busca bináriaEntrada: Um vetor M1,M2, . . . ,Mn de inteiros ordenado eum inteiro xSaída: (“sim”, i) ou “não”
– p. 24/32
Busca bináriaEntrada: Um vetor M1,M2, . . . ,Mn de inteiros ordenado eum inteiro xSaída: (“sim”, i) ou “não”
Iníciol ! 1; r ! n; achou! falso;
– p. 24/32
Busca bináriaEntrada: Um vetor M1,M2, . . . ,Mn de inteiros ordenado eum inteiro xSaída: (“sim”, i) ou “não”
Iníciol ! 1; r ! n; achou! falso;Enquanto (l " r) e (não achou) faça
– p. 24/32
Busca bináriaEntrada: Um vetor M1,M2, . . . ,Mn de inteiros ordenado eum inteiro xSaída: (“sim”, i) ou “não”
Iníciol ! 1; r ! n; achou! falso;Enquanto (l " r) e (não achou) faça
k ! $(l + r)/2%;
– p. 24/32
Busca bináriaEntrada: Um vetor M1,M2, . . . ,Mn de inteiros ordenado eum inteiro xSaída: (“sim”, i) ou “não”
Iníciol ! 1; r ! n; achou! falso;Enquanto (l " r) e (não achou) faça
k ! $(l + r)/2%;Se x = Mk então achou! verdadeiro
– p. 24/32
Busca bináriaEntrada: Um vetor M1,M2, . . . ,Mn de inteiros ordenado eum inteiro xSaída: (“sim”, i) ou “não”
Iníciol ! 1; r ! n; achou! falso;Enquanto (l " r) e (não achou) faça
k ! $(l + r)/2%;Se x = Mk então achou! verdadeirosenão se x > Mk então l ! k + 1 senão r ! k & 1
– p. 24/32
Busca bináriaEntrada: Um vetor M1,M2, . . . ,Mn de inteiros ordenado eum inteiro xSaída: (“sim”, i) ou “não”
Iníciol ! 1; r ! n; achou! falso;Enquanto (l " r) e (não achou) faça
k ! $(l + r)/2%;Se x = Mk então achou! verdadeirosenão se x > Mk então l ! k + 1 senão r ! k & 1
Se achou então imprima (“sim”, k) senão imprima “não”Fim
– p. 24/32
Busca bináriaEntrada: Um vetor M1,M2, . . . ,Mn de inteiros ordenado eum inteiro xSaída: (“sim”, i) ou “não”
Iníciol ! 1; r ! n; achou! falso;Enquanto (l " r) e (não achou) faça
k ! $(l + r)/2%;Se x = Mk então achou! verdadeirosenão se x > Mk então l ! k + 1 senão r ! k & 1
Se achou então imprima (“sim”, k) senão imprima “não”Fim
Qual o tempo (pior caso) gasto pelo algoritmo?
– p. 24/32
Busca binária - tempo
O tempo gasto pela busca binária é proporcionalao número de iterações do laço “Enquanto ... faça”.
– p. 25/32
Busca binária - tempo
O tempo gasto pela busca binária é proporcionalao número de iterações do laço “Enquanto ... faça”.
O número de elementos do vetor no início da
1a. iteração é n
– p. 25/32
Busca binária - tempo
O tempo gasto pela busca binária é proporcionalao número de iterações do laço “Enquanto ... faça”.
O número de elementos do vetor no início da
1a. iteração é n
2a. iteração é n/2
– p. 25/32
Busca binária - tempo
O tempo gasto pela busca binária é proporcionalao número de iterações do laço “Enquanto ... faça”.
O número de elementos do vetor no início da
1a. iteração é n
2a. iteração é n/2
3a. iteração é n/22
– p. 25/32
Busca binária - tempo
O tempo gasto pela busca binária é proporcionalao número de iterações do laço “Enquanto ... faça”.
O número de elementos do vetor no início da
1a. iteração é n
2a. iteração é n/2
3a. iteração é n/22
...
(i + 1)a. iteração é n/2i
– p. 25/32
Busca binária - tempo
Na última iteração teremos n/2i = 1, o que resultaem
i = log n
– p. 26/32
Busca binária - tempo
Na última iteração teremos n/2i = 1, o que resultaem
i = log n
Portanto, o tempo gasto pela busca binária éO(log n).
– p. 26/32
Analise de Algoritmos
Algoritmos de ordenação
–p. 27/32
Ordenação
Algoritmos básicos:
Trocas sucessivas (bubblesort)
Seleção
Inserção
– p. 28/32
Ordenação - bubblesort
Entrada: Um vetor M = M1,M2, . . . ,Mn de inteirosSaída: O vetorM ordenado em ordem não decrescente
– p. 29/32
Ordenação - bubblesort
Entrada: Um vetor M = M1,M2, . . . ,Mn de inteirosSaída: O vetorM ordenado em ordem não decrescente
InícioPara j ! i até n& 1 façaPara 1 ! i até j façaSe Mi > Mi+1 então “troque Mi com Mi+1”
Fim
– p. 29/32
Ordenação - bubblesort
Entrada: Um vetor M = M1,M2, . . . ,Mn de inteirosSaída: O vetorM ordenado em ordem não decrescente
InícioPara j ! i até n& 1 façaPara 1 ! i até j façaSe Mi > Mi+1 então “troque Mi com Mi+1”
Fim
Qual o tempo (pior caso) gasto pelo algoritmo?
– p. 29/32
Ordenação - bubblesort
Entrada: Um vetor M = M1,M2, . . . ,Mn de inteirosSaída: O vetorM ordenado em ordem não decrescente
InícioPara j ! i até n& 1 façaPara 1 ! i até j façaSe Mi > Mi+1 então “troque Mi com Mi+1”
Fim
Qual o tempo (pior caso) gasto pelo algoritmo?Resposta: O(n2)
– p. 29/32
Ordenação por seleção
Entrada: Um vetor M = M1,M2, . . . ,Mn de inteirosSaída: O vetorM ordenado em ordem não decrescente
– p. 30/32
Ordenação por seleção
Entrada: Um vetor M = M1,M2, . . . ,Mn de inteirosSaída: O vetorM ordenado em ordem não decrescente
Idéia:Selecione o maior elementoTroque-o com o “último” da lista
– p. 30/32
Ordenação por seleção
Entrada: Um vetor M = M1,M2, . . . ,Mn de inteirosSaída: O vetorM ordenado em ordem não decrescente
Idéia:Selecione o maior elementoTroque-o com o “último” da lista
Exercício: Escreva o algoritmo
– p. 30/32
Ordenação por seleção
Entrada: Um vetor M = M1,M2, . . . ,Mn de inteirosSaída: O vetorM ordenado em ordem não decrescente
Idéia:Selecione o maior elementoTroque-o com o “último” da lista
Exercício: Escreva o algoritmo
Qual o tempo (pior caso) gasto pelo algoritmo?
– p. 30/32
Exercícios1. Escreva um algoritmo para ordenar os elementos de
um vetor utilizando a seguinte idéia:selecione o menor elementotroque-o com o “primeiro” da lista
2. Escreva um algoritmo para ordenar os elementos deum vetor M1,M2, . . . ,Mn utilizando a seguinte idéia(ordenação das cartas de baralho - inserção):
suponha que M1,M2, . . . ,Mi já está ordenadoinsira Mi+1 na posição correta para obterM1,M2, . . . ,Mi+1 ordenado
– p. 31/32
Exercícios3. Escreva um algoritmo para verificar se os elementos de
um vetor M1,M2, . . . ,Mn estão em ordem nãodecrescente.
4. Um algoritmo de ordenação é estável se não altera aposição relativa dos elementos de mesmo valor.(a) Bubblesort é estável?(b) Seleção é estável?
– p. 32/32