Complexidade algoritmo

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2490 palavras )
  • Download(s) : 0
  • Publicado : 7 de abril de 2013
Ler documento completo
Amostra do texto
Complexidade de Algoritmos
Siang Wun Song - Universidade de São Paulo - IME/USP

MAC 5710 - Estruturas de Dados - 2008

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Objetivo de estudar complexidade de algoritmos

Por que analisar a complexidade dos algoritmos? A preocupação com a complexidade de algoritmos é fundamental para projetar algoritmoseficientes. Podemos desenvolver um algoritmo e depois analisar a sua complexidade para verificar a sua eficiência. Mas o melhor ainda é ter a preocupação de projetar algoritmos eficientes desde a sua concepção.

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Eficiência ou complexidade de algoritmos

Para um dado problema considere dois algoritmos que o resolvem.Seja n um parâmetro que caracteriza o tamanho da entrada do algoritmo. Por exemplo, ordenar n números ou multiplcar duas matrizes quadradas n × n (cada uma com n2 elementos). Como podemos comparar os dois algoritmos para escolher o melhor?

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Complexidade de tempo ou de espaço

Precisamos definir alguma medidaque expresse a eficiência. Costuma-se medir um algoritmo em termos de tempo de execução ou o espaço (ou memória) usado.
Para o tempo, podemos considerar o tempo absoluto (em minutos, segundos, etc.). Medir o tempo absoluto não é interessante por depender da máquina. Em Análise de Algoritmos conta-se o número de operações consideradas relevantes realizadas pelo algoritmo e expressa-se esse númerocomo uma função de n. Essas operações podem ser comparações, operações aritméticas, movimento de dados, etc.

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Pior caso, melhor caso, caso médio
O número de operações realizadas por um determinado algoritmo pode depender da particular instância da entrada. Em geral interessa-nos o pior caso, i.e., o maiornúmero de operações usadas para qualquer entrada de tamanho n. Análises também podem ser feitas para o melhor caso e o caso médio. Neste último, supõe-se conhecida uma certa distribuição da entrada. Exemplo: Busca seqüencial de um dado elemento em um vetor armazenando n elementos de forma aleatória. Discuta o pior caso, melhor caso e o caso médio. No caso médio suponha a distribuição uniforme e que odado buscado está dentro do vetor. Como muda o caso médio se o dado em geral não está presente?

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Complexidade de tempo

Como exemplo, considere o número de operações de cada um dos dois algoritmos que resolvem o mesmo problema, como função de n. Algoritmo 1: f1 (n) = 2n2 + 5n operações Algoritmo 2: f2 (n) =500n + 4000 operações Dependendo do valor de n, o Algoritmo 1 pode requerer mais ou menos operações que o Algoritmo 2. (Compare as duas funções para n = 10 e n = 100.)

Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Comportamento assintótico

Algoritmo 1: f1 (n) = 2n2 + 5n operações Algoritmo 2: f2 (n) = 500n + 4000 operações Um caso de particularinteresse é quando n tem valor muito grande (n → ∞), denominado comportamento assintótico. Os termos inferiores e as constantes multiplicativas contribuem pouco na comparação e podem ser descartados. O importante é observar que f1 (n) cresce com n2 ao passo que f2 (n) cresce com n. Um crescimento quadrático é considerado pior que um crescimento linear. Assim, vamos preferir o Algoritmo 2 ao Algoritmo 1.Siang Wun Song - Universidade de São Paulo - IME/USP

Complexidade de Algoritmos

Notação O
Dada uma função g(n), denotamos por O(g(n)) o conjunto das funções
{ f (n) : ∃ constantes c e n0 tais que 0 ≤ f (n) ≤ cg(n) para n ≥ n0 .}

Isto é, para valores de n suficientemente grandes, f (n) é igual ou menor que g(n). Como abuso de notação, vamos escrever f (n) = O(g(n)) ao invés de f...
tracking img