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!