CUSTO E ALGORITMOS DE ORDENAÇÃO

CUSTO E ALGORITMOS DE ORDENAÇÃO

1. N LOG N

   • UM ALGORITMO É DITO TER TEMPO LOGARITMO SE T(N) = O(LOG N). DEVIDO AO USO DO SISTEMA DE NÚMEROS BINÁRIOS PELOS COMPUTADORES, O LOGARITMO É FREQUENTEMENTE DE BASE 2 (ISTO É, LOG2 N, MUITAS VEZES ESCRITO LG N).

2. CONSTANTE O(1)

   • TEMPO DE EXECUÇÃO DO ALGORITMO INDEPENDE DO TAMANHO DA ENTRADA
   • OS PASSOS DO ALGORITMO SÃO EXECUTADOS UM NÚMERO FIXO DE VEZES

3. LOGARÍTIMICA O(log2n)

   • TÍPICO DE ALGORITMOS QUE DIVIDEM UM PROBLEMA TRANSFORMANDO-O EM PROBLEMAS MENORES (DIVIDIR PARA CONQUISTAR)
   • TEMPO DE EXECUÇÃO PODE SER CONSIDERADO MENOR DO QUE UMA CONSTANTE GRANDE

4. QUADRÁTICA O(n²)

   • TÍPICO DE ALGORITMOS QUE OPERAM SOBRE PARES DOS ELEMENTOS DE ENTRADA
   • COMUMENTE EM UM ANEL DENTRO DE OUTRO
   • ÚTIL PARA RESOLVER PROBLEMAS DE TAMANHOS RELATIVAMENTE PEQUENOS

5. CÚBICA O(n³)

   • ÚTIL PARA RESOLVER PROBLEMAS PEQUENOS

6. LINEAR O(n)

   • O ALGORITMO REALIZA UM NÚMERO FIXO DE OPERAÇÕES SOBRE CADA ELEMENTO DA ENTRADA
   • MELHOR SITUAÇÃO PARA UM ALGORITMO QUE PROCESSA N ELEMENTOS DE ENTRADA E PRODUZ N ELEMENTOS DE SAÍDA

7. EXPONENCIAL O(2n)

   • TÍPICOS DE ALGORITMOS QUE FAZEM BUSCA EXAUSTIVA (FORÇA BRUTA) PARA RESOLVER UM PROBLEMA
   • NÃO SÃO ÚTEIS DO PONTO DE VISTA PRÁTICO