Juliana Jenny Kolb
Home > Simulados on-line > Questões de Concursos > Tecnologia da Informação (TI) > Algoritmos e Estruturas de Dados
Notação Big O
A Notação Big O, em teoria da computação é usada para descrever como o tamanho da entrada fornecido a um algoritmo qualquer afeta os recursos que o mesmo utiliza, sejam estes de memória ou tempo de execução.
Conhecer esse tipo de informação sobre um algoritmo é a base de qualquer otimização que possa ser feita sobre o mesmo. Não só para entender como o mesmo opera em termos de eficiência geral mas também para decidir corretamente quando for necessário sacrificar alguma aspecto de performance ou complexidade em favor de outro. Isso vale tanto para uso de CPU, memória como para rede, disco e qualquer outro recurso similar.
Complexidade versus performance
Performance é uma medida de quanto dos recursos disponíveis um algoritmo usa. Isso depende tanto do código quanto da máquina onde o mesmo está rodando.
Complexidade, por outro lado, é como o algoritmo escala, ou seja, o que acontece quando mais e mais dados são passados ao mesmo? Complexidade afeta performance, obviamente, mas o converso não é verdadeiro.
Desta forma, a Notação O descreve a complexidade do algoritmo e não sua performance. Isso será visto mais adiante com um exemplo.
Entendendo a notação
O principal objetivo da notação O, no que tange à descrição de complexidade de um algoritmo é explicar de maneira sucinta como o tamanho do problema afeta o número de operação necessárias para executar o mesmo. Operações podem ser atribuições, comparações, cálculos numéricos, leituras, escritas, e assim por diante, tomadas em unidade.
A notação não descreve o número exato de operações, mas está interessada em casos específicos de operação. Em outras palavras, ela é igualmente válida para descrever o melhor caso, o pior caso, ou o caso médio de um algoritmo qualquer.
Ordem de Crescimento da Complexidade
^ – sinal para expoente.
| Ordem | Nome | Descrição |
| O(1) | constante | mais rápido |
| O(log n) | logarítmico
/ sublinear |
muito bom |
| O(n) | linear | é o melhor que se pode esperar se algo não pode ser determinado sem examinar toda a entrada |
| O(n log n) | limite de muitos problemas práticos. Ex. ordenação. |
| O(n^2) | quadrático | muitos algoritmos simples de ordenação |
| O(n^k) | polinomial | para n pequeno |
| O(k^n) | exponencial | evitar o uso |
Vídeo Selecionado
Site Pesquisado
http://logbr.reflectivesurface.com