Aula 4- Complexidade Algoritmica (1) PDF

UNIVERSIDADE S. TOMÁS DE MOÇAMBIQUE CURSO DE TECNOLOGIAS DE SISTEMAS DE INFORMAÇÃO Estrutura de Dados e Algoritmos Ano 2007 Aula 11: Complexidade Algorítmica Conteúdo 1. Conceito...

UNIVERSIDADE S. TOMÁS DE MOÇAMBIQUE CURSO DE TECNOLOGIAS DE SISTEMAS DE INFORMAÇÃO Estrutura de Dados e Algoritmos Ano 2007 Aula 11: Complexidade Algorítmica Conteúdo 1. Conceito de Complexidade Algorítmica 1. 1 Avaliação de Algoritmos 2. Notações O-Grande, Omega e Theta 2.1 Notação O-Grande 2.2 Notação Ómega 2.3 Notação Theta 3. Crescimento Assimptótico de Funções 3. 1 Principais Classes de Complexidade 3. 2 Análise da Complexidade de Algoritmos 3. 3 Regras para a Análise de Algoritmos 4. Exercícios práticos 1 1. Conceito de Complexidade Algorítmica Diferentes algoritmos podem ser construídos para resolver um determinado problema. Esses algoritmos podem variar na forma de buscar os dados de entrada, processar e imprimir os dados de saída. Assim sendo, estes podem ter diferenças significativas em termos de performance e utilização de espaço. Entender como analisar algoritmos e como medir a eficiência algorítmica ajuda bastante na escolha do melhor algoritmo a ser usado (melhor optimizado). No entanto, para desenvolver algoritmos realmente eficientes, não basta conhecer técnicas e alternativas para problemas comuns. O programador deve ter a capacidade de prever, ao desenvolver um algoritmo, qual será o seu comportamento, quer com poucos ou com muitos dados de entrada. A tentativa de prever o comportamento do algoritmo consiste em avaliar sua complexidade. Para isso, são feitos cálculos, que podem ser simples ou complexos. Neste contexto teremos como objectivos para análise de algoritmos:  Avaliar um algoritmo para verificar se ele é eficiente ou não,  Verificar se um algoritmo é correcto ou incorrecto,  Comparar vários algoritmos (que resolvem o mesmo problema) para decidir qual deles é o mais eficiente. Exemplo: Suponhamos que nos seja colocado um problema para encontrar o maior e o menor elemento dum array com n elementos, e, que tenhamos como dado de entrada o referido array. Resolução: Primeiro é necessário determinar as instâncias de execução do algoritmo. Neste caso teremos: 2 Instâncias de Execução de Algoritmos: Uma instância de um problema consiste de um conjunto de dados de entrada e saída utilizados durante uma única execução. Por exemplo, abaixo temos duas diferentes instâncias de execução do mesmo algoritmo, cujo problema foi especificado acima. Problema: Encontrar o maior e o menor valor de um vector com n elementos. Entrada: {1,34,56,32,3,54,3,356,3,2,23,78,65,32,11,1,43,356,66} Saída: Menor valor = 1 Maior valor = 356 Problema: Encontrar o maior e o menor valor de um vector com n elementos. Entrada: {2,54,67,93,54,23,345,67,42,447,4,983,10,76,31,15,57,83,45,794,346,44} Saída: Menor valor = 2 Maior valor = 983 A partir do exemplo acima, podemos verificar que em diferentes instâncias de execução, os dados de entrada podem ser bastante variados, podendo inclusive ter uma grande variação de volume. Ou seja, na instância apresentada no primeiro quadro o array de entrada tem 19 valores, enquanto na instância apresentada no segundo quadro o array de entrada tem 22. Da mesma forma, numa outra instância é possível que se tenha 500 elementos de entrada. A questão que se levanta então é: dado um algoritmo que funciona de forma eficiente para 10 elementos, ele continuará funcionando de forma eficiente para 10.000 ou mais? O algoritmo deve trabalhar correctamente sobre todas as instâncias para as quais foi projectado para solver. Portanto, um algoritmo para o qual é possível achar uma instância de dados de entrada para a qual ele não consegue achar uma resposta correcta é um algoritmo incorrecto. No entanto, provar o contrário, que o algoritmo é correcto para qualquer instância, não é tão simples. Para isso, o algoritmo deve ser avaliado utilizando alguns critérios. 3 Deste modo, passaremos a ilustrar a avaliação do algoritmo. 1.1 Avaliação de Algoritmos Algoritmos podem ser avaliados utilizando-se vários critérios. Geralmente o que interessa é a taxa de crescimento ou espaço necessário para resolver instâncias cada vez maiores de um problema. Podemos associar um problema a um valor chamado de ‘tamanho’ do problema, que mede a quantidade de dados de entrada. O tempo que um algoritmo necessita, expresso como uma função do tamanho do problema, é chamado de complexidade temporal do algoritmo. O comportamento assimptótico dos algoritmos (ou funções) representa o limite do comportamento de custo quando o tamanho cresce. O comportamento assimptótico pode ser definido como o comportamento de um algoritmo para grandes volumes de dados de entrada. A complexidade temporal de um algoritmo pode ser dividida em 3 aspectos:  Melhor caso – o melhor caso representa uma instância que faz o algoritmo executar utilizando o menor tempo possível.  Pior caso – o maior tempo demorado pelo algoritmo para executar alguma instância.  Caso médio – a média de tempo que o algoritmo demora para executar. Geralmente, o mais importante é avaliar o pior caso (porque pode inviabilizar o algoritmo) e o caso médio, porque representa como o programa vai se comportar, na prática, na maioria dos casos. Tipos de Avaliação de Algoritmos A avaliação de algoritmos divide-se em dois tipos a saber:  Avaliação Empírica: é a forma mais simples de se avaliar um algoritmo e consiste implementá-lo num computador e executá-lo com várias instâncias do problema. Define-se então um critério para a eficiência, como por exemplo o tempo gasto para 4  execução. Com base na observação, pode-se calcular o pior caso (a instância de execução que levou mais tempo), o melhor caso (a instância de execução que gastou menos tempo) e o caso médio (a média do tempo gasto em todas as instâncias de execução). O problema com esse tipo de avaliação é que o tempo gasto vai depender do computador utilizado, do compilador, da linguagem de programação, etc.  Avaliação Teórica: é aquela em que consiste em encontrar uma fórmula matemática que expresse o recurso, por exemplo o tempo necessário para o algoritmo executar em função do tamanho dos dados de entrada. Existem algumas notações predefinidas usadas para comparar diferentes funções: 2 Notações O-grande, Omega e Theta Após obter a função que representa o comportamento de um software, basta analisá-la para termos uma medida da complexidade do software. Para isso utiliza-se as 3 notações a seguir: O-grande, Omega e Theta. Elas são utilizadas também para comparar funções de diferentes algoritmos. 2.1 Notação O-Grande Esta notação é utilizada para analisar o Caso Pior. Uma função f(n) é O(g(n)) se  c>0 e n0 tais que f(n) =n0. Explicação: uma função f(n) é da ordem de complexidade de g(n) e escreve-se f(n) = O(g(n)) se existe uma constante c e um valor n0 tal que para qualquer valor de n maior do que n0 f(n) é menor ou igual a c*g(n). Isso significa que:  g(n) é um limite superior para f(n)  f(n) denomina assimptoticamente f(n) 5 Propriedades:  f(n) = O(f(n))  c. f(n) = O(f(n)), c=constante  O(O(f(n))) = O(f(n))  O(f(n)) + O(g(n)) = O(max(f(n),g(n))  O(f(n)) * O(g(n)) = O (f(n) * g(n)) 2.2 Notação Omega Esta notação é utilizada para analisar o melhor caso. Uma função f(n) é (g(n)) se  c>0 e n0 tais que f(n) >= c*g(n) para n>=n0. Explicação: uma função f(n) é da ordem de complexidade de g(n) e escreve-se f(n) = (g(n)) se existe uma constante c e um valor n0 tal que qualquer valor de n maior do que n0, f(n) é maior ou igual a c*g(n). Isso significa que:  g(n) é um limite inferior para f(n) 2.3 Notação Theta Esta notação é utilizada para analisar o caso médio. Uma função f(n) é (g(n)) se  c1, c2 e n0 tais que c1. g(n)