Complexidade de Algoritmos — Abordagens O(n²), O(n) e O(n log n) para o mesmo problema
O segundo algoritmo (veja o primeiro aqui) que eu escolhi fazer uma análise um pouco mais detalhada foi o Contador de Duplicados disponibilizado no site do LeetCode com o seguinte enunciado:
Dado um array de inteiros, encontre se o array possui algum valor duplicado. Sua função precisa retornar true se algum elemento aparecer pelo menos duas vezes no array e retornar false se todos os elementos forem distintos.
Busca Linear Ingênua
A primeira abordagem que eu encontrei para solucionar este algoritmo, possui o nome de Busca Linear Ingênua (Naive Linear Search).
Apesar dela ser a primeira que vem na nossa mente quando pensamos em grupos de números pequenos não, concordo totalmente com o uso do termo “ingênua” para defini-la.
Como veremos ao longo deste artigo, as outras soluções utilizam conceitos um pouco mais sofisticados e comportamentos embutidos e específicos das novas linguagens de programação. Chamar o algoritmo acima de “ingênuo” utilizando estruturas de dados modernas, parece me soar um pouco anacrônico. (Opinião pessoal é claro).
Para entender melhor como a Análise de Complexidade nos ajuda a entender com mais clareza o comportamento de um algoritmo irei o mostrar uma abordagem empírica e uma analítica pra solução de Busca Linear Ingênua.
Abordagem Empírica x Abordagem Analítica
Antes de qualquer coisa, há dois pontos importantes de serem observados :
1 — Sempre devemos utilizar em nossa análise o pior caso. Onde o algoritmo executa a maior quantidade de passos possível.
2 — Caso a fórmula apresentada para a abordagem analítica apresente números exponenciais (n²..n³..). O maior expoente será fator dominante no cálculo da complexidade (esse conceito ficará mais claro ao longo da explicação)
Abordagem empírica
Observe a execução detalhada da solução mostrada acima, recebendo uma entrada que possui números duplicados: {1,2,3,1}.
Analisando de forma rápida, podemos perceber que :
1 — O algoritmo não executou todos os passos. Na última linha, ao comparar o quarto elemento com o primeiro elemento do mesmo vetor (graças aos 2 índices independentes) a condição do algoritmo foi satisfeita. Sendo assim, esse detalhamento acima com os valores {1,2,3,1} não representa o pior caso.
2 — Temos um total de 7 situações onde um algoritmo realizou comparações entre pares com o objetivo de satisfazer o seu objetivo.
Dada essa primeira situação, o que irá acontecer quando executarmos o pior caso? Onde não haja um elemento duplicado na lista e o algoritmo tenha que percorrer todos os elementos?
Veja abaixo o detalhamento da execução do mesmo algoritmo utilizando os seguintes elementos {1, 2 , 3 , 9 }.
Temos 10 comparações no pior caso, onde o algoritmo fez uma varredura em todos os elementos do Array.
Como pode ser percebido, a abordagem empírica é trabalhosa de fazer, difícil de explicar e chata de entender. E outro problema dessa abordagem é que, não fica tão claro como utilizá-la para definir a complexidade desse algoritmo.
Abordagem Analítica
Conforme detalhado na solução deste algoritmo no LeetCode, conseguimos verificar através da fórmula matemática n(n +1)/2 qual a quantidade de pares que podem ser gerados na comparação que utiliza a abordagem Naive Linear Search.
Sendo n a entrada de elementos, ao substituirmos pelas entradas já analisadas acima, encontramos os mesmo valores de interações entre os pares:
4 *(4 + 1) / 2 = (16+4)/2 => 10 pares a serem comparados
Utilizando a regra do expoente como fator dominante na Notação O (n² + n / 2) concluo então que a abordagem Naive Linear Search possui complexidade O(n²). (Caso você tenha uma opinião diferente, fique a vontade para comentar, estou aprendendo este assunto ainda).
Em meus estudos surgiu a dúvida:
eu posso transformar (n² + n/ 2) em (n³ / 2)? Meu algoritmo poderia ser O(n³)?
Pra responder esta questão, basta substituir o n e comparar com a versão empírica mostrada acima.
(4 ^3)/2 = 64/2 => 32 pares (resposta errada)
Ou seja, a abordagem Naive Linear Search para solucionar o algoritmo de contagem de números duplicados possui a complexidade de tempo O(n²).
Mas será que podemos melhorar esse tempo?
Solução O(n)
Como já citado no inicio do artigo, podemos utilizar algumas estruturas de dados um pouco mais sofisticadas para resolver esse problema com um desempenho muito mais aceitável.
A estrutura HashSet do C# (todos os meus códigos serão escritos nessa linguagem) possui uma característica muito conveniente para este nosso tipo de problema: ela não aceita que valores duplicados.
Desta forma, o seguinte algoritmo abaixo irá obter sucesso em capturar os valores duplicados.
Esta versão de algoritmo realiza um loop, o que facilita o entendimento da sua complexidade O(n) pois o valor da entrada nums influencia diretamente na quantidade de interações que o algoritmo irá executar. Desta forma, o valor de n é o fator dominante deste algoritmo.
Aproveitando ainda mais as facilidades fornecidas pela Linguagem C# e sua estrutura ISet<T> podemos implementar o algoritmo de contagem de duplicados até utilizando um número menor de steps na sua implementação.
Uma vez que a estrutura HashSet não aceita valores duplicados, podemos facilmente comparar com a quantidade de itens da entrada.
Solução O(n log n)
A última implementação desse algoritmo, tem eficiência intermediária entre O(N) e O(N²).
Primeiro , ela realiza uma ordenação dos dados e depois procura os duplicados. Para verificar os duplicados, o algoritmo compara uma posição i do vetor com outra mais avançada (i+ 1).
Visto que o objetivo do algoritmo é encontrar os duplicados e parar o processamento, ele não irá processar todas as comparações no seu melhor caso (onde os elementos duplicados não são os maiores da lista).
{1,2,3,1} se transforma em{1,1,2,3}. Na execução o algoritmo irá parar no primeira step.
Já no seu pior caso, o algoritmo processa um número (n-1) de comparações:
{1,3,2,9} se transforma em {1,2,3,9} e o algoritmo irá fazer 3 comparações: (1–2), (2–3),(3,9)
Neste momento surge a dúvida: se na implementação do algoritmo são utilizadas apenas comparações simples entre elementos, porque então a sua classificação é de (n log n)?
QuickSort
A Busca linear Ingênua era a única das implementações que não tinha um recurso interno “embutido” na sua implementação. Na última solução utilizamos a função Sort presente na estrutura de dados Array da Linguagem C#.
Esta função possui uma complexidade (n log (n)) pois segundo a Microsoft, ele utiliza internamente o algoritmo QuickSort para a maioria dos casos. (InsertSort para uma quantidade de partição de elementos menor ou igual a 16 e HeapSort para uma quantidade de partições 2 * Log^(n)).
Como o QuickSort possui a complexidade de (n log (n)) (vamos abstrair e assumir que a lista de elementos de entrada não está ordenada, porque aí essa complexidade se altera pra O(n²)) a nossa solução “herda” essa complexidade para si, uma vez que ela passa se tornar o elemento dominante do algoritmo.
Conclusão
Pretendo abordar com mais detalhes num artigo futuro, o que faz um algoritmo como QuickSort executar com complexidade sub-quadrática. Neste caso aqui, objetivo era mostrar superficialmente porque o algoritmo O (N) é considerado mais eficiente que um O(n log n) ou um O(n²).
Pra quem tem um background de Matemática Discreta e Abstrata muito apurado, essa relação é bastante óbvia.
Mas só agora estou conseguindo fazer as pazes com alguns conceitos matemáticos não comuns ao nosso dia-a-dia como os Logaritmos.
Graças a pessoas como Gustavo Viegas e Professor Ricieri estou conseguindo perceber o quanto entender esses recursos podem me tornar um programador mais analítico e menor empírico. (não que o empirismo seja um problema, mas nem sempre é o caminho menos trabalhoso).
Um abraço e obrigado pela Leitura!
