O Poder da Análise de Algoritmos: Uma Breve Visão sobre Big O
Se você é programador ou está estudando para se tornar um, em algum momento, você ouvirá falar sobre análise de algoritmos. O que popularmente muitos conhecem como Big O ou notação Big O.
A primeira vista, esses tópicos de ciência da computação podem nos dar uma impressão de ser algo muito distante da realidade de um programador. Pode nos dar um falso entendimento que esses assuntos devem ser tratados somente no meio acadêmico.
No entanto, como programadores, temos esses assuntos presentes em nosso dia a dia, mesmo que sem perceber. Fazemos análises de algoritmos intuitivamente. Sempre que estamos escrevendo código estamos analisando os algoritmos que foram criados. Portanto, analisar um algoritmo não é uma atividade incomum no momento de programar.
Mas e a notação Big O?
Para explicar para você, caro leitor, do que se trata esse tema, vou dividir a explicação em 3 blocos, vou explicar o que é um algoritmo, vou falar sobre análise de algoritmos e irei concluir com a notação Big O.
O que é um algoritmo?
Sendo direto na definição. Algoritmos podem ser definidos como sequências de passos para se chegar a um objetivo. Por exemplo, se você vai escovar os dentes, tem uma sequência de ações que você precisa executar para cumprir esse objetivo. Pegue a escova. Coloque pasta na escova. Escove os dentes do lado esquerdo etc.
Mesmo sem se dar conta, você segue esse algoritmo toda vez em que escova os dentes. Você executa essas sequências de passos para chegar ao seu objetivo final que é ter dentes limpos.
Só que para um mesmo objetivo, podemos ter diversos caminhos para se chegar a ele. Existe infinitas maneiras de se escovar os dentes, infinitas variações de algoritmos para escovar os dentes. Por exemplo, você pode primeiro passar fio dental, molhar a escova antes de colocar a pasta, escovar com a mão contrária a habitual, iniciar por um lado ou um ângulo diferente etc.
Todas essas variações de algoritmos possuem um determinado custo de tempo, que pode ser maior ou menor dependendo da opção escolhida.
Análise de Algoritmos
Se quisermos escolher o melhor algoritmo para escovar os dentes em relação ao tempo gasto, podemos medir com um cronômetro o tempo decorrido em cada variação e chegar a conclusão de qual é o mais rápido. Mas, se quisermos avaliar de acordo com a limpeza dos dentes, precisamos montar uma métrica para dizer se o objetivo está compatível com o esperado.
De maneira similar, se quisermos saber escolher o melhor algoritmo dentre um grupo de algoritmos em termos de tempo de execução precisamos saber como avaliar a performance de um algoritmo. Novamente, podemos marcar o tempo total de execução, mas essa não é a melhor forma, pois esse tempo pode variar de acordo com o hardware utilizado, a linguagem de programação, o sistema operacional, a utilização do processador etc.
Se quisermos avaliar de uma forma generalizada, olhando apenas para o algoritmo, será necessário ter uma métrica para dizer se aquele algoritmo é rápido ou devagar. Essa métrica deve ser independente do local, de hardware ou da linguagem que está implementado o algoritmo. Precisa existir uma notação que sirva para qualquer caso de avaliação.
Na análise de algoritmos foram desenvolvidas as ferramentas necessárias para fazer essa avaliação. Basicamente, vamos olhar para um trecho de código e tentar exprimir uma equação matemática que descreva o comportamento esperado daquela função. Essa expressão matemática vai nos ajudar a encaixar o algoritmo em um tipo de comportamento esperado.
Notação Big O?
A notação Big O vai ser uma critério para analisar o algoritmo no pior caso de entrada, na situação em que o algoritmo vai executar o maior número de passos possíveis para resolver o problema.
Resumindo, a notação trata-se de conseguir classificar seu algoritmo em uma taxa de crescimento. Quando alguém diz: “seu algoritmo é O(n)”, Isso quer dizer que ele tende a crescer de forma linear no pior caso de uso.
Abaixo estão alguns padrões de comportamentos:
Por que isso é importante?
Conseguir classificar o comportamento do seu algoritmo sem precisar rodar casos de testes te ajudará muito no seu dia a dia. Analisar seu código em uma batida de vista te possibilita a saber se é ou não uma boa abordagem.
Lembrando que uma abordagem ruim pode trazer impactos não somente para seu usuário, mas também para a sua empresa.
No fim, saber classificar e entender as complexidades assintóticas te da poderes.
