Please enable JavaScript.
Coggle requires JavaScript to display documents.
ANÁLISE DA EFICIÊNCIA DE ALGORITMOS, ANÁLISE EMPÍRICA DE ALGORITMOS,…
ANÁLISE DA EFICIÊNCIA DE ALGORITMOS
investigação da eficiência de um algoritmo a respeito de duas fontes: tempo de execução e espaço de memória.
A ANÁLISE FRAMEWORK
primariamente o foco está concentrado na eficiência do tempo, porém o framework analítico introduzido também é aplicável para analizar a eficiência no espaço.
MEDINDO O TAMANHO DO INPUT
é lógico investigar a eficiência do algoritmo como uma função de um parâmetro n, que indica o tamanho do input.
UNIDADES PARA MEDIR O TEMPO DE EXECUÇÃO
apenas medir o tempo de execução de um algoritmo pode ser complicado, pois é preciso levar em consideração a velocidade do computador/ compilador utilizado, a qualidade do programa que o algoritmo está implementado, além de outros fatores.
por isso, uma abordagem eficiente é identificar a chamada OPERAÇÃO BÁSICA, que é a operação que mais contribui para o tempo de execução, e computar a quantidade de vezes que essa operação é realizada.
ORDEM DE CRESCIMENTO
é importante pois geralmente apenas os inputs de grande tamanho irão afetar na eficiência do algoritmo
afetar na eficiência do algoritmo
a função que cresce mais devagar é a logarítmica, enquanto a exponencial cresce rapidamente para números astronomicamente grandes (são melhores para resolver problemas pequenos).
PIOR CASO, MELHOR CASO E CASO MEDIO EM EFICIÊNCIA
a eficiência do pior caso é uma informação importante para determinar o tempo de execução que tal algoritmo não irá ultrapassar
a eficiência do melhor caso não é tão primordial como a do pior caso, porém é possível tirar vantagem dessa informação para alguns tipos de inputs uteis em certos algoritmo.
a eficiência do caso médio não é necessariamente a media do pior e do melhor, e por isso se torna importante para legitimar algoritmos que tem uma eficiência muito melhor no caso médio que na pior hipótese dos casos.
ANÁLISE EMPÍRICA DE ALGORITMOS
Outra forma de analisar algoritmos é através de imagens com informações importantes, podendo ser estáticas ou dinâmicas, também chamadas de algorithm animation.
Algoritmos estáticos mostram o processo por meio de uma série de imagens, já dinâmicos acontece por várias animações demonstrando o procedimento.
(as imagens também ajudam a descobrir novas funcionalidades nos algoritmos).
Analisar a eficiência de um algoritmo é um processo empírico, graças à complexidade de descrevê-lo matematicamente. Seguem alguns processos:
1.Entender o objetivo do experimento.
2.Decidir as características do input.
3.Definir a eficiência do sistema de medida.
4.Fazer um programa que implemente o algoritmo.
5.Gerar alguns inputs.
6.Testar os inputs e registrar os resultados.
7.Analisar os dados registrados.
Portanto, o propósito do algoritmo dita como ele deve ser medido. Geralmente contadores são implementados no código para anotar a quantidade de vezes que o processo é repetido.
Além da ideia dos contadores, as vezes registra-se o tempo para executar uma ação como fator decisivo para a eficiência de um algoritmo.
Durante esses experimentos, obtemos dados muito importantes em pontos específicos do código, podendo apontar possíveis 'bottlenecks' e pontos que podem ser melhoradas, sendo esse processo chamado de profiling.
Os dados obtidos no experimento precisam ser registrados graficamente num 'scatterplot' por meio de pontos num plano cartesiano, a fim de obter uma análise eficiente dos dados.
ANÁLISE MATEMÁTICA DE ALGORITMOS NÃO RECURSIVOS
EXEMPLO 1:
precisamos do numero de elementos para achar o maior valor do array
plano para analisar a eficiencia de algoritmos nao recursivos:
identificar a operação básica e o n de entrada, configurar o somatório de entrada para achar a ordem de entrada ou estabelecer uma ordem de crescimento.
EXEMPLO 2:
checagem se há um elemento repetido
operação básica será a comparação entre dois elementos,
EXEMPLO 3:
em uma multiplicação de matrizes, achar o numero total de multiplicadores.
EXEMPLO 4:
acha o numero de dígitos binarios na representação binaria de um decimal inteiro positivo
o numero exato de comparações está em crescimento logarítmico.
NOTAÇÕES ASSINTÓTICAS E CLASSES BÁSICAS DE EFICIÊNCIA
para comparar e rankear as ordens de crescimento são usadas tês notações: O (big oh), (big omega), and (big theta).
usando a definição formal de notações assindéticas, é possível provar suas propriedades gerais, que são uteis na análise de algoritmos que compreendem duas partes executadas consecutivamente.