Big O Notation
Vamos logo falar da notação que vai nos acompanhar a carreira inteira. Big O é uma forma de denotar o desempenho de um algoritmo, levando sempre em consideração o pior dos casos. Porém, Big O leva em consideração a escalabilidade e a execução. Por exemplo, O(n) é melhor que O(n²), mas, sem a análise assintótica, não podemos afirmar com total certeza. Análise assintótica é a forma de avaliar o algoritmo conforme o tamanho da entrada cresce.
A análise assintótica é utilizada para avaliar o desempenho e a eficiência de um algoritmo à medida que o tamanho da entrada de uma função cresce indefinidamente, aproximando-se do infinito. Isso é feito já que medir pelo tempo exato cria muitas variantes e inconsistências, como a velocidade do processador da máquina.
Porém, mesmo sem uma análise assintótica entre O(n) e O(n²), nós conseguimos afirmar qual vai escalar melhor com o tamanho do input.
Por exemplo, temos 2 algoritmos que organizam uma estante de livros:
Algoritmo A O(n): Vai ler uma instrução complexa para cada livro. O "custo fixo" por item é alto.
Algoritmo B O(n²): A lógica é simplória, quase instantânea, mas você precisa comparar cada livro com todos os outros.
Se a estante tem apenas 2 livros, o Algoritmo B O(n²) provavelmente será mais rápido porque a lógica é simples. Mas, se a estante tem 1.000 livros, o Algoritmo A O(n) vence, porque ele escala de forma constante, enquanto o outro explode em complexidade.
Complexidade Temporal e Complexidade Espacial
Existem dois tipos de complexidade sobre os quais vamos falar bastante na maioria dos algoritmos, sendo eles:
Complexidade Temporal: É o tempo que a execução leva conforme o tamanho da entrada cresce. Por exemplo, um algoritmo que percorre todos os elementos de uma lista para encontrar o maior valor executa uma operação para cada elemento, caracterizando uma complexidade O(n).
Complexidade Espacial: É a quantidade de memória adicional que o algoritmo utiliza durante sua execução, além da memória necessária para armazenar os dados de entrada.
Complexidades boas por ordem de melhor para mediana
| Complexidade | Big O | Exemplo de algoritmos |
|---|---|---|
| Constante | O(1) | Acesso a elementos de um array |
| Logaritmo | O(log n) | Busca binária em arrays |
| Linear | O(n) | Busca sequencial em arrays |
| Linearitmica | O(n log n) | Classificação de arrays com merg sort |
Complexidades ruins por ordem de pior para horrivel
| Complexidade | Big O | Exemplo de algoritmos |
|---|---|---|
| Quadrático | O(n²) | Ordenação de arrays com bubble sort |
| Exponencial | O(2ⁿ) | Problema do Caixeiro Viajante |
| Fatorial | O(n!) | Determinante de matrizes com teorema de Laplace |
Referências
https://www.geeksforgeeks.org/dsa/analysis-algorithms-big-o-analysis/?_x_tr_hist=true
Entendendo Algoritmos: Um guia ilustrado para programadores e outros curiosos - ISBN-13: 978-8575225639
Top comments (0)