Analise de Algoritmo

Prévia do material em texto

ANÁLISE DE ALGOTIMOS
Aula #02
Kissema Eduardo Rafael
Instituto Superior Politécnico de Tecnologias e Ciências
Departamento de Engenharias e Tecnologias
08/08/2017
Objectivos da Aula
} Instrutivo:
} Identificar, comparar e demonstrar as funções de eficiências 
dos algoritmos através de notações assimptotas.
} Educativo:
} Sentir a necessidade de conhecer a ordem de crescimento
dos algoritmos
2
Sumário
} Introdução
} Estruturas de Dados
} Fundamentos de Análise de Eficiência de Algoritmos
} Mecanismos de Análise
} Medidas de Tamanho de Entrada
} Unidades para medição do tempo de execução
} Ordens de crescimento
} Eficiências de Pior caso, melhor caso e caso médio
} Notação Assimptótica e classes de eficiências básicas
} Definição Informal
} Notações O, Ω e 𝚯 e suas propriedades
} Uso de limites para comparação de ordens de crescimento
} Classes de eficiências básicas
3
Introdução
} Algoritmo
} É uma sequencia não ambígua de instruções que serve para
resolver problema, i.e., para obter requerida saída para
qualquer dado de entrada em quantidade de tempo finito
} Programas de computador não existem sem algoritmos
4
Introdução
} Passos necessário entre o desenho e análise do algoritmo
} Entendimento do problema
} Considerar a capacidade da componente computacional
} Escolha entre a solução exacta e aproximada do problema
} Escolha da estrutura de dados apropriada
} Escolha da técnica do desenvolvimento do algoritmo
} Métodos da especificação do algoritmo
5
Introdução
} Passos necessário entre o desenho e análise do algoritmo
} Provar se o algoritmo está correcto
} Analisar o algoritmo
} Eficiência do:
¨ Tempo
¨ Espaço
} Simplicidade
} Generalidade
} Codificar o algoritmo
6
Introdução
} Tipos de Problemas
} Ordenação
} Buscas (Pesquisa)
} Processamento de textos
} Problemas de grafos
} Problemas de combinação
} Problemas Geométricos
} Problema numéricos
7
} Estrutura de Dados
} Estrutura de dados Lineares
} Listas sequenciais
} Listas dinâmicas (Simplesmente e
Duplamente ligadas)
} Listas especiais (Pilhas e Filas)
} Estruturas de dados não lineares
} Grafos
} Arvores
} Conjuntos e dicionários
Mecanismos de Análise
} Análise de algoritmos num sentido mais restrito, é uma técnica
para investigação da eficácia de um algoritmo em relação a
dois recursos:
} Tempo de execução: A rapidez da execução de um algoritmo
} Espaço de memória: O espaço necessário para execução do
algoritmo
} A eficiência pode ser estudado em termos quantitativos
precisos, ao contrário de dimensões como a simplicidade e
generalidade.
} Dada a velocidade e a memória dos computadores de hoje, as
considerações de eficiência são de primordial importância do
ponto de vista prático.
8
Mecanismos de Análise
} Medição do tamanho da entrada
} Começando com a observação óbvia de que quase todos os
algoritmos têm tempo de execução maior se o tamanho de
entrada do algoritmo for de maior dimensão.
} Por exemplo, leva mais tempo para:
¨ Ordenar vector de tamanho muito grande
¨ Multiplicar matrizes maiores,e assim por diante.
} Portanto, é lógico a investigação da eficiência de um algoritmo
como uma função de algum parâmetro n que indica o tamanho
de entrada do algoritmo.
} Na maioria dos casos, a selecção de tal parâmetro é bastante
simples
9
Mecanismos de Análise
} Medição do tamanho de entrada
} Exemplo: 
algoritmo somar(a, b);
algoritmo somatorio(a,b,c);
algoritmo buscaSequencial(A[0..n-1], k);
algoritmo isQuadrada(A[0..n-1,0..n-1]);
algoritmo mult(A[0..m-1], B[0..n-1]);
10
Mecanismos de Análise
} Unidades para medição do tempo de execução
} Podemos medir o tempo de execução com segundos,
milissegundo?
} Há desvantagens óbvias para tal abordagem, tais como:
} A dependência da velocidade de um computador específico
} A dependência sobre a qualidade de um programa de execução do
algoritmo e do compilador usado para gerar o código de máquina
} A dificuldade de cronometrar o tempo de funcionamento real do
programa.
11
Mecanismos de Análise
} Unidades para medição do tempo de execução
} Como pretendemos medir a eficiência de um algoritmo, gostaríamos
de ter uma métrica que não depende destes factores externos.
} Uma das possibilidade é contar o número de vezes que cada
instrução do algoritmo é executado.
} Essa abordagem é excessivamente difícil e, como veremos, geralmente
desnecessário.
} A única coisa a fazer é identificar a operação mais importante do
algoritmo, chamado de operação básica, a operação que mais
contribuí para o tempo total de execução, e calcular o número de
vezes que a operação básica é executada.
} Para a análise do tempo de execução de um algoritmo usa-se a contagem
do número de vezes que a operação básica do algoritmo é executado
sobre as entradas de tamanho n.
12
Mecanismos de Análise
} Ordem de Crescimento
} A diferença em tempos de execução com tamanho de entrada 
menor não é o factor que distingue a eficiência de algoritmos.
} Para valores de n maior é somente a função de ordem de 
crescimento que conta.
13
n log𝑛 n n.log𝑛 n2 n3 2n n!
10 3,3 101 3,3	x	101 102 103 103 3,6	x	106
102 6,6 102 6,6	x	102 104 106 1,3	x	1030 9,3	x	10157
103 10 103 10	x	103 106 109
104 13 104 13	x	104 108 1012
105 17 105 17	x	105 1010 1015
106 20 106 20	x	106 1012 1018
Mecanismos de Análise
} Casos de Eficiências
} Existem muitos algoritmos que o seu tempo de execução depende 
não só do tamanho da entrada mas sim, um especifico valor de 
entrada.
} Exemplo: 
algoritmo buscaSequencial(A[0..n-1], k)
iß 0
enquanto i < n e A[i] <> k faça
i ß i + 1
Se i < n 
retorna i
Senão 
retorna -1
} Claramente, o tempo de execução do algoritmo pode ser diferente 
para lista A[n] para mesma entrada n.
14
Mecanismos de Análise
} Pior caso
} É o método mais fácil de se obter. Baseia-se no maior tempo de 
execução sobre todas as entradas de tamanho n.
} No algoritmo anterior, pode-se observar que o pior caso, acontece 
quando o elemento a pesquisar não existir ou se o mesmo se 
encontrar na última posição, o algoritmo faz todas comparações 
possíveis para todos valores de entrada de tamanho n: C(pior)=n.
} Melhor Caso
} É o menor tempo de execução em uma entrada de tamanho n.
} Podemos analisar eficiência do melhor caso como seguinte:
} Determinamos o valor do tamanho da entrada em que o contador C(n) é
o menor para todos valores entrada de tamanho n. Isso, não quer dizer
que o melhor caso seja o menor valor de n, isto é, para tamanho de
entrada n o algoritmo executa mais rápido.
} No exemplo anterior, Cmelhor (n) = 1
15
Mecanismos de Análise
} Caso Médio
} Consideremos o caso do algoritmo da pesquisa sequencial
} A probabilidade de uma busca com sucesso é igual p onde 0<p<1
} A probabilidade de sucesso ocorrer na i-ésima posição da lista é igual
para cada i.
} No caso da busca com sucesso, a probabilidade de sucesso ocorrer
na i-ésima posição da lista é p/n para cada i e o número de
comparações feitas pelo algoritmo nesta situação é obviamente i.
} No caso de insucesso, o número de comparações é n com a
probabilidade de (1 – p), assim:
16
Mecanismos de Análise
} Caso Médio
Cmed(n) =[1(p/n) + 2 (p/n) + … + i(p/n) + … + n(p/n)] + n(1 – p)
=(p/n)[1 + 2 + … + i + … +n] + n(1 – p)
=(p/n)[n(n + 1)/2] + n(1 – p)
=p(n+1)/2 + n(1 – p) 
} Se p = 1 (sucesso): o número de comparações é (n+1)/2
} Se p = 0 (insucesso): o número de comparações é n.
17
Notação assimptótica
} Na sessão anterior, a análise da eficiência concentrou-se
na ordem de crescimento da contagem de operação
básica do algoritmo como principal indicador da eficiência
do algoritmo.} Para comparar e eleger essas ordens de crescimento,
usamos as seguintes notações: O(big oh ),Ω(big omega) e
Θ (big theta)
18
Notação assimptótica
} O(g(n)) é um conjunto de todas funções com o menor 
ou igual ordem de crescimento que g(n) (para múltiplos 
de uma constante quando n tende a infinito)
} Exemplo:
} n∈O(n2), 100n + 5 ∈O(n2), (½)n(n–1) ∈O(n2).
} n3∉O(n2), 0,00001n3∉O(n2), n4 +n + 1∉O(n2).
} Ω(g(n)) é um conjunto de todas funções com maior ou 
igual ordem de crescimento que g(n). 
} Exemplo:
n3∈ Ω(n2), ½ n(n–1)∈ Ω(n2)
mas 100n +5 ∉ Ω(n2).
} Θ(g(n)) é um conjunto de todas funções com a mesma 
ordem de crescimento que g(n).
19
Notação assimptótica
} Notação Ο
} Definição:
A função t(n)∈O(g(n)), se e somente se existe uma constante 
positiva c e um inteiro não negativo n0 para todo positivo n, tal 
que:
t(n)≤cg(n) para todo n≥n0
Exemplo: 100n+5 ∈ O(n2).
Prova:
100n+5 ≤100n +n (∀ n≥5)
= 101n
≤ 101n2
Pondo c = 101 e n0= 5, temos 100n+5 ∈ O(n2)
20
Notação assimptótica
} Notação Ω
} Definição:
A função t(n)∈Ω(g(n)), se e somente se existe uma constante 
positiva c e um inteiro não negativo n0 para todo positivo n, tal 
que:
t(n) ≥ cg(n) para todo n≥n0
Exemplo: n3∈Ω(n2).
Prova: n3≥n2 para todo n≥ 0,
Portanto podemos seleccionar c=1 e n0=0.
21
Notação assimptótica
} Notação Θ
} Definição:
A função t(n)∈Θ(g(n)), se e somente se existem constantes 
positivas c1 e c2 e um inteiro não negativo n0 para todo 
positivo n, tal que:
c1g(n)≤ t(n)≤c2g(n) para todo n≥n0
Exemplo: (½)n(n-1)∈Θ(n2) 
(½)n(n-1) = (½)n2 – (½)n ≤ (1/2)n2 para todo n ≥ 0
(½)n(n-1)=(1/2)n2 – (1/2)n ≥ (½)n2 – (½)n – (½)n para todo n ≥ 2
=(¼) n2
Logo, pode-se seleccionar c2=¼ , c1=½ e n0=2
22
Notação assimptótica
} Usando limites para comparação de ordem de crescimento
} As definições de Ο,Θ e Ω indispensáveis para demonstração
das propriedades abstractas, dificilmente são usadas para
comparação de ordens de crescimento entre duas específicas.
O método conveniente de o fazer é baseado no calculo de
limite da razão de duas funções:
} Os dois primeiro casos significa que t(n)∈O(g(n)) e os dois 
últimos significa t(n)∈Ω(g(n)) e o segundo caso implica que 
t(n) ∈ Θ(g(n))
23
Notação assimptótica
} Usando limites para comparação de ordem de 
crescimento
} Compare a ordem de crescimento das seguintes funções 
(½)n(n–1) e n2.
} Como o limite é igual a um número positivo, então as duas 
funções tem a mesma ordem de crescimento, assim sendo, 
(½)n(n–1)∈Θ(n2)
24
Notação assimptótica
} Classes de eficiências básicas
25
Classe Nome
1 constante
log n logarítmica
n linear
n log n Linearítmica
n2 quadrática
n3 cúbica
2n exponencial
n! factorial