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.

image

image

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.