Please enable JavaScript.

Coggle requires JavaScript to display documents.

Análise da eficiência de algoritmos - Coggle Diagram

- - - - a característica escolhida para definir o n pode variar
        
        se o input é uma lista, n é seu tamanho
        
        se o input é um número, n pode ser o próprio número ou seu tamanho em bits dependendo do problema
        
        etc..
      - .
    - - Operação que mais contribui pro tempo de execução
      - Tipicamente a operação mais lenta localizada no loop mais interior do algoritmo
      - T (n) ≈ cop * C(n).
        
        T(n) = tempo de execução
        
        cop = tempo de execução da operação base
        
        C(n) = número de execuções da operação base para um input de complexidade n
        
        Ordem de crescimento
        
        log n
        
        n
        
        n * log n
        
        constante
        
        n²
        
        n³
        
        X^n
        
        .
        
        n!
        
        Chamados de exponenciais, algoritmos com essas ordens de crescimento tendem a aumentar bruscamente o tempo de execução mesmo pra inputs não tão complexos
        
        Análise assintótica das ordens de crescimento
        
        Notação O (Big O)
        
        demarca o conjunto de algoritmos com ordem de crescimento inferior ao referencial
        
        Notação Big Omega
        
        demarca o conjunto de algoritmos com ordem superior ao referencial
        
        Notação Big Theta
        
        demarca o conjunto de algoritmos de mesma ordem do referencial
        
        definição
        
        limites
        
        Análise de casos
        
        em alguns algoritmos, a eficiência para um mesmo tamanho de input é alterada pela particularidade e organização do input, tornando relevante a análise de casos
        
        Pior caso
        
        Bastante usado
        
        Melhor caso
        
        Raramente usado
        
        Caso médio
        
        Bastante usado, bom analisar a eficiência do algoritmo numa aplicação geral
        
        Sua velocidade não é tipicamente obtida pela simples média entre a velocidade do pior caso e do melhor caso