Big O - A importância e a influência de saber analisar algoritmos.

O objetivo do post não é ensinar Big O Notation.

Importância

Big O é uma notação para analisar os piores casos de algoritmos, e afinal, qual o valor de conhece-la?

Muitos podem pensar que é algo fútil e apenas utilizado para ser cobrado em provas da faculdade e entrevistas de emprego. Entretanto, seu propósito está em estudar a complexidade de tarefas computacionais para aplicar algoritmos mais eficientes para casos apropriados.

Ficou difícil? Vamos facilitar...

Imagine que você tenha uma lista de números, ordenada, da seguinte forma:

1, 10, 24, 37, 61, 89, 121

A partir disso, você deve criar um código para dizer se um número X está ou não na lista. O método que você provavelmente pensou em codificar foi: ir de número em número, desde o início, e comparar cada um com o número X, caso seja igual você retornaria True, caso nenhum seja igual, False.
Essa não é uma aplicação ruim, visto que a lista de números é pequena. Com esse método, você faria no máximo 7 operações (tamanho da lista), já que se o número X não estiver na lista, você terá que ir até o final para verificar tal fato.

Contudo, imagine que agora seja dada uma lista, ordenada, com 10^8 números e você tenha a mesma tarefa. Concorda que serão necessárias 10^8 consultas? AAAAHH, isso é um número extremamente grande.

E se eu dissesse que é possível buscar tal número X, na mesma lista, com menos de 30 operações, seria incrível não é mesmo?

E SIM, É POSSÍVEL!!!

O método que faz isso nessa incrível velocidade é chamado de Binary Search. E agora, consegue ver a importância de saber analisar seus algoritmos? Poder desenvolver códigos e lógicas mais eficientes que retornam o mesmo resultado de forma mais veloz.

Influência

Assim, você pode estar se perguntando, mas isso realmente afeta o meu dia a dia?

COM TODA CERTEZA.

Imagina se a Google não soubesse implementar algoritmos mais eficientes e toda vez que você fosse fazer uma simples pesquisa tivesse que ficar esperando minutos ou até horas para receber o resultado, seria horrível, concorda?

Apesar disso, para criar seu site de portfólio ou projeto pessoal básico, provavelmente você não irá se preocupar com Big O e implementação de métodos extremamente eficientes, visto que a demanda de informações será baixa e isso não afetará o projeto.

Sendo assim, pode-se concluir que uma boa parte dos desenvolvedores acredita que analisar algoritmos seja perda de tempo, visto que tal análise é de fato relevante em projetos de grande escala, os quais, não são a maiora existente. Mas não caia nessa, se você quer se tornar um excelente profissional da área, conhecer métodos mais eficientes é de extrema importância.

Conclusão

Vamos utilizar um pouco da notação Big O?

Na aplicação primordial o máximo de operações era sempre o tamanho exato da lista de números, ou seja, apresenta complexidade:

O(N), em que N é o tamanho da lista.

Já na aplicação otimizada, o máximo de operações cresce de forma logarítmica, apresenta complexidade:

O(log N), em que N é o tamanho da lista.

Dessa forma, podemos ver no seguinte gráfico que o primeiro método apresenta um crescimento das operações computacionais muito mais rápido que do segundo método, ou seja, o primordial demora mais que o otimizado para retornar uma resposta.

Continue estudando

Caso queira saber como analisar suas implementações em função da Big O Notation, indico esses dois vídeos no youtube: Vídeo 01 | Vídeo 02.

Caso queira treinar e aplicar o conceito de Binary Search em outra situação, diferente da apresentada no post, acesse esse post do Programiz e tente resolver esse desafio do LeetCode.

Fonte:
McDowell. Cracking the Coding Interview, 6th Edition. Julho de 2015.
Cormen, et al. Introduction to Algorithms, 3rd Edition. Setembro de 2009.