Quando o tempo de execução te assusta!

A notação Big O é um conceito que todos os estudantes de ciência da computação encontrarão em seus estudos em algum lugar ao longo do caminho. Mas, qual a importância que o Big O tem?

Big O?

A letra “O” vem de ordem, outro termo para descrever o crescimento de uma função. A letra “N” sempre utilizada na matemática, representa o número de entradas em questão.
Utilizando a notação Big O, em termos básicos, você irá saber com que rapidez uma função crescerá ou diminuirá. O tempo de execução de uma função é expresso em quão rápido ela cresce em relação à entrada conforme a entrada aumenta.
Para um algoritmo com muito poucas entradas, isso não é um grande negócio. Mas, à medida que a quantidade de insumos aumenta para um número muito grande, torna-se cada vez mais importante. Afinal, ninguém quer esperar o dia todo apenas para carregar uma página em um site ou a visualização de um aplicativo.

O tempo de execução não é o único fator ao considerar a eficiência da função. A eficiência de um algoritmo também considera o uso da rede, de disco e de memória.
A complexidade da CPU (tempo) é o principal fator. É considerado principalmente como o desempenho, quanto espaço em disco ou memória / tempo é usado quando um programa está sendo executado junto com a complexidade.

Por exemplo, como os requisitos de recursos aumentam à medida que as entradas aumentam.

Complexidade da notação

Seguindo a ordem dos menos eficientes aos mais eficientes:

1. O(n!) (fatorial) o número de instruções executadas cresce muito rapidamente para um pequeno crescimento do número de itens processados. Dentre os ilustrados é o pior comportamento para um algoritmo, pois rapidamente o processamento se torna inviável. É o caso da implementação inocente do Problema do Caixeiro Viajante ou de um algoritmo que gere todas as possíveis permutações de uma lista, por exemplo (fonte desse exemplo).
2. O(2ⁿ) (exponencial) também é bem ruim, pois o número de instruções também cresce muito rápidamente (exponencialmente), ainda que numa taxa menor do que o anterior. É o caso de algoritmos que fazem busca em árvores binárias não ordenadas, por exemplo.
3. O(n²) (quadrático) é factível, mas tende a se tornar muito ruim quando a quantidade de dados é suficientemente grande. É o caso de algorítmos que têm dois laços (for) encadeados, como, por exemplo, o processamento de itens em uma matriz bidimensional.
4. O(n log n) (sub-quadrático ou super-linear) é melhor do que o quadrático, sendo geralmente até onde se consegue otimizar algoritmos que são quadráticos em sua implementação mais direta e inocente (naïve). É o caso do algoritmo de ordenação QuickSort, por exemplo (que tem essa complexidade no caso médio, mas que ainda assim é quadrático no pior caso).
5. O(n) (linear) é aquele cujo crescimento no número de operações é diretamente proporcional ao crescimento do número de itens. É o caso de algoritmos de busca em uma matriz unidimensional não ordenada, por exemplo.
6. O(log n) (logaritmo) é aquele cujo crescimento do número de operações é menor do que o do número de itens. É o caso de algoritmos de busca em árvores binárias ordenadas (Binary Search Trees), por exemplo (no caso médio, no pior caso continua sendo linear).
7. O(1) (constante) é aquele em que não há crescimento do número de operações, pois não depende do volume de dados de entrada (n). É o caso do acesso direto a um elemento de uma matriz, por exemplo.

Conclusão

Espero ter ajudado e ter proporcionado uma boa leitura, em breve devo escrever exemplos para cada tipo de Big O Notation.

Precisava escrever algo para o último dia do ano, e porque não sobre um assunto que dominou meu ultimo mês de trabalho de 2021?

Obrigado.

Feliz 2022! Com muito amor e saúde!

Fonte: https://www.bigocheatsheet.com/