Módulo_-_Análise_de_algoritmos

Prévia do material em texto

Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de Algoritmos
Escola de Ciência e Tecnologia
Disciplina:ESD-2
Análise de Algoritmos
1
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmo
• Todo algoritmo é projetado para executar uma
determinada função e, para isso, ele utiliza uma
quantidade de memória e tempo de
Disciplina:ESD-2
quantidade de memória e tempo de
processamento.
• A resolução de um problema pode ser realizada
por um conjunto de algoritmos distintos.
– melhores resultados na utilização de algoritmos é
importante determinar seu desempenho.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmo
• Exemplo:
– Organizar elementos
Disciplina:ESD-2
Qual o melhor algoritmo para organizar 
elementos?
Como compara-los?
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• Análise de algoritmos
– Analisar um algoritmo significa prever os 
recursos de que ele necessitará.
Disciplina:ESD-2
recursos de que ele necessitará.
– A área de analise de algoritmo possui dois tipos 
de problemas distintos:
1. Análise da classe de um algoritmo
2. Análise de um algoritmo especifico
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• Análise de algoritmos: Classe de algoritmo
– Determinar o algoritmo de menor custo possível
para resolver um problema.
Disciplina:ESD-2
para resolver um problema.
• Análise de algoritmos: Algoritmo especifico
– Calcular o custo de um determinado algoritmo
na resolução de um problema.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de complexidade
• Como fazer então para comparar a eficiência 
de algoritmos?
• Quais métricas utilizar? 
Disciplina:ESD-2
• Quais métricas utilizar? 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de Algoritmos
• Métricas possíveis:
– Tempo real de execução ou processamento.
• Medição do tempo real de execução de um 
Disciplina:ESD-2
• Medição do tempo real de execução de um 
algoritmo em um computador
Os resultados terão forte dependência do compilador, de 
hardware e memória disponibilizada.
Dificuldade em ser replicado, possui fortes dependências
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de Algoritmos
• Devemos adotar uma métrica livre de 
dependências
–Modelo matemático ou modelo de computação 
Disciplina:ESD-2
–Modelo matemático ou modelo de computação 
genérico com um único processador, a RAM 
(Máquina de acesso aleatório)
As instruções são executadas uma após a outra , 
sem operações concorrentes.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• O método RAM: Contem instruções existentes 
em computadores reais.
Disciplina:ESD-2
– Instruções aritméticas: soma, subtração, multiplicação, 
divisão, piso, teto e resto.
– Instruções de movimentação de dados: carregar, 
armazenar e copiar
– Instruções de controle: desvio condicional, chamada e 
retorno de funções. 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• Custo de cada operação
– Neste momento não é relevante, considera-se 
que cada operação possui custo constante.
Disciplina:ESD-2
que cada operação possui custo constante.
Assim as operações mais significativas dentro de um 
algoritmo é que contribuem para seu tempo de execução
Exemplo: Algoritmos de ordenação
Considera-se: número de comparações entre ao elementos
Desconsidera-se: operação aritméticas , de atribuição e manipulação de índice
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• Se o tempo de execução de um algoritmo
será representado por uma função de custo
T, onde T(n) é a medida do tempo
Disciplina:ESD-2
T, onde T(n) é a medida do tempo
necessário para executar o algoritmo para
um problema de tamanho n.
T é a função complexidade de tempo do algoritmo
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• Se a memória gasta na execução de um
algoritmo será representado por uma
função de custo T, onde T(n) é a medida
Disciplina:ESD-2
função de custo T, onde T(n) é a medida
do espaço necessário para executar o
algoritmo para um problema de tamanho n.
T é a função complexidade de espaço do algoritmo
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmo
• IMPORTANTE:
não representa o valor real da 
Disciplina:ESD-2
T(n) não representa o valor real da 
métrica, mas sim, o número de vezes que 
certa operação relevante é executada. 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• Aplicando o conceito...
Algoritmo:
Encontrar o menor
Disciplina:ESD-2
Encontrar o menor
elemento de um vetor A
de inteiros, com n
elementos
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• Na função calculamenor o T(n) será considerado 
a função de complexidade de tempo para o 
numero de comparações entre os elementos.
Disciplina:ESD-2
numero de comparações entre os elementos.
– Para encontrar o menor elemento temos que 
realizar n-1 comparações.
Logo, T(n) = n-1
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de
• T(n) depende diretamente do tamanho de n, 
no exemplo anterior T(n) é uniforme.
Disciplina:ESD-2
• Nem sempre é assim...
– Existem algoritmos que dependem de outros 
fatores, como os de ordenação.
• Dependência da ordenação inicial.
O mesmo para qualquer tamanho de n.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algotimos
• Considerando um algoritmo de busca:
– Compara-se o elemento buscado com os 
elementos armazenados segundo alguma regra.
Disciplina:ESD-2
elementos armazenados segundo alguma regra.
• Exemplo: 
– A dados armazenados em um array.
– Busca sequencial
T(n) é calculado com n sendo o 
número de consultas de comparação.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de algoritmos
• Busca sequencial em array...
Supondo que todas as entradas são igualmente prováveis
Disciplina:ESD-2
• Pior caso: T(n) = n
• Melhor caso: T(n) =1
• Caso médio: T(n) = ?
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
• Para o caso médio, considere pi a 
probabilidade de procurar o i-ésimo registro.
Disciplina:ESD-2
• T(n) =1.p1+2.p2+3p3+...+ nPn
• Considerando que a probabilidade é a 
mesma para o registro ser encontrado em 
uma das posições. P1=p2=p3=..=pn= 1/n
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de Algoritmos
• T(n)= 1/n * (1+2+3+4%++..+n) (PA)
Disciplina:ESD-2
• T(n) = 1/n * ((n*(n+1))/2)
• T(n) = (n+1)/2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de complexidade
• Para valores pequenos de n, qualquer 
algoritmo, mesmo que ineficiente, gastará 
pouco tempo. 
Disciplina:ESD-2
pouco tempo. 
– A escolha do algoritmo é feito para valores 
grandes de n.
– Estuda-se então o comportamento assintótico 
da função de complexidade.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise de complexidade
• O que analisamos:
A maneira como T(n) aumenta, como ele se 
Disciplina:ESD-2
A maneira como T(n) aumenta, como ele se 
comporta a medida que o tamanho de n aumenta 
indefinidamente.
Isto é, O comportamento assintótico de T(n)
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise Assintótica
Disciplina:ESD-2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Análise assintótica
• Notações assintóticas
– São utilizadas para representar o 
comportamento assintótico as funções de 
Disciplina:ESD-2
comportamento assintótico as funções de 
complexidade
– Relacionar o comportamento das funções de 
complexidades de vários algoritmos 
Pior caso (O), Melhor Caso(Ω) e Caso médio(ʘ)
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Analise de algoritmos
• As notações vistas são definidas em termos 
de funções cujos domínios são o conjunto 
dos números naturais N = {0,1,2,3,4,5...}
Disciplina:ESD-2
dos números naturais N = {0,1,2,3,4,5...}
Antes de começarmos, veremos uma definição
de domínio assintóticoentre funções....
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notação de complexidade
• Notação O (Omicrôn maiúscula)
– Uma função f(n) é O(g(n)) se existem duas 
constantes positivas c e n tais que f(n)<=c. g(n), 
– PIOR CASO
Disciplina:ESD-2
constantes positivas c e n0 tais que f(n)<=c. g(n), 
para todo n>=n0.
– A notação O é utilizada para dar um limite 
assintótico superior(pior caso) sobre uma 
função, dentro de um fator constante.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notação de complexidade
Disciplina:ESD-2
Para todos os valores n à
direita de n0, o valor da
função f(n) está sobe ou em
abaixo de g(n).
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notações de complexidade
• Exemplos:
• F(n)=(1/3)*n2-3n é O(n2), 
– quando c=1/3 e n =1
Disciplina:ESD-2
– quando c=1/3 e n0 =1
• F(n)=(n+1)2 é O(n2), 
– quando c=3 e n0=2.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notações de complexidade
1901ral
1902ral
1902ral
F(n)=(1/3)*n2-3n é O(n2), c=1/3 e n0>1 
Disciplina:ESD-2
1900ral
1900ral
1900ral
1900ral
1901ral
1901ral
1901ral
1901ral
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
f(n)
On2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notações de complexidade
IMPORTANTE
Quando se afirma que o tempo de execução de um algoritmo 
é O(n2), significa que existe uma função f(n) que é O(n2) tal 
Disciplina:ESD-2
é O(n ), significa que existe uma função f(n) que é O(n ) tal 
que, para qualquer valor de n, não importando que entrada 
especifica seja escolhida, o limite superior e determinado pelo 
valor c.n2
Válido para qualquer função, n2 é apenas um exemplo!
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notações de complexidade
• Notação Ω (Ômega maiúscula) 
– Uma função f(n) é Ω(g(n)) se existem duas 
constantes positivas c e n tais que 
– melhor CASO
Disciplina:ESD-2
constantes positivas c e n0 tais que 
c.g(n)<=f(n), para todo n>=n0
– Serve para dar o limite assintótico inferior sobre 
uma função dentro de um fator constante.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notações de complexidade
Disciplina:ESD-2
Para todos os valores n à
direita de n0, o valor da
função f(n) está sobre ou em
cima de g(n).
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notações de complexidade
• Exemplos:
• Seja f(n)=(1/2)n2- 3n é Ω(n2)
– Quando c=1/8, n0 = 8
Disciplina:ESD-2
– Quando c=1/8, n0 = 8
• Seja f(n) = 2n3+3n2+n é Ω(n3)
– Quando c=1 e n0=1
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notações de complexidade
IMPORTANTE
Quando se afirma que o tempo de execução de um algoritmo 
é Ω(n3), significa que existe uma função f(n) que é Ω(n3) tal 
Disciplina:ESD-2
é Ω(n ), significa que existe uma função f(n) que é Ω(n ) tal 
que, para qualquer valor de n, não importando que entrada 
especifica seja escolhida, o limite inferior e determinado pelo 
valor c.n3
Válido para qualquer função, n3 é apenas um exemplo!
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notações de complexidade
• Notação ʘ (Theta maiúscula)
– Uma função f(n) é x(g(n)) se existem constantes 
positivas c1,c2 e n0 tais que 
– CASO MÉDIO
Disciplina:ESD-2
positivas c1,c2 e n0 tais que 
0<=c1.g(n)<=f(n)<=c2.g(n), para todo n>=n0.
– Para todos os valores n a direita de n0, o valor de f(n) 
está acima de c1g(n ) ou abaixo de c2.g(n). São iguais a 
menos de uma constante. 
A notação ʘ é utilizada para dar um limite assintótico firme sobre uma função.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Notação de complexidade
Disciplina:ESD-2
Para todos os valores n à direita de
n0, o valor da função f(n) está sobre
ou acima de c1·g(n) e sobre ou
abaixo de c2·g(n).
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exercícios
Disciplina:ESD-2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exercícios
• Exercícios
Prova: FCC - 2011 - TRT - 19ª Região (AL) - Técnico Judiciário - Tecnologia da Informação
Disciplina:ESD-2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exercício
• Um programador decidiu utilizar, em determinado sistema
de análise estatística, uma árvore AVL como estrutura de
dados. Considerando-se n a quantidade de elementos
dessa árvore, o melhor algoritmo de pesquisa, com base
Disciplina:ESD-2
dessa árvore, o melhor algoritmo de pesquisa, com base
em comparações, possui complexidade de tempo, no pior
caso, igual a:
a) O(1) b) O(log n) 
c) Ω(n) d) Ω(nlogn)
e) Ω(n2)
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exercício
• Uma lista ordenada de N números é inserida em uma pilha 
e depois retirada, sendo que, a cada POP, o elemento 
retirado é inserido em uma árvore de busca binária. Após a 
completa inserção de todos os elementos nesta árvore, são 
Disciplina:ESD-2
completa inserção de todos os elementos nesta árvore, são 
feitas buscas de números na mesma. O tempo no pior caso 
da busca de um número nesta árvore é
a) O(1) b) O(log N)
c) O(N) d) O(Nlog N)
e) O(N2) 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exercício
• Seja n o tamanho da entrada de um algoritmo para um
problema P. Cada alternativa, que corresponde a um
algoritmo distinto, apresenta o número de operações
necessárias para resolver P. Considerando-se a análise
Disciplina:ESD-2
necessárias para resolver P. Considerando-se a análise
assintótica (Big O notation), qual algoritmo possui menor
complexidade?
a) 2 + 10logn b) 3n2+n
c) 1000+ 2n3 d) 5n+128
e) 4n
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exercício
• No desenvolvimento de um sistema de análise 
financeira, um programador utilizou um algoritmo cuja 
complexidade de tempo, no pior caso, é igual a O(n). 
Outro programador aponta um algoritmo de melhor 
Disciplina:ESD-2
Outro programador aponta um algoritmo de melhor 
complexidade igual a
a) O(logn ) b) O(n2 )
c) O(n.logn ) d) O(n!)
e) O(2n)
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exercício
• Observe o código abaixo, que busca o maior elemento de 
um vetor v[0..n -1].
a) O(logn) 
Disciplina:ESD-2
• Qual a complexidade do algoritmo?
a) O(logn) 
b) O(n) 
c) (nlogn) 
d) O(1) 
e) (n2) 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exercício
• Durante a análise de um problema de programação, uma 
analista montou a seguinte fórmula recursiva para 
descrever a solução do problema:
Disciplina:ESD-2
A complexidade da solução encontrada é: 
a) O(n x log n). b) O(n2 x log n). 
c) O(2n). d) O(n2). 
e) O(n3).