Como classificar algoritmos com Big O Notation

Como classificar algoritmos com Big O Notation
Brendo Rodrigo Souza de Matos
Brendo Rodrigo Souza de Matos

Compartilhe

Nesta série de artigos, abordamos a importância da análise de complexidade de algoritmos,a implementação da busca binária, a ordenação através do MergeSort e através do QuickSort. Nós sempre mencionamos a notação big O de uma forma bem abstrata e intuitiva. Que tal agora entendê-la um pouco melhor?

INTRODUÇÃO

No nosso atual contexto tecnológico, com as mais diversas máquinas e poderes de processamento e armazenamento volátil, seria inviável mensurar algoritmos apenas contando o tempo em que são executados. Então como podemos saber que um algoritmo tem um desempenho melhor que o outro?

Como abordamos nos artigos mencionados acima, uma ótima opção é calcularmos aproximadamente a quantidade de operações que o algoritmo executa. Mas que operações são essas?

Melhor, pior e caso médio

Para explicar melhor, vamos relembrar a primeira solução de busca de alunos em que utilizamos a busca linear. Decidimos que iríamos percorrer todos os alunos da lista até achar o que estamos buscando. Então vamos pensar em algumas possibilidades?

Supomos que temos a lista de alunos em ordem alfabética e estamos em busca do aluno Brendo.

Sequência linear de pessoas com Brendo na primeira posição e destacado das demais pessoas,, Erica na segunda posição, Mônica na terceira, Nico na quarta, Paula na quinta, Rodrigo na sexta e Wanessa na sétima.

Olha que coisa boa! O encontramos na primeira posição da lista e não precisamos mais percorrer-lá. Por isso este será o nosso melhor caso.

Agora precisamos ir em busca do aluno Nico.

Sequência linear de nomes com Brendo na primeira posição, Erica na segunda, Mônica na terceira, Nico na quarta, destacado dos demais, Paula na quinta, Rodrigo na sexta e Wanessa na sétima. Setas indicam ligações entre um nome e outro, de Brendo até Nico.

Vimos que foi necessário percorrer a metade da lista para achá-lo, então vamos considerar que este é o nosso caso médio.

Agora vamos encontrar a aluna Wanessa?

Sequência linear de nomes com Brendo na primeira posição, Erica na segunda, Mônica na terceira, Nico na quarta, Paula na quinta, Rodrigo na sexta e Wanessa na sétima, destacada dos demais. Setas indicam ligações entre os nomes.

Notamos que percorremos todos os alunos até encontrá-la, então devemos considerar que este é o pior caso, certo? Certo! E onde o Big O entra nessa história? Exatamente aqui! Big O é uma notação que sempre leva em conta o pior caso.

Mas por que dividimos nossa solução em três casos se iremos utilizar apenas o pior? Guarde essa informação pois ela terá grande importância daqui a pouco!

Continuando, vamos aprofundar a análise do pior caso: nele sempre teremos que percorrer todos os alunos. E o que isso significa?

A cada aluno adicionado a nossa lista, o algoritmo executará mais uma comparação. Vamos entender isso melhor através de um gráfico?

Gráfico que representa o crescimento linear do algoritmo,  mostrando que a cada N itens adicionados na lista são necessárias N operações executadas em nosso algoritmo no pior caso, eg. Para uma lista de 1 milhão de alunos, no pior caso executaremos pelo menos 1 milhão de operações no algoritmo.

Agora fica claro que da mesma forma com que a lista cresce, o nosso algoritmo cresce de forma linear quanto a suas operações. Então podemos considerá-lo, na notação big O, como O(N).

Está na hora de analisarmos a nossa segunda solução de busca, a busca binária.

Nesta solução também devemos considerar que há uma lista ordenada e a cada comparação no meio da lista, podemos descartar a metade da lista em que o item não está.

Sequência linear de nomes com Brendo na primeira posição, Erica na segunda, Mônica na terceira, Nico na quarta, Paula na quinta, destacada dos demais, Rodrigo na sexta e Wanessa na sétima. Uma seta sobre os nomes de Rodrigo e Paula aponta para a esquerda. Outra seta, sobre os nomes de Nico, Paula, Rodrigo e Wanessa, aponta para a direita.

Percebemos então que o desempenho já será bem melhor se comparado com o da busca linear, visto que nem mesmo nos piores dos casos vamos percorrer todos os itens.

Mas quão melhor é esse algoritmo? Vamos lá! Para iniciar nossa análise vamos verificar o nosso melhor caso, que ocorre quando buscamos o item do meio da lista.

Sequência linear de nomes com Brendo na primeira posição, Erica na segunda, Mônica na terceira, Nico na quarta, destacado dos demais, Paula na quinta, Rodrigo na sexta e Wanessa na sétima.

Então podemos verificar que no melhor caso, como na busca linear, a binária também se comporta como O(1).

E qual seria o pior caso? Como podemos calcular a quantidade de operações que nossa busca binária irá executar? De maneira bem intuitiva e levando em conta o que já foi informado sobre o algoritmo, vamos responder a essas duas perguntas.

Sabendo que a cada comparação podemos descartar a metade da lista, conseguimos inferir que a divisão da lista por 2 de forma sucessiva nos trará a quantidade de operações realizadas com a contagem das divisões realizadas.

Imagem que mostra a quantidade de operações realizadas na busca binária em uma lista com 7 itens. Os números mostrados são 7 > 4 > 2 > 1.

Aplicando o conceito na lista acima, que continha 7 alunos, vemos que no pior caso executamos apenas 3 comparações.

Imagem que mostra a quantidade de operações realizadas na busca binária em uma lista com 100 itens. Os números mostrados são 100 > 50 > 25 > 13 > 7 > 4 > 2 > 1.

Agora supomos que temos 100 alunos, então no pior dos casos executaremos 7 comparações.

Percebemos a grande diferença entre as 100 comparações que executamos no pior caso da busca linear com as 7 comparações que executamos com a busca binária. Vamos ver isso graficamente?

Gráfico comparando a taxa de crescimento dos algoritmos de busca linear e binária. Em 3 pontos do gráfico, quando temos uma lista com 10 itens a busca linear executa 10 operações, enquanto a binária executa 3. Quando a lista alcança 50 itens, são executadas 50 operações na busca linear e 6 na binária. Quando a lista atinge 100 itens, são executadas 100 operações na busca linear e 7 na binária.

E essa diferença fica ainda mais visível quando aumentamos bastante o tamanho da lista.

Mas será que o algoritmo linear é o pior desempenho que temos em tempo de execução? Já adianto que não e podemos provar com o algoritmo de ordenação SelectionSort que explicamos no artigo de implementação do merge sort.

Mostramos que ele possui a notação assintótica de O(N²), então vamos ver o quão pior é esse algoritmo graficamente?

Gráfico mostra uma simulação de um algoritmo quadrático, que cresce exponencialmente a sua entrada. Quando a lista alcança 10 itens, o algoritmo quadrático executa 100 operações, enquanto o linear e logarítmico executam 10 e 3 operações Quando lista alcança 100 itens, algoritmo quadrático executa 10 mil operações. Linear e logarítmico, 100 e 7 operações.

Vemos que o nosso algoritmo O(N²) ou quadrático evolui de forma exponencial em comparação aos nossos outros algoritmos que crescem discretamente no gráfico. E acredite, ainda há algoritmo piores em eficiência como os O(n³), O(2ⁿ) mas que são assuntos para outras oportunidades.

E com tudo isso, fica mais evidente a importância de conhecermos esses conceitos na hora de implementarmos os nossos programas, as nossas features.

Caso tenha seguido a trilha de artigos sobre complexidade de algoritmos, deve ter se lembrado de uma dúvida relacionada aos algoritmos de ordenação(Merge e Quick Sort): Como escolher o melhor, entre algoritmos com a mesma complexidade?

A seguir, vamos explicar mais detalhadamente quais fatores e parâmetros devemos avaliar em algoritmos com a mesma complexidade no próximo artigo da série.

Nos vemos lá!

Brendo Rodrigo Souza de Matos
Brendo Rodrigo Souza de Matos

Engenheiro de Software apaixonado pelo que faz, amante de novos desafios e sedento por conhecimento. Atualmente sou Engenheiro de Software no Méliuz (B3: CASH3) e mestrando em Ciências da Computação pela Universidade Federal do Amazonas.

Veja outros artigos sobre Programação