Please enable JavaScript.

Coggle requires JavaScript to display documents.

Empirical Analysis of Algorithms :check: - Coggle Diagram

- - - - 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.
- - - - 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
        
        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
      - -achar uma formula fechada de contagem ou estabelecer uma ordem de crescimento
  - - - 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
- - - - 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 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.