Notação Big O e Complexidade de Código, como usar e por que você já deveria conhecê-la
O que é?
Resumidamente, notação Big O é uma ferramenta matemática usada para descrever a complexidade e o custo de um algoritmo.
Como funciona?
A notação Big O classifica algoritmos em relação às mudanças de desempenho quanto ao tamanho da entrada.
Ou seja, a partir de termos algébricos, ela metrifica o comportamento limitante de uma função quando o argumento tende a um valor específico ou ao infinito.
Basicamente a partir do número de operações que uma entrada é submetida é definida a complexidade daquele código.
Por que usar?
Engenheiros da computação, cientistas de dados e demais profissionais que criam e manipulam código, devem estar sempre atentos a performance e complexidade dos processos que criam, tanto para a otimização de tempo, recursos e também do fator de manutenção, alterações e implementações no código.
Vocês querem código? Vamos a prática!
Ta aí um exemplo de código (python) para calcular o valor O(n):
def find_max(numbers):
max_num = numbers[0]
for num in numbers:
if num > max_num:
max_num = num
return max_num`
Neste exemplo, a função find_max recebe uma lista de números e retorna o número máximo.
A complexidade do algoritmo é determinada pela quantidade de operações que ele executa.
A primeira linha da função (max_num = numbers[0]) é executada apenas uma vez, portanto, tem uma complexidade de O(1).
O loop for que segue executa n vezes, onde n é o tamanho da lista, portanto, tem uma complexidade de O(n).
As três linhas dentro do loop for (if num > max_num:, max_num = num, e return max_num)
são executadas uma vez para cada elemento na lista, portanto, cada uma tem uma complexidade de O(1).
Adicionando todas as complexidades, obtemos uma complexidade total de O(1 + n + 1 + 1 + 1), que é simplificada para O(n).
Complementando, seguem outros posts sobre o assunto:
- https://www.tabnews.com.br/drigols/analise-de-loops-em-complexidade-de-algoritmos
- https://www.tabnews.com.br/gabrielTapes/complexidade-de-algoritmos-recursivos
- https://www.tabnews.com.br/rodriguesxxx/6-100-dias-estudando-estruturas-de-dados-complexidades-as-3-marias
- https://www.tabnews.com.br/marcoshmendes/big-o-notation-conheca-as-complexidades-dos-algoritmos-mais-utilizados
- https://www.tabnews.com.br/lucasrguerra/duvida-calculo-de-complexidade-de-um-algoritmo
- https://www.tabnews.com.br/luizhf42/desvendando-big-o-o-ozao