Crescimento de funções- Análise de Algorítimos

Crescimento de funções

As expressões produzidas pela análise matemática da eficiência de um algoritmo geralmente são baseadas em funções matemáticas bem conhecidas. Uma das vantagens de associar a eficiência de um algoritmo a essas funções é que fica mais fácil entender como seu custo varia em relação ao tamanho do parâmetro primário do algoritmo. Outra vantagem é que isso nos permite comparar os custos de diferentes algoritmos com facilidade. 




A seguir, você poderá ver as funções matemáticas normalmente utilizadas na análise matemática do custo:

A Figura 1 (abaixo) mostra um gráfico onde você pode analisar como as curvas de crescimento correspondentes a essas funções se comportam à medida que aumentamos o tamanho do parâmetro primário do algoritmo. 

Neste gráfico, a curva da função de custo é rotulada como , antecipando a notação que você conhecerá daqui a pouco, ainda nesta aula. Para a maioria dessas funções, quanto maior for o tamanho do parâmetro primário N, maior será o custo computacional do algoritmo. 

Dessa forma, você poder ver, por exemplo, que se um algoritmo tem sua expressão de custo correspondente a uma função constante, então, ele consome sempre o mesmo tempo, independente do valor de N. Por outro lado, se o algoritmo tem uma expressão de custo exponencial, um pequeno aumento no tamanho de N tem grande impacto no tempo consumido pelo algoritmo.

Figura 1: Funções de Custo Tradiconais

O custo de um algoritmo normalmente é descrito por uma expressão formada por alguma dessas funções multiplicada por uma constante. Esta expressão corresponde à operação dominante, obtida após desconsiderar outros termos de menor importância, que correspondem a operações de menor impacto no custo do algoritmo. Por exemplo, a expressão poderia ser utilizada para denotar o custo de um algoritmo, onde N seria o parâmetro primário e seriam as constantes multiplicativas que representam tempos de execução de operações elementares. 

Dada a expressão de custo de um algoritmo, o termo de maior importância para a determinação do custo corresponde à operação dominante, geralmente relacionada ao número de comandos da instrução de repetição mais interna do algoritmo. Normalmente, representamos o custo do algoritmo de forma simplificada, considerando apenas o termo de maior importância na expressão de custo global. Assim, a expressão de custo anterior poderia ser simplificada para , que é o termo que mais influencia no custo à media que o tamanho do parâmetro primário aumenta.

As constantes de uma expressão de custo representam os tempos de execução de operações elementares (atribuição, leitura e escrita simples etc.). Esses tempos normalmente não podem ser determinados apenas pela observação do algoritmo, pois vão depender do ambiente de execução (velocidade do processador, velocidade de acesso memória do computador etc.).

Fonte: ( Site metropoledigital)

BONS ESTUDOS!!!