Empirical Analysis of Algorithms ✅
Analisar a eficiência de um algoritmo é, em suma, um processo empírico, visto a complexidade de descrevê-lo matematicamente.
Para isso, seguimos alguns processos:
1.Entender o propósito do experimento.
2.Decidir as características do input.
3.Definir a eficiência do sistema de medida.
4.Prepare um programa implementando o algoritmo.
5.Gere alguns inputs.
6.Teste o input e registre os resultados.
7.Analise os dados obtidos.
Em suma, o propósito do algoritmo dita como ele deve ser medido. Geralmente contadores são implementados no código para registrar 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.
Muitas vezes, são gerados pseudonúmeros para testar o algoritmo, sendo estes gerados a partir de funções já presentes nas linguagens de programação, dentre eles o método linear congruente.
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 sucinta dos dados.
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 através de uma série de imagens, já dinâmicos, como o nome diz, se dá por várias animações demonstrando o procedimento.
Além do propósito educativo das imagens, elas também ajudam a descobrir funcionalidades ainda desconhecidas dos algoritmos
Há dois tipos de eficiência de algoritmo, a eficiência temporal, que lida com a rapidez com que o programa funciona, e a eficiência espacial, que lida com o espaço extra que é requerido do computador.
As notações Ω, O e Θ são utilizadas para comparar os índices de grandeza que representam os crescimentos das funções de eficiência dos algoritmos.
Análise Matemática de Algoritmos Não Recursivos ✏
Exemplo 1
- para achar o maior valor do array: precisamos do numero de elementos
- for loop (mais utilizado) : 2 operações - comparação (A[i] > maxValor) que eh a operação basica e atribuicao (maxValor = A[i])
- num de comparacoes sempre igual p n arrays
- o num de comparacoes = somatorio de 1 ate n -1
Plano para analisar a eficiência de algoritmos não recursivos:
- decidir o parametro para o tamanho da entrada (n)
-identificar a operacao basica
-se o num de vezes q ela eh realizada nao depender so de n, investigar o melhor e pior caso separadamente
-configurar o somatorio da operacao basica
-achar uma formula fechada de contagem ou estabelecer uma ordem de crescimento
(REGRAS DE MANIPULACAO DE SOMA)
Exemplo 2
-temos que checar se ha algum elemento repetido
-operacao basica eh a comparacao entre dois elementos
-o num de comparacoes depende se existem elementos iguais no array e, se sim, qual a suas posicoes
-os dois piores casos sao: arrays que nao tem elementos repetidos e arrays em que os 2 ultimos elementos sao o unico par de elementos iguais
- nesses casos, 1 comparacao eh feita para cada repeticao do loop mais interno
-portanto, no pior caso o algoritmo compara os n(n-1)/2 pares distintos de n elementos
Exemplo 3
-multiplicacao de matrizes
-usamos 2 matrizes n x n A e B para achar o seu produto C
-operacoes de multiplicação e adicao sao feitas uma vez em cada repeticao do loop mais interno
-multiplicacao eh considerada a operacao basica
-montamos a soma do num total de multiplicacoes
-o num de multiplicacoes pra cada par é o representado por um somatorio k que vai de 0 ate n - 1 (S1)
- o num total de multiplicacoes é uma soma tripla de S1
Exemplo 4
acha o numero de dígitos binarios na representação binaria de um decimal inteiro positivo
a operação mais frequente nao eh dentro do while mas na comparacao n > 1 que determina quando o laço sera executado
a variavel do laco assume apenas alguns valores entre o maior e menos limite, entao usamos um meio alternativo de computar seu numero de execuções
o numero exato de comparacoe n > 1 seria log2 n + 1
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.
É lógico investigar a eficiência do algoritmo como uma função de um parâmetro n, que indica o tamanho do input.
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.
A ordem é importante pois geralmente apenas os inputs de grande tamanho irão 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).
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 úteis em certos algoritmos.
A eficiência do caso médio não é necessariamente a média do pior e do melhor, e por isso se torna importante para legitimar algoritmos que têm uma eficiência muito melhor no caso médio que na pior hipótese dos casos.