Conceitos Fundamentais de Análise de Algoritmos
114 pág.

Conceitos Fundamentais de Análise de Algoritmos


DisciplinaAnálise de Algoritmos191 materiais713 seguidores
Pré-visualização5 páginas
Análise de Algoritmos
CONCEITOS FUNDAMENTAISCONCEITOS FUNDAMENTAIS
Bacharelado em Ciência da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Fevereiro de 2016
 
Conteúdo
\u25cf Introdução
\u25cf Análise de Algoritmos
\u25cf Complexidade Computacional
\u25cf Revisão Matemática
\u25cf Funções de Complexidade
\u25cf Notação Assintótica
\u25cf Técnicas de Análise de Algoritmos
\u25cf Leitura Recomendada
 
Problema Computacional
\u25cf Relaciona a entrada e a saída 
desejada
\u25cf Uma instância é um possível valor de 
entrada
ORDENAÇÃO
Entrada: Uma sequência de n números a
1
, a
2
, ..., a
n
Saída: Uma reordenação da sequência de entrada a
1
', a
2
', ..., 
 a
n
', onde a
1
' \u2264 a
2
' \u2264 \u2026 \u2264 a
n
' (ordem crescente) ou 
 a
1
' \u2265 a
2
' \u2265 \u2026 \u2265 a
n
' (ordem decrescente)
ORDENAÇÃO
Entrada: Uma sequência de n números a
1
, a
2
, ..., a
n
Saída: Uma reordenação da sequência de entrada a
1
', a
2
', ..., 
 a
n
', onde a
1
' \u2264 a
2
' \u2264 \u2026 \u2264 a
n
' (ordem crescente) ou 
 a
1
' \u2265 a
2
' \u2265 \u2026 \u2265 a
n
' (ordem decrescente)
50, 23, 10, 1, -8, 1004 é uma instância para a ordenação!50, 23, 10, 1, -8, 1004 é uma instância para a ordenação!
 
Algoritmo
\u25cf Representa um conjunto bem 
definido de instruções que toma 
um valor de entrada (ou conjunto 
de valores) e produz algum valor 
(ou conjunto de valores) como 
saída \u2013 solução de um problema
\u25cf Algoritmo é uma tecnologia!
\u25cf É tão importante quanto hardware 
rápido, interfaces intuitivas, sistemas 
orientados a objetos, etc.
 
Avaliação de Algoritmos
\u25cf Corretude
\u25cf Um algoritmo está correto se para toda entrada 
(legal) ele produz a saída correta
\u25cf Simplicidade
\u25cf Um algoritmo é simples se é de fácil entendimento, 
implementação e manutenção
\u25cf Eficiência (em função do tamanho da entrada)
\u25cf Busca-se melhor desempenho, qualidade de serviço e 
uso adequado de recursos de processamento e 
armazenamento
\u25cf Quanto tempo o algoritmo gasta para produzir a 
saída correta?
\u25cf Quanto espaço de memória é necessário?
 
Analisar um algoritmo é 
estudar o seu 
comportamento frente a 
diferentes tamanhos e valores 
de entrada para produzir a 
saída esperada 
 
Conteúdo
\u25cf Introdução
\u25cf Análise de Algoritmos
\u25cf Complexidade Computacional
\u25cf Revisão Matemática
\u25cf Funções de Complexidade
\u25cf Notação Assintótica
\u25cf Técnicas de Análise de Algoritmos
\u25cf Leitura Recomendada
 
Como Predizer a Eficiência de 
um Algoritmo?
\u25cf Estimativa de tempo e recursos 
consumidos
\u25cf Linguagem de programação utilizada
\u25cf Estruturas de dados utilizadas
\u25cf Estilo de programação
\u25cf Compilador
\u25cf Arquitetura de máquina
\u25cf Ambiente de execução
 
Possibilidades Reais para 
Analisar Algoritmos
\u25cf 1) Codificar o algoritmo usando uma 
linguagem de programação, executar o 
programa e medir o tempo gasto
\u25cf Há dificuldade de medir o tempo gasto
\u25cf Máquina, linguagem de programação, 
compilador, dados de entrada têm que ser 
idênticos para que a comparação entre 2 ou mais 
algoritmos seja coerente
\u25cf 2) Definir uma medida de custo para cada 
instrução do algoritmo e derivar uma 
operação matemática para o tempo de 
execução
 
Comparação entre 
Algoritmos
\u25cf Recursos tipicamente analisados
\u25cf Espaço de armazenamento
\u25cf Tempo de execução
\u25cf Para comparar os diferentes 
algoritmos, de forma justa, é 
necessário definir um modelo 
abstrato de máquina
 
Modelo RAM (Random-Access 
Machine)
\u25cf Modelo de computação genérico com um único 
processador
\u25cf Hirarquia de memória não modelada
\u25cf Tipos 
\u25cf Inteiros e ponto flutuante
\u25cf Instruções
\u25cf Aritméticas (adição, subtração, multiplicação, 
divisão, resto)
\u25cf Movimentação de dados (carregar, armazenar, 
copiar)
\u25cf Controle (desvio condicional e incondicional, 
chamada e retorno de rotina)
 
Tempo de Execução
\u25cf Vamos caracterizar o tempo de 
execução de um algoritmo como função 
do tamanho da entrada
\u25cf A medida de complexidade dá uma idéia 
de como varia o tempo de execução de 
uma implementação de um algoritmo 
quando varia o tamanho da entrada
\u25cf Por exemplo, numa inversão de matrizes, o 
número de operações (adição e multiplicação) 
varia com a dimensão da matriz, ou na 
ordenação de uma lista, varia com o número de 
elementos da lista
 
Medição Empírica do Tempo 
de Execução
\u25cf Obtenção do tempo através da execução 
propriamente dita (em um computador real)
\u25cf Resultados dependem do compilador, hardware, quantidade 
de memória disponível, etc...
\u25cf Experimentos são realizados sobre um conjunto limitado de 
entradas de teste 
\u25cf É difícil comparar os tempos de execução 
de 2 ou mais algoritmos, a menos que 
executados sob o mesmo ambiente 
(hardware + software) e condições
\u25cf É necessário implementar o algoritmo e executá-lo para 
estudar o tempo de execução
 
Medição Analítica do Tempo 
de Execução
\u25cf Obtenção de uma ordem de grandeza do 
tempo de execução independente do 
computador, linguagem de programação, 
compilador e condições locais de 
processamento
\u25cf Tem por base uma EXPRESSÃO MATEMÁTICA que 
traduz o comportamento do algoritmo
\u25cf Considera todas as entradas possíveis
\u25cf É fácil comparar os tempos de execução de 
2 ou mais algoritmos independente de 
hardware e software
\u25cf Pode ser efetuada considerando o algoritmo 
em si
 
Análise Analítica de 
Algoritmos
\u25cf Resulta em uma função T(n), real e 
não negativa
\u25cf n é o tamanho da entrada, n \u2265 0
\u25cf T(n) caracteriza o tempo de execução 
em função do tamanho da entrada n
\u25cf Representa a quantidade estimada de 
passos necessários para a execução do 
algoritmo para uma entrada de tamanho 
n
 
Passo
\u25cf É independente de máquina
\u25cf Operação com tempo de execução constante 
ou execução de um número fixo de operações 
básicas de tempo constante
\u25cf Exemplos
\u25cf Atribuição de valores a variáveis
\u25cf Chamadas de métodos
\u25cf Operações matemáticas
\u25cf Comparação entre 2 valores
\u25cf Seguir uma referência a um objeto
\u25cf Retorno de um método
 
Exemplo
\u25cf Passo = operação de atribuição
 
Na Prática...
\u25cf Estamos interessados em contar 
o número de passos executados
\u25cf Usamos tal valor como estimativa 
de tempo de execução de um 
algoritmo
\u25cf A contagem se relaciona com o 
tempo de execução no RAM, pois 
cada passo corresponde a uma 
instrução realizada em tempo 
constante
 
Exemplo
Encontrar o menor elemento de um vetor A de inteiros, 
com n elementos
int calculamenor (int A[], int n){
 int i, menor;
 menor = A[0];
 for (i = 1; i < n; i++){
 if (A[i] < menor)
 menor = A[i];
 }
 return menor;
}
São realizadas n-1 
comparações, 
então T(n) = n - 1
 
Medidas de Complexidade
Um algoritmo pode executar mais rapidamente sobre 
algumas entradas do que sobre outras do mesmo tamanho
\u25cf Pior caso
\u25cf Corresponde ao maior tempo de 
execução sobre todas as entradas 
de tamanho n
\u25cf Melhor caso
\u25cf Corresponde ao menor tempo de 
execução sobre todas as entradas 
de tamanho n
 
Medidas de Complexidade
Um algoritmo pode executar mais rapidamente sobre 
algumas entradas do que sobre outras do mesmo tamanho
\u25cf Caso médio (ou esperado)
\u25cf Comportamento médio do algoritmo frente a 
variados e significativos valores de entrada
\u25cf Para muitos algoritmos, é difícil determinar o 
caso médio 
\u2013 Seria preciso considerar as n! permutações de 
entrada ocorrem com a mesma probabilidade
\u25cf Estimativa razoável
\u2013 Média dos tempos de execução sobre todas as 
entradas de tamanho n
 
Exemplo
Pesquisa Sequencial
\u25cf Problema: acessar os registros de um 
arquivo
\u25cf Cada registro possui uma chave única que 
é utilizada para recuperação