Seu algoritmo está escalável?

O que é notação O ou Big O Notation ?

A notação O (Big O) é uma notação matemática utilizada para medir a eficiência e desempenho do algoritmo de forma simples e prática. Ela é usada para descrever o limite superior do número de operações que um algoritmo realiza em função do tamanho de entrada. Por exemplo, se um algoritmo tem uma complexidade O (n), isso significa que o número de operações cresce linearmente com o tamanho de entrada.

Alguns exemplos de algoritmos comuns e sua notação O incluem:

• Busca linear: O(n), pois o algoritmo percorre cada elemento na entrada, um de cada vez.
• Busca binária: O(log n), pois o algoritmo divide a entrada em pedaços cada vez menores até encontrar o elemento desejado.
• Ordenação por bolha: O(n^2), pois o algoritmo compara cada par de elementos na entrada e troca-os se eles estiverem fora de ordem, e isso é feito várias vezes até que a entrada esteja ordenada.
• Ordenação quicksort: O(n log n), pois o algoritmo divide a entrada em pedaços cada vez menores e depois os une de volta em ordem.

Medição

Para testar a performance de um algoritmo, é comum medir o tempo de execução para diferentes tamanhos de entrada e comparar com a notação O esperada. É possível fazer testes usando bibliotecas específicas para medir o tempo de execução, ou usando uma linguagem de programação com recursos de medição de tempo embutidos.

Abaixo temos um exemplo bem simples de como medir o tempo de execução de um algoritmo de busca linear usando a linguagem C#, com a classe Stopwatch:

Vejamos um outro exemplo abaixo, de como medir o tempo de execução de um algoritmo usando o algoritmo de ordenação quicksort, também com C#.

Em ambos os exemplos, a classe Stopwatch é usada para iniciar e parar a medição do tempo de execução, e o tempo é exibido em milissegundos.

É importante notar que medir o tempo de execução de um algoritmo pode ser afetado por vários fatores, como a velocidade do processador, o tamanho da entrada e a otimização do código, então é importante usar várias medições e fazer testes com diferentes tamanhos de entrada para obter resultados precisos. No site Big O Cheat Sheet tem como objetivo, mostrar a complexidade de espaço tempo do Big-O de cada algoritmo.

A importância do Big O Notation

É importante que os desenvolvedores conheçam o Big-O para que possam escolher melhor a otimização do seus algoritmos, de acordo com as necessidades de desempenho, o que é fundalmental para garantir que o software seja rápido, escalável e eficiente.

Além disso, a notação O permite prever o desempenho de um algoritmo com base no tamanho de entrada, o que é útil para identificar problemas de escalabilidade antes que eles aconteçam. Isso é especialmente importante para softwares que precisam lidar com grandes volumes de dados ou que precisam ser escaláveis.

Leia mais sobre:

• função logarítimica
• Funções em notação assintótica
• Complexidade de algoritmos
• Complexidade Temporal e Espacial

Complexidade de tempo e espaço Big-O

A complexidade de tempo de um algoritmo descreve quanto tempo é necessário para executar o algoritmo em relação ao tamanho da entrada, também pode ser expressa em notação Big-O. A complexidade de espaço, por outro lado, descreve quanto espaço (memória) é necessário para armazenar os dados e as estruturas de dados utilizadas pelo algoritmo.

Por exemplo, se um algoritmo tem uma complexidade de espaço O(n), isso significa que a quantidade de memória adicional necessária pelo algoritmo é proporcional ao tamanho da entrada. Um algoritmo com uma complexidade de espaço O(1), é chamado de algoritmo com complexidade constante de espaço, pois ele não requer mais memória adicional independentemente do tamanho da entrada.

Conclusão

Este artigo contém uma breve explicação sobre a notação matemática Big-O, como descrevo, é importante os desenvolvedores saibam ao menos o que significa e para que serve. É sempre importante mensurar a complexidade e o tempo que seu algoritmo está executando. Vale salientar que é um assunto que é muito visto em questionários de processos seletivos para áreas cargos de Software Engineer.

Referências