VA Analise Algoritmos 01

Prévia do material em texto

Aula 1
Desenvolvimento de algoritmos
Análise de Algoritmos
Gisele Alves Santana
Nesta aula, você vai:
§ Revisar os conceitos básicos e lógicos utilizados 
para a construção de algoritmos;
§ Entender as formas de representação dos 
algoritmos, principalmente o pseudocódigo; 
§ Conhecer a importância da análise de 
algoritmos no contexto computacional; 
§ Entender o conceito de 
complexidade e como são 
realizados os cálculos para 
definir o tamanho 
de um problema. 
Resumo da aula
Estuda alguns problemas computacionais que 
surgem em vários contextos e aplicações.
Basicamente, a análise de um algoritmo 
considera dois fatores:
§ Prova de que o algoritmo está correto;
§ Estimação do tempo de execução 
que o algoritmo consome.
§ Em alguns casos também 
é considerada a estimativa 
do espaço de memória 
utilizado pelo algoritmo. 
Análise de algoritmos
Objetivo geral 
§ Permitir que, dado dois algoritmos que 
resolvem um mesmo problema, decidir qual 
deles é o mais eficiente;
§ A análise de complexidade é responsável pela 
obtenção de estimativas de tempos de execução 
de programas que implementam um algoritmo.
Análise de algoritmos
Desejável: avaliar o desempenho de um algoritmo 
independentemente da sua implementação
§ Levar em conta apenas o número de instruções 
executadas para determinadas entradas;
§ São consideradas apenas as instruções principais 
(operações básicas para a execução do algoritmo). 
Análise de algoritmos
É dependente da quantidade de dados que 
são processados
§ Tamanho da entrada;
§ Por exemplo: busca por um registro em uma 
lista com 250 registros é maior que em uma 
lista com 20 reg. 
Análise de algoritmos
Operação de busca em uma lista linear não ordenada:
§ Número de comparações executadas varia muito, 
pois a chave desejada pode estar armazenada no 
início ou no fim da lista;
§ Complexidade: expressa em função 
do tamanho da lista.
Análise de algoritmos
Casos especiais:
§ Pior caso: ocorre quando o aumento do valor de 
“n” (aumento das entradas) resulta em um 
maior crescimento do número de operações;
§ Melhor caso: ocorre quando o aumento do valor 
de “n” (aumento das entradas) 
resulta em um menor crescimento 
do número de operações;
Análise de algoritmos
Casos especiais:
§ Caso médio: ocorre quando o algoritmo se 
comporta de maneira mediana, ou seja, quando 
se consideram todas as possíveis entradas 
e respectivas probabilidades de ocorrência. 
Análise de algoritmos
Problemas e instâncias
§ Problema computacional: formado por uma 
coleção de instâncias;
§ Instância: conjunto de dados
• Exemplo: problema de encontrar a média dos 
elementos do vetor V[11 30 35 22 56 98] que 
possui 6 elementos inteiros. 
• Uma instância:
- Encontrar a média 
dos elementos do vetor.
Análise de algoritmos
Problemas e instâncias
§ Tamanho de uma instância: corresponde à 
quantidade de dados utilizada para a descrição 
da instância;
§ Problema que calcula a média dos elementos: 
• Tamanho da instância [11 30 35 22 56 98] é = 6. 
Análise de algoritmos
Problemas e instâncias
§ Percebe-se que o tamanho de uma instância 
geralmente corresponde ao número de 
elementos n;
§ Porém, o tamanho pode corresponder ao número 
total de dígitos decimais do vetor, neste caso, 12.
Análise de algoritmos
Consumo de tempo
§ Para cada instância, o algoritmo consome uma 
quantidade de tempo diferente;
§ Suponha que o algoritmo consome T(I) unidades 
de tempo para processar a instância I;
§ A relação entre T(I) e o tamanho 
de I oferece uma medida da 
eficiência do algoritmo;
Análise de algoritmos
Consumo de tempo
§ Geralmente, um problema tem muitas 
instâncias diferentes de um mesmo tamanho, 
exigindo a introdução dos conceitos de 
“melhor caso” e “pior caso”. 
Análise de algoritmos
Consumo de tempo
§ Dado um algoritmo A para o problema e um número 
n, sendo T1(n) o máximo de T(I) para todas as 
instâncias I de tamanho n do problema; 
Diz-se que:
• No pior caso – T1 mede o consumo de tempo de A.
§ Seja T2(n) o mínimo de T(I) para todas 
as instâncias I de tamanho n.
Diz-se que:
• No melhor caso – T2 mede o 
consumo de A.
Análise de algoritmos
Continuando...
Desenvolvimento de algoritmos 
Pode ser comparado a uma receita que indica o 
passo a passo dos métodos necessários para a 
resolução de uma tarefa. 
O algoritmo não é capaz de responder a pergunta 
“o que fazer?”, mas sim “como fazer”. 
Um algoritmo pode ser definido como uma sequência 
lógica, finita e definida de instruções 
que devem ser seguidas para 
resolver um problema ou 
executar uma tarefa.
Algoritmo
Exemplo: trocar pneu do carro
Algoritmo
Formas de representação
§ Descrição narrativa;
§ Pseudocódigo;
§ Fluxograma.
Algoritmo
Descrição narrativa
Algoritmo
Início
• Verificar se o interruptor está desligado;
• Procurar por uma lâmpada nova;
• Pegar uma escada;
• Levar a escada até o local;
• Posicionar a escada;
• Subir os degraus;
• Retirar a lâmpada queimada;
• Colocar a lâmpada nova;
• Descer da escada;
• Acionar o interruptor;
• Se a lâmpada não acender, então:
§ Retirar a lâmpada queimada;
§ Colocar outra lâmpada nova
• Senão
§ Tarefa terminada;
Fim
Fluxograma
Algoritmo
Pseudocódigo
Algoritmo
Algoritmo <nome do algoritmo>
<declaração de variáveis>
Início
<corpo do algoritmo>
Fim
Algoritmo Calcula_dobro
Variáveis Num, Dobro: real;
Início
Leia (Num);
Dobro <- 2*num;
Escreva (dobro);
Fim
Pseudocódigo
Algoritmo
Algoritmo Calculadora
Declaração de variáveis
num1, num2, resultado: Real;
Inicio
Escreva(“Digite um número: “);
Leia(num1);
Escreva(“Digite outro número: “);
Leia(num2);
resultado <- num1 + num2;
Escreva(“Soma = “, resultado);
resultado <- num1 - num2;
Escreva(“Subtração = “, resultado);
resultado <- num1 * num2;
Escreva(“Multiplicação = “, resultado);
resultado <- num1 / num2;
Escreva(“Divisão = “, resultado);
Fim
Pseudocódigo
§ Pontos importantes:
• Variável
- Espaço de memória alocado para 
armazenamento de dados; 
- No exemplo, foram criadas 3 variáveis.
Algoritmo
• Símbolo "<-"
- Atribuição de valor a uma variável. 
- Por exemplo, (resultado <= num1 + num2) 
atribui à variável resultado, o valor da soma 
dos valores armazenados nas 
variáveis num1 e num2.
Algoritmo
Pseudocódigo
§ Pontos importantes:
• Comando "Leia(num1)“
- Significa que o algoritmo está lendo o que o 
usuário digitou e armazenando na 
variável numero1.
• Comando “Escreva(resultado)”
- Exibe na tela o valor atual 
da variável resultado.
Algoritmo
Finalizando...
Desenvolvimento de algoritmos 
Complexidade
§ Espaço exigido e ao tempo de execução de um 
algoritmo para determinada entrada de dados; 
§ Cálculo da complexidade de um algoritmo: 
• Máquina de Turing: modelo matemático simples 
capaz de medir a quantidade de passos utilizados 
para a execução de um algoritmo;
• Pode ser medida de acordo 
com o número de segundos 
consumidos na execução 
do algoritmo. 
Medidas de complexidade
Não é conveniente calcular os tempos de 
execução em máquinas específicas. 
Assim, a maioria das análises de complexidade 
considera apenas a quantidade de operações 
elementares que são executadas. 
Está relacionada ao crescimento assintótico da 
contagem de operações.
Medidas de complexidade
Complexidade assintótica
§ Determina o tamanho de problemas que 
podem ser solucionados por um algoritmo;
§ Para um algoritmo que processa entradas de 
tamanho “n” no tempo t*n2, onde t é uma 
constante, diz-se que a complexidade de 
tempo do algoritmo é: O(n2),ou seja, “ de ordem n2”. 
Medidas de complexidade
Complexidade assintótica
§ Relacionada ao número de unidades de 
tempo (UT) necessárias para processar uma 
entrada de tamanho “n”;
§ Unidade de tempo: 1 milissegundo;
§ Assim: 1UT = 1 ms = 10-3 segundos;
§ Equação do cálculo do tamanho 
de problemas:
Medidas de complexidade
( ) *T n n UT=
T – tempo desejado;
UT – unidade de tempo (medida em 1 ms);
n – tamanho do problema.
Exemplo
Cálculo do tamanho do problema:
§ Para cada algoritmo;
§ 1 segundo, 1 minuto, 1 hora.
Medidas de complexidade
ALGORITMO COMPLEXIDADE DE TEMPO
X1 n
X2 n log2 n
X3 n2
X4 n3
Algoritmo X1
Medidas de complexidade
Algoritmo X2
Medidas de complexidade
Algoritmo X3
Medidas de complexidade
Algoritmo X4
Medidas de complexidade
Tabela: resumo com os cálculos
Medidas de complexidade
ALGORITMO
COMPLEXIDADE 
DE TEMPO
1 SEGUNDO 1 MINUTO 1 HORA
X1 n 1.000 60.000 3.600.000
X2 n log2 n 140 4893 200.000
X3 n2 31,6 244,9 1.897,4
X4 n3 10 39,1 153,3
Para a escolha de um determinado algoritmo 
dentre vários que resolvem o mesmo problema, 
pode-se optar por aquele que possui fácil 
entendimento, depuração e codificação, ou ainda, 
pode-se selecionar um algoritmo que usa 
eficientemente os recursos do computador.
Medidas de complexidade