Análise de Algoritmos - Problemas, instâncias, algoritmos e tempo

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


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


Dados dois algoritmos para um mesmo problema,a análise permite decidir qual dos dois é maiseficiente.

– p. 3/32


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


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


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


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


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


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


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


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


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


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


Inícioi ! 1;

Enquanto (i " n) e (x #= Mi) faça i ! i+ 1;

– p. 23/32

Busca sequencial


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


Inícioi ! 1;


Fim

Qual o tempo (pior caso) gasto pelo algoritmo?

– p. 23/32

Busca sequencial


Inícioi ! 1;


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


Iníciol ! 1; r ! n; achou! falso;

– p. 24/32


Iníciol ! 1; r ! n; achou! falso;Enquanto (l " r) e (não achou) faça

– p. 24/32



k ! $(l + r)/2%;

– p. 24/32



k ! $(l + r)/2%;Se x = Mk então achou! verdadeiro

– p. 24/32



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




Se achou então imprima (“sim”, k) senão imprima “não”Fim

– p. 24/32




Se achou então imprima (“sim”, k) senão imprima “não”Fim


– 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



O número de elementos do vetor no início da

1a. iteração é n

– p. 25/32




1a. iteração é n

2a. iteração é n/2

– p. 25/32




1a. iteração é n



– p. 25/32




1a. iteração é n



...

(i + 1)a. iteração é n/2i

– p. 25/32


Na última iteração teremos n/2i = 1, o que resultaem

i = log n

– p. 26/32


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


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



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




Fim


– p. 29/32




Fim

Qual o tempo (pior caso) gasto pelo algoritmo?Resposta: O(n2)

– p. 29/32

Ordenação por seleção


– p. 30/32



Idéia:Selecione o maior elementoTroque-o com o “último” da lista

– p. 30/32




Exercício: Escreva o algoritmo

– p. 30/32




Exercício: Escreva o 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

Education

Análise de Algoritmos - Problemas, instâncias, algoritmos e tempo