620554_AED (4) - Complexidade de Algoritmos

Prévia do material em texto

1
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos
• Técnicas para Análise de Algoritmos
• Medidas de Tempo de Execução
• Análise do Pior Caso, Caso Médio e Melhor Caso
• Comportamento Assintótico de Funções
• Classes de Comportamento Assintótico
• Considerações Práticas sobre Análise de Algoritmos Recursivos
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Bibliografia
• CORMEN, Thomas H. et al. – Algoritmos: Teoria e Prática
• PREISS, Bruno – Estruturas de dados e algoritmos. Rio de Janeiro: Campus, 2001. 584p.
• SZWARCFITER, Jayme Luiz; MARKENZON, Lilian – Estruturas de dados e seus Algoritmos
• VILLAS, Marcos Vianna; VILLASBOAS, Luiz Felipe P. – Programação – Conceitos, Técnicas e Linguagens.
Rio de Janeiro: Campus, 1988. 196p.
• MCDONALD, Matthew – Begining ASP.NET 4 in C# 2010 – Apress – 2010
• MCMILLAN, Michael – Data Structures and Algorithms Using C# – Cambridge University Press – 2007
• ZIVIANE, Nivio – Projeto de Algoritmos com Implementações em Pascal e C – 2002
• Material de Aula – Algoritmos e Estruturas de Dados – Tiago Braga – 2012
• Material de Aula – Algoritmos e Estruturas de Dados – Camilo Jorge Santos de Oliveira – 2011
2
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
Um algoritmo é fortemente influenciado pelo seu comportamento depois que for implementado em
uma linguagem de programação qualquer.
Um programador deve estudar as diversas opções de algoritmos que podem ser utilizados na solução
de um problema específico, focando sua análise nos aspectos relativos ao Tempo e ao Espaço de
Memória que será utilizado.
Na área da Análise de Algoritmos existem dois tipos de problemas bem distintos:
• Análise de um algoritmo particular, isoladamente, quando se mede o custo para usar um dado
algoritmo na solução de um problema específico. Nesse caso o importante é verificar o número
de vezes que cada parte do algoritmo deve ser executada e da quantidade de memória que será
utilizada;
• Análise de uma Classe de Algoritmos, quando se analisa, dentro de um conjunto de algoritmos,
qual é o que possui menor custo para se resolver o problema apresentado
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
O Custo de Utilização de um algoritmo pode ser medido de duas formas:
• Medição do Tempo de Execução diretamente a partir da execução do programa em um
computador real. No entanto esse tipo de forma de medição é inadequada e os resultados não
podem ser generalizados:
• Os resultados são dependentes do compilador, que pode favorecer algumas construções
em detrimento de outras;
• Os resultados dependem também do hardware e de sua arquitetura;
• Quando grandes quantidades de memória são utilizadas as medidas de tempo podem ser
depender desse aspecto.
• Uso de um Modelo Matemático baseado em um computador idealizado. O conjunto de
operações a serem executadas deve ser especificado, assim como o custo associado com a
execução de cada operação.
3
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
Na análise matemática o número de operações presentes no algoritmo é considerado prioritariamente
e não o tempo de execução de cada uma delas, que é analisado como constante.
Em um algoritmo de busca, por exemplo, considera-se mais importante o número de operações de
comparação entre os elementos do conjunto a ser ordenado, ignorando-se as operações aritméticas,
de atribuição ou de manipulações de índices.
Para medir o custo de execução de um algoritmo é comum a definição de uma função de custo ou
função de complexidade ( ) , que pode ser de Tempo ou de Espaço.
É importante ressaltar que a função de complexidade de tempo não representa diretamente o
tempo gasto, mas o número de veze que uma operação considerada importante é executada.
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
Seja o seguinte programa para se obter o maior elemento dentro de um conjunto de 10 elementos:
static void Main(string[] args)
{
int[] A={13,5,7,12,10,7,21,9,18,11}; // 10 Elementos
int Maior;
Maior=CalculaMaior(A); // Chama a Função...
Console.WriteLine("O Maior Elemento é o {0}\n\n",Maior);
Console.ReadKey();
}
...
4
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
A Função para o Cálculo:
static int CalculaMaior(int[] X)
{
int Temp = X[0]; // Primeiro Elemento;
for (int i = 1; i < 10; i++) // Para todos os elementos
{
if (X[i] > Temp) // Compara...
Temp = X[i]; // Se for o caso, substitui...
}
return Temp; // Retorna o maior elemento
}
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
Como se pode notar, serão necessárias 9 comparações para que o maior valor do conjunto de
elementos seja encontrado.
Generalizando, pode-se dizer que se é uma função de complexidade, e mede o número de
comparações em um conjunto de elementos, = − 1 para > 0.
Assim, nesse caso, o tempo é proporcional à quantidade de elementos.
No entanto nem sempre é assim. Muitas vezes o tempo varia segundo as condições dos dados de
entrada. Por exemplo, em algoritmos de ordenação, quanto mais organizado já estiver o vetor, menos
tempo de operação será necessário.
Isso significa que é importante a identificação de três cenários:
• Melhor Caso;
• Pior Caso;
• Caso Médio;
5
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
O Melhor Caso e o Pior Caso correspondem, respectivamente, ao menor e ao maior tempo de
execução sobre todas as possíveis entradas de tamanho .
O Caso Médio, também chamado de Caso Esperado, corresponde à média dos tempos de execução de
todas as entradas de tamanho . Nessa análise o custo médio é obtido com base em uma distribuição
de probabilidades, razão pela qual ela tende a ser mais difícil e envolver fundamentos matemáticos
mais profundos.
Por exemplo, seja uma função de complexidade tal que corresponda ao número de registros
consultados em um arquivo texto sequencial:
João
Pedro
Carla
Ana
Joaquim
Pedro
Paula
Qual o Melhor Caso, Pior Caso e Caso
Médio para essa análise?
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
João
Pedro
Carla
Ana
Joaquim
Pedro
Paula
O Melhor Caso ocorre quando o registro procurado é o
primeiro, como é o caso do João. O Pior Caso é ser o
último da consulta, que é o caso da Paula. Assim,
Melhor Caso: = 1
Pior Caso: = 
6
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Complexidade de Algoritmos – Introdução
Para o Caso Médio, é necessário considerar que toda pesquisa sempre recupera um registro. Se for
a probabilidade de que o i − é registro seja procurado e considerando que para se recuperar
esse registro são necessárias comparações, tem-se: = 1 + 2 + 3 + ⋯+ 
Para se calcular basta, então, conhecer a distribuição de probabilidades . Se cada registro tivera mesma probabilidade de ser acessado que todos os outros, então, = . Nesse caso,
 = 1 1 + 2 + 3 + ⋯+ = 1 + 12 = + 12
Caso Esperado ou Caso Médio
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Comportamento Assintótico de Funções
Como se observou, o custo para se obter uma solução para um problema aumenta com o tamanho 
do problema. O parâmetro fornece uma medida da dificuldade para se resolver o problema, no
sentido de que o tempo necessário para isso cresce quando cresce.
Para valores pequenos de qualquer algoritmo custa pouco, até mesmo os mais ineficientes. O
problema é maior e pode se tornar crítico para valores de maiores. Por isso passa a ser importante o
estudo do comportamento assintótico das funções de custo. O comportamento assintótico de ( )
representa o limite do comportamento do custo quando cresce.
7
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Comportamento Assintótico de Funções
Definição:
Uma função ( ) domina assintoticamente outra função se existem duas constantes positivas 
e tais que, para ≥ temos ≤ . | ( )|
 ( ) e 
 . ( )
 
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Comportamento Assintótico de Funções
Exemplo – Seja = = − ≤ | − | para todo pertencente ao conjunto dos números naturais. Logo, domina
assintoticamente . , no entanto, não domina assintoticamente , porque − > | | para todo > e > 1
qualquer que seja o valor de .
Exemplo – Seja = ( + 1) = ( + 1) ≤ 4| | para todo ≥ 1 e < |( + 1) | para > 0. Isso significa que e 
dominam assintoticamente uma a outra.
8
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Comportamento Assintótico de Funções – Notação O (Ômicron)
Knuth sugeriu uma notação para a dominação assintótica. Por exemplo, para se expressar que ( )
domina assintoticamente escreve-se: = ( )
Onde se lê: é da ordem de no máximo ( )
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Comportamento Assintótico de Funções – NotaçãoΩ (Ômega) e θ (Theta)
A notação = ( ) tem um significado como ≤ .
De maneira análoga, a notação Ω (Ômega) pode ser usada para expressar ≥ : = Ω( ) 
A notação θ (Theta) expressa = : = θ( )
9
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Comportamento Assintótico de Funções – Operações com a Notação O
Um programa pode possuir trechos específicos com diferentes graus de complexidade. Para isso
algumas operações com a Notação O podem ser úteis:
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Comportamento Assintótico de Funções – Operações com a Notação O
Exemplo:
Suponha três trechos de um algoritmo cujos tempos de execução são , e log .
Qual a complexidade do algoritmo como um todo?
Para os dois primeiros trechos, conforme a regra da soma: max ( , ) = .
Incluindo o terceiro trecho, também seguindo a regra da soma: (max ( , log )) = ( ).
O Algoritmo, portanto, possui complexidade ( ).
10
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Se é uma Função de Complexidade para um dado algoritmo, então ( ) é considerada a
Complexidade Assintótica (ou comportamento assintótico) desse algoritmo.
A relação de dominação assintótica permite comparar funções de complexidade. Se uma função e
outra dominam assintoticamente uma a outra, então os algoritmos associados são equivalentes em
termos de suas complexidades.
Nesses casos, o comportamento assintótico não serve para comparar os algoritmos.
Considerando, por exemplo, dois algoritmos, A e B, aplicados à mesma classe de problemas. Sabe-se
que A leva 3 vezes o tempo de B ao serem executados em um computador, ou seja = 3 ( ) ,
sendo que = ( ).
O comportamento assintótico não serve para comparar os algoritmos A e B porque eles se diferem
apenas por uma constante.
Isso é importante?
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Seja, por exemplo, um programa que leva 100 seg para ser executado, e outro que leva 2 seg.
Qual dos dois programas é melhor?
Depende do tamanho do problema...
Para < 50 o programa com tempo 2 é melhor, ou seja, para problemas com entrada de dados
pequena é preferível usar o programa com tempo de execução .
Quando cresce, no entanto, o programa com tempo leva mais tempo que o .
11
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Principais Classes de Problemas:
 = (1)
• Algoritmos com complexidade (1) são ditos de Complexidade Constante;
• O uso do algoritmo independe de n;
• As instruções do algoritmo são executadas um número fixo de vezes.
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Principais Classes de Problemas:
 = (log )
• Um Algoritmo com complexidade (log ) é dito ter Complexidade Logarítmica;
• São típicos em algoritmos que transformam um problema em outros menores;
• Quando é 1.000, log = 10. Quando é 1.000.000,log = 20, ou seja, para se dobrar o
valor de log é necessário dobrar o valor de .
12
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Principais Classes de Problemas:
 = ( )
• Um Algoritmo com complexidade ( ) é dito ter Complexidade Linear;
• Em geral um pequeno trabalho é realizado sobre cada elemento de entrada;
• É a melhor situação possível para um algoritmo que precisa processar e produzir uma
quantidade de elementos de saída;
• Cada vez que dobra de tamanho o tempo de execução também dobra.
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Principais Classes de Problemas:
 = ( log )
• Ocorre tipicamente em algoritmos que quebram um problema em outros menores e resolvem
cada um deles de forma independente, juntando as soluções ao final;
• Quando é 1.000.000, log é de cerca de 20.000.000. Quando é 2.000.000, log é
de cerca de 42.000.000.
13
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Principais Classes de Problemas:
 = ( )
• Um Algoritmo com complexidade ( ) é dito ter Complexidade Quadrática;
• Ocorrem quando os itens de dados são processados aos pares, muitas vezes em um anel dentro
de outro (estruturas de repetição);
• Quando é 1.000 o número de operações é da ordem de 1.000.000. Sempre que dobra o
tempo de execução é multiplicado por 4;
• Algoritmos com essa complexidade são úteis para resolver problemas de tamanho
relativamente pequeno.
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Principais Classes de Problemas:= ( )
• Um Algoritmo com complexidade ( ) é dito ter Complexidade Cúbica;
• Servem para resolver problemas de tamanho pequeno;
• Quando é 100 o número de operações é da ordem de 1.000.000;
• Quando dobra o tempo de execução fica multiplicado por 8.
14
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Principais Classes de Problemas:
 = (2 )
• Um Algoritmo com complexidade (2 ) é dito ter Complexidade Exponencial;
• Normalmente não são úteis sob o ponto de vista prático;
• Ocorrem na solução de problemas quando se usa “força bruta” para resolvê-los
• Quando é 20 o tempo de execução é próximo a 1.000.000. Se dobra o tempo fica elevado
ao quadrado.
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Complexidade de Algoritmos
Classes de Comportamento Assintótico
Comparações: