Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 4 - Coggle Diagram

- - - - 1º- Entender o algoritmo e decidir o propósito da análise
      - 2º- Decidir uma unidade de medida para os resultados dos testes (número de operações básicas ou medidas de tempo)
      - 3º- Definir as características para os inputs utilizados como amostra para o teste (tamanho, magnitude, etc.)
      - 4º- Preparar um programa para executar o(s) algoritmo(s)
      - 5º- Gerar os inputs gerados pseudo-randomicamente para servirem de amostra
      - 6º- Rodar o(s) algoritmo(s) com a amostra gerada e observar os resultados
      - 7º- Analisar os dados obtidos
    - - Pros: Este tipo de análise é útil por mostrar mais claramente informações específicas sobre um algoritmo, executado em um computador específico, do que pelo uso das funções assintóticas
      - Contras: Pelo algoritmo ser executado em um computador específico, fatores externos, como a qualidade dos componentes deste computador, atrapalham na generalização dos dados obtidos. Além de que os resultados podem variar bastante a depender da amostra utilizada
- - - - Se refere à quantidade de unidades de memória utilizadas pelo(s) input(s), output(s) e pelo algoritmo em si. Porém, pela grande quantidade de memória que computadores de hoje em dia possuem, é normal se analisar somente o espaço consumido pelos inputs e variáveis no geral
      - O espaço total exigido por input, ao longo de um algoritmo, deve ser medido na forma de uma função com um parâmetro n, que indica o tamanho original do input dado. Porém, n não possui uma unidade de medida universal, ela irá depender do algoritmo:
        
        Em uma Sequential Search, o parâmetro n vai ser a quantidade de elementos da array
        
        Já em um teste de primalidade, o parâmetro n vai ser a magnitude do número inteiro
    - - Se refere ao quão rápido um algoritmo é
      - Unidade de medida
        
        Geralmente não é medida em nenhuma unidade de tempo, pois fatores externos comprometem a medição da eficiência do algoritmo em si
        
        Para se estimar em unidades de tempo, como segundos, deve-se usar o tempo de execução da operação básica em um computador específico e multiplicá-lo por C(n)
        
        A eficiência é medida por uma função C(n), que é o número de repetições da operação básica do algoritmo a partir de um input de tamanho n. Uma operação básica é a operação que mais irá contribuir para o total de tempo gasto pelo algoritmo em uma repetição
      - Ordens de crescimento
        
        Classificação da função C(n) de um algoritmo que mostra o quanto o resultado cresce a medida que n (o tamanho do input) cresce. Quanto mais rápido C(n) cresce, mais devagar o algoritmo vai ser para inputs de n grandes
        
        Tipos principais:
        
        Logarítmica (a que cresce mais lentamente)
        
        Linear (2ª que cresce mais lentamente)
        
        Exponencial 2^n (2ª que cresce mais rapidamente)
        
        Fatorial (a que cresce mais rapidamente)
      - Eficiência de casos
        
        Tipos de casos:
        
        Melhor Caso: O melhor caso é a ocasião em que o algoritmo é executado com o menor C(n) possível
        
        Pior Caso: O pior caso é a ocasião em que o algoritmo é executado com o maior C(n) possível
        
        Caso médio: O mais importante na comparação para a escolha do algoritmo, o caso médio é uma estimativa para o valor que C(n) normalmente irá apresentar
        
        Apesar da ordem de crescimento e da própria função C(n) ajudar na eficiência de tempo do algoritmo, é importante também ver o quanto a eficiência do algoritmo varia dependendo do input recebido
- - - - Visualização Estática: Usa uma série de imagens estáticas apresentando o progresso do algoritmo ao longo do tempo
      - Visualização Dinâmica (Animação de algoritmos): Apresenta uma série de imagens sequenciadas sobre o progresso do algoritmo rapidamente, semelhante a uma animação
        
        É considerada superior à Visualização Estática, porém é mais complicada de se implementar