Andre Nobre

Desenvolvedor e arquiteto. Apaixonado por tech, código limpo e simplificação dos discursos tecnológicos.

Categoria: Tech Basic

Analisando a complexidade de algoritmos

Existem alguns fundamentos básicos de algoritmos que todos aqueles que se envolvem com isto deveriam saber.

Um deles é entender o quão complexo é um algoritmo, e principalmente se há alternativas melhores.

Para isto existem notações e métodos conhecidos na literatura.

O objetivo deste post é tentar explicar de maneira clara a notação Big-O.

Começando a entender a notação

Notação

Substantivo feminino

1.ato de notar, de representar algo por meio de símbolos ou caracteres.

Primeiro ponto que precisamos chegar a um acordo: não podemos medir complexidade e performance (eficiência) baseada em tempo (milissegundos, segundos, minutos, etc) através de um programa rodando na sua própria máquina.

O tempo final de um algoritmo é relativo à capacidade do seu ambiente de execução. O que eu quero dizer com isto é que se você tem um ambiente ruim, seu algoritmo demorará mais tempo pra ser executado.

De forma resumida, é por este motivo que não podemos entender a complexidade de um algoritmo pelo tempo que ele executa em uma determinada estrutura.

Por isto partimos de um pressuposto que a gente irá aferir nossa complexidade através de medidas que independem do runtime, através de uma notação.

Podemos criar diversas maneiras de medir esta complexidade e chegar a um padrão. Porém, a comunidade acadêmica matemática já fez isso há bastante tempo, criando a notação Big-O.

A notação Big-O demonstra a complexidade de um algoritmo em referência à suas entradas. Por exemplo, se um algoritmo executa apenas 1 instrução, e sempre executará independente do valor da sua entrada, dizemos que a complexidade deste algoritmo é O(1), ou constante.

Veja um exemplo muito simples:

static int SumNumbers(int a, int b) 
{ 
  return a + b; 
} 

Analise que independente dos valores de a e b, este algoritmo sempre executará 1 instrução.

Podemos ter casos mais complexos como O(n). Esta notação indica um crescimento linear de acordo com a entrada.

Veja o exemplo abaixo:

static bool FindItem(List<string> items, string value) 
{ 
  foreach(var item in items) 
  { 
    if (item == value) 
    { 
      return true; 
    } 
  } 
  return false; 
} 

Este bloco aceita uma lista de entrada e um valor para ser encontrado. Vamos considerar que a lógica interna (if…) é executada uma vez para cada item da lista.

Se adotarmos que cada execução demora “1 tempo” pra ser executado, se enviarmos 10 elementos teremos “10 tempos”; se enviarmos 100 elementos teremos “100 tempos” e assim por diante.

Veja que o crescimento é linear; se em um determinado ambiente de execução esta unidade “tempo” for igual a 1 segundo, cada elemento adicionado na lista soma 1 segundo ao tempo total.

Por isto a notação O(n) é linear em relação à entrada da função versus tempo de execução.

No gráfico podemos ver:

O que podemos entender por este início?

Espero que neste ponto tenha sido possível compreender que a notação Big-O demonstra a complexidade de um algoritmo criando uma referência em relação ao número de execução das instruções de acordo com o tamanho da entrada.

Se um algoritmo, independente da sua entrada, sempre executa apenas 1 instrução, dizemos que a complexidade é O(1). Se a quantidade de instruções executadas cresce na mesma proporção que a sua entrada, dizemos então que é O(n).

Avançando um pouco mais

A lógica da notação é sempre a mesma. Se você tem um algoritmo que a complexidade cresce em uma proporção log n de acordo com sua entrada, então dizemos que sua complexidade é O(log n)

Um exemplo clássico de um algoritmo O(log n) é uma busca binária

Veja:

static int binarySearch(int[] nums, int startingIndex, int length, int itemToSearch) 
{ 
  if (length >= startingIndex) 
  { 
    int mid = startingIndex + (length - startingIndex) / 2; 
 
    // If the element found at the middle itself 
    if (nums[mid] == itemToSearch) 
    return mid; 
 
    // If the element is smaller than mid then it is 
    // present in left set of array 
    if (nums[mid] > itemToSearch) 
    return binarySearch(nums, startingIndex, mid - 1, itemToSearch); 
 
    // Else the element is present in right set of array 
    return binarySearch(nums, mid + 1, length, itemToSearch); 
  } 
 
  // If item not found return 1 
  return -1; 
} 

Por que este algoritmo é O(log n)?

Primeiro vamos entender do se trata este algoritmo.

O objetivo é encontrar um número dentro de uma lista de n números.

Uma maneira muito fácil de executar isto é percorrer todos os números da lista, realizando a comparação sobre cada item.

No pior cenário, vamos realizar a análise sobre TODOS os elementos. Isso quer dizer que se a lista tiver 100 elementos, vamos realizar a comparação sobre os 100 para encontrar o que estamos procurando (no pior cenário).

Então desta forma o algoritmo teria complexidade O(n).

Usando uma busca binária podemos encontrar o elemento procurado de forma muito mais fácil.

Através de divisão e conquista, o algoritmo busca dividindo a lista (considerando que está ordenada) e realizando a pesquisa apenas no bloco onde o elemento provavelmente está, ate que encontre.

Isso quer dizer que nunca iremos percorrer todos os elementos da lista, garantindo então que a complexidade deste algoritmo não cresce de forma linear com o número de elementos (portanto, de fato não é O(n)).

Vamos considerar esta lista para nosso exemplo: {1, 5, 6, 10, 15, 17, 20, 42, 55, 60, 67, 80, 100}

Supondo que queremos o número 55, em quantas execuções conseguiremos encontrar o resultado?

Faça o teste de mesa do algoritmo. O resultado será 3 execuções!

Se utilizássemos algum algoritmo O(n) poderíamos levar até 13 execuções.

Aqui você pode se perguntar: mas se o elemento a ser buscado está no inicio do conjunto, a busca linear é muito mais performática.

E você está de certo. Mas é fato que não podemos lidar com algo tão variável como este. E por isto é importante saber de um conceito importante sobre Big-O:

Esta notação representa o limite superior de uma função, dado uma entrada extremamente grande (ou com esta tendência).

Isso quer dizer que, dado uma entrada n consideravelmente grande, o comportamento da função segue o resultado da notação.

No nosso caso, com um crescimento linear, caso a lista n seja extremamente grande (por exemplo, 1 bilhão de registros), poderíamos levar até 1 bilhão de comparações para encontrar o número desejado, enquanto com um algoritmo log n levaríamos em torno de 31 execuções.

Podemos ver a performance de um algoritmo O(log n) através do gráfico abaixo:

Como analisar um código da minha solução?

Algo muito comum de se encontrar na literatura é a análise de complexidade utilizando Big-O sobre algoritmos padrão.

Para analisar sobre seu algoritmo do dia a dia, a lógica é a mesma. Vamos ver este exemplo abaixo:

 var listaNovosRelacionamentos = modalidadesCategoria.Where(filtro => filtro.Selecionado == true).ToList();
                foreach (var modalidade in listaNovosRelacionamentos)
                {
                    try
                    {
                        var modelosAtualizar = relacionados.Where(a => a.CategoriaId == modalidade.CategoriaId && a.ModeloId == codigoModelo && a.ModalidadeId == modalidade.ModalidadeId);

                        foreach (var modeloAtualizar in modelosAtualizar)
                        {
                            if (!modeloAtualizar.FlagPrincipal || (modeloAtualizar.FlagPrincipal && modalidade.Selecionado))
                            {
                                modeloAtualizar.DataAtualizacao = DateTime.Now;
                                modeloAtualizar.FlagExcluido = !modalidade.Selecionado;
                                ModeloCategoriaModalidade.Atualizar(modeloAtualizar);
                            }
                            else
                            {
                                status.AdicionarErro("Não é possível desvincular a modalidade principal!");
                            }

                        }

                        if (!modelosAtualizar.Any())
                        {
                            if (modalidade.Selecionado)
                            {
                                var modeloNovo = new ModeloCategoriaModalidade();
                                modeloNovo.ModeloId = codigoModelo;
                                modeloNovo.ModalidadeId = modalidade.ModalidadeId;
                                modeloNovo.CategoriaId = modalidade.CategoriaId;
                                modeloNovo.DataCriacao = DateTime.Now;
                                modeloNovo.DataAtualizacao = DateTime.Now;
                                modeloNovo.FlagExcluido = false;

                                ModeloCategoriaModalidade.Inserir(modeloNovo);
                            }

                        }

                    }
                    catch
                    {
                        status.AdicionarErro("Erro ao atualizar a modalidade " + modalidade.ModalidadeId + " !");
                    }
                }

Analise o trecho de código acima. Qual é a complexidade deste algoritmo?

Mesmo sem saber os detalhes, é muito possível que este algoritmo seja O(n²). Dado uma lista de entrada, ela percorre todos os itens e ainda efetua uma lógica sobre itens relacionados a cada entrada.

Quer dizer que se o item listaNovosRelacionamentos for extremamente grande, a tendência é que o tempo deste algoritmo seja completamente inviável.

Veja o gráfico referente a um algoritmo n²:

O exercício é: será que é possível melhorar a eficiência deste algoritmo sabendo disto?

Conclusão

É extremamente importante entender os conceitos básicos de algoritmos e também de estrutura de dados para trabalhar com isto no dia a dia.

A notação Big-O é muito importante para nos tornarmos mais profissionais. Evolua para outras notações como Omega-Q, Theta-O

Espero ter conseguido passar de uma forma mais introdutória este conceito. Em breve entrarei com novos posts para a continuação do assunto.

Grande abraço!

Testes de Carga com JMeter

Sempre que criamos uma solução precisamos garantir sua execução conforme a expectativa através de testes. Seja no momento do desenvolvimento (ou antes disso), durante a fase de pré-produção e até em produção, é extremamente importante pensar em continous testing de forma estratégica.

Para aqueles cenários onde há grande variação de carga, torna-se fundamental realizar os testes equivalentes com frequência.

Existem inúmeras ferramentas para isto, mas com certeza você não fugirá completamente de trabalhar com o famoso Apache JMeter.

The Apache JMeter™ application is open source software, a 100% pure Java application designed to load test functional behavior and measure performance. It was originally designed for testing Web Applications but has since expanded to other test functions.

Site oficial

Algo importante de já deixar destacado é que o JMeter não é um browser e nunca teve este objetivo; por este motivo, suas verificações não executam o retorno das eventuais consultas à páginas Web:

JMeter is not a browser, it works at protocol level. As far as web-services and remote services are concerned, JMeter looks like a browser (or rather, multiple browsers); however JMeter does not perform all the actions supported by browsers. In particular, JMeter does not execute the Javascript found in HTML pages. Nor does it render the HTML pages as a browser does (it’s possible to view the response as HTML etc., but the timings are not included in any samples, and only one sample in one thread is ever displayed at a time).

Como executar os testes de carga utilizando JMeter?

Todos os exemplos levam em consideração que você já efetuou o download da ferramenta.

Para facilitar, gravei um vídeo de exemplo com as explicações necessárias.

Até a próxima!

Desenvolvido em WordPress & Tema por Anders Norén