Análise Assintótica

Análise Assintótica

1. Análise Assintótica Marcos Castro

2. Análise Assintótica A análise de algoritmos ignora valores pequenos e concentra-se nos valores enormes de n . f (n) = n + 10 Para valores pequenos de n, qualquer algoritmo custa pouco para ser executado, até mesmo os algoritmos ineficientes. Matematicamente falando, a análise assintótica é o método de descrever o comportamento dos limites. É desejável exprimir o consumo de tempo de um algoritmo de forma que não dependa da linguagem de programação. 2

3. Análise Assintótica Por exemplo, numa pesquisa sequencial, o número de vezes que a chave de consulta é comparada com a chave de cada registro: Pior caso: f(n) = n Caso médio: f(n) = (n + 1) / 2 Melhor caso: f(n) = 1 3

4. Análise Assintótica O melhor caso corresponde ao menor tempo de execução sobre todas as possíveis entradas de tamanho n. O pior caso corresponde ao maior tempo de execução sobre todas as entradas de tamanho n. O caso médio corresponde à média dos tempos de execução de todas as entradas de tamanho n. É suposta uma distribuição de probabilidades sobre o conjunto de tamanho n. 4

5. Análise Assintótica A notação “ Grande-O ” representa a complexidade no pior caso. É a mais utilizada, pois para vários algoritmos o pior caso ocorre com frequência. Outros tipos de notações que tratam outros casos: Notação theta (limite assintótico firme) Notação ômega (limite assintótico inferior, análise de melhor caso) 5

6. Análise Assintótica Notações: 6

7. Contato [email protected] www.geeksbr.com www.twitter.com/mcastrosouza www.github.com/marcoscastro 7