Please enable JavaScript.
Coggle requires JavaScript to display documents.
análise de eficiência de algoritmos - Coggle Diagram
análise de eficiência de algoritmos
feita com base no espaço da memória e no tempo de execução
classes de eficiencia
3 notações para comparar a ordem de crescimento
big oh
conjunto de funções com ordem de crescimento menos ou igual a g(n)
big omega
conjunto de funções com ordem de crescimento maior ou igual a g(n)
big theta
conjunto de funções com ordem de crescimento igual a g(n)
um algoritmo de melhor classe de eficiência deve superar um algoritmo de pior classe de eficiência mesmo em entradas moderadas.
unidades para medir o tempo de execução de um algoritmo
T(n) = cp x C(n)
T = tempo de execução,
cp = tempo que certo algoritmo roda no computador usado
C(n) = quantas vezes aquele algoritmo vai rodar
a metrica usada não pode depender do tipo de computador usado ou do compilador.
primeiro identificamos as operações básicas e depois calculamos a quantidade de vezes que essas operações foram executadas.
ordens de crescimento
a menor função de crescimento é a logarítmica
funções exponenciais são recomendadas apenas para entradas muito pequenas
a diferenca de eficiência de algoritmos só fica clara quando o tamanho do input começa a crescer. para pequenos inputs a diferença é quase imperceptível.
A eficiência de pior caso de um algoritmo é sua
eficiência para a entrada de pior caso de tamanho n, que é uma entrada (ou entradas) de tamanho n para a qual o algoritmo executa o mais longo entre todos os possíveis
entradas desse tamanho.
para qualquer caso, a eficiencia temporal não vai exceder o Cworst(n).
calculado considerando o input que haja o maior numero de interações no algoritmo possível
a eficiencia do caso medio procura fornecer informações sobre o comportamento do algoritmo em casos aleatórios
a análise do caso médio de um algoritmo é consideravelmente mais difícil que os melhores casos e piores casos
a eficiencia no melhor caso é calculado pelo input de melhor, ou seja, aquele que dado um input de tamanho n roda da forma mais rapida possível para aquele algoritmo
analise matematica de algoritmos não recursivos
1- decidir um parametro para o tamanho do input
2- identificar as operações básicas a serem executadas
3 - verificar se o número de vezes que as operações básicas são executadas depende apenas do tamanho do input. caso não, o Cworst, Cbest e Caverage precisam ser investigados separadamente
4 - fazer o somatório do número de vezes que as operações básicas são executadas e achar a expressão de eficiencia temporal em função de n