Complexidade de Algoritmos de uma forma intuitiva · pedrosoares

Introdução

Este artigo é baseado na apresentação "Complexidade de Algoritmos de uma forma intuitiva" que foi ministrado por mim no Front-End Day 2024, que aconteceu em Fortaleza CE, e tem como objetivo desmistificar esse tema tão importante na Ciência da Computação.
Durante a graduação, participei da Maratona de Programação da SBC, uma competição universitária de Algoritmos e Estruturas de Dados. Essa experiência aprofundou meu conhecimento nesse tema muitas vezes temido por desenvolvedores. Minha missão é apresentar esse assunto de forma didática, utilizando a matemática apenas quando é essencial para entender a notação assintótica. Mas o que é notação assintótica? Calma, vamos desmistificar tudo neste artigo.

Pré-requisitos

Para entender este artigo da melhor forma, não há pré-requisitos formais de matemática avançada. O texto propõe desmistificar o tema da complexidade de algoritmos de forma intuitiva, utilizando a matemática apenas quando essencial para explicar a notação assintótica, assunto que veremos mais na frente.

No entanto, ter uma compreensão básica dos seguintes conceitos pode ser útil:

Lógica de programação: Familiaridade com conceitos básicos de programação, como sequências, repetições (loops) e estruturas condicionais (if/else).
Estruturas de dados (opcional): Uma noção básica de Estrutura de Dados pode ajudar a entender melhor os exemplos, mas não é estritamente necessário. Se você souber como trabalhar com arrays e objetos será o suficiente.
Javascript (opcional): A familiaridade com Javascript é útil, pois os exemplos de código neste artigo serão apresentados nessa linguagem. Essa apresentação foi feita em um evento de Front-End, por esse motivo todos os exemplos foram escritos em Javascript.

Algoritmos? O que são ? Onde vivem ?

Um algoritmo é como uma receita de bolo: uma sequência finita de passos bem definidos e ordenados que, quando executados, resolvem um problema. Ele pode receber dados de entrada, processá-los e gerar uma ou mais saídas como resultado.

flowchart LR
    B[/Entrada/] --> C[Processamento]
    C --> D[/Saída/]

Por que Analisar Algoritmos?

Analisar algoritmos é crucial em diversas situações:

Desenvolvimento de Aplicações: Para garantir que nossos programas sejam eficientes.
Pesquisas Acadêmicas: Para comparar e avaliar diferentes soluções para um problema.
Processos Seletivos: Muitas empresas avaliam o conhecimento de análise de algoritmos dos candidatos. Além de resolver o problema, provavelmente o entrevistador vai pedir a complexidade da solução.

Como Analisamos Algoritmos ?

Existem algumas formas de analisar algoritmos, uma delas é através do Benchmark.

O Benchmark é uma técnica que consiste em medir o tempo de execução de um algoritmo em um ambiente específico.

Para ilustrar o conceito de Benchmark de forma simples, imagine que desejamos comparar a eficiência de duas abordagens para somar os elementos de um array: utilizando um laço for e utilizando a função reduce. Nosso objetivo é identificar qual das duas operações consome menos tempo de execução:

// Função utilizando for loop
function sumWithForLoop(array) {
  let sum = 0;
  for (let i = 0; i < array.length; i++) {
    sum += array[i];
  }
  return sum;
}

// Função utilizando reduce
function sumWithReduce(array) {
  return array.reduce((acc, value) => acc + value, 0);
}

Agora, precisamos apenas criar um utilitário que faz o benchmark das duas funções e no fim teremos o tempo em ms que cada uma delas levou para somar o array de números.

// Função para realizar o benchmark
function benchmark(func, array) {
  const start = performance.now();
  func(array);
  const end = performance.now();
  return end - start;
}
// Cria um array de 1 milhão de números aleatórios
const array = Array.from({ length: 1000000 }, () => Math.floor(Math.random() * 100));
// Realiza o benchmark para ambas as funções
const forLoopTime = benchmark(sumWithForLoop, array);
const reduceTime = benchmark(sumWithReduce, array);
// Exibe os resultados
console.log(`Tempo com for loop: ${forLoopTime} ms`);
console.log(`Tempo com reduce: ${reduceTime} ms`);

O Benchmark é uma técnica interessante e bastante utilizada. No entanto, essa abordagem tem algumas desvantagens:

Variabilidade nos Resultados: Fatores externos, como a carga do sistema e outros processos em execução, podem afetar os resultados. Esse foi o resultado do nosso benchmark em 3 execuções:

➜  node benchmark.js 
Tempo com for loop: 2.3145129999611527 ms
Tempo com reduce: 6.602074000053108 ms
➜  node benchmark.js
Tempo com for loop: 1.833701999974437 ms
Tempo com reduce: 6.053470999933779 ms
➜ node benchmark.js
Tempo com for loop: 1.7311650000046939 ms
Tempo com reduce: 5.934331999975257 ms

Contexto Específico: O Benchmark reflete o desempenho em um cenário particular (tipo de dados, tamanho do problema, hardware, linguagem de programação), o que pode não ser representativo de outras situações.

"Trabalhoso": Realizar um benchmark de cada função desenvolvida seria excessivamente trabalhoso. Na próxima seção, exploraremos um método mais simples para avaliar a complexidade do código.

Notação assintótica

É usada para medir como o tempo de execução ou espaço requerido (memória) de um algoritmo cresce à medida que o tamanho da entrada cresce. A notação assintótica é independente da máquina e da linguagem de programação utilizada e foca na ordem de grandeza da quantidade de passos executados por um algoritmo, em relação ao tamanho da entrada. Vamos tentar entender através de exemplos.

Soma de Elementos de um Array

Vamos analisar o exemplo da soma dos elementos do array novamente.

function sum(array) {
  let sum = 0;
  for (let i = 0; i < array.length; i++) {
    sum += array[i];
  }
  return sum;
}

A ideia é contar quantas vezes cada linha é executada:

let sum = 0;: Uma única atribuição (1 passo).
for (let i = 0; i < array.length; i++): Detalharemos a quantidade de vezes que essa linha é executada posteriormente, pois ela pode causar uma certa confusão.
sum += array[i];: A quantidade de execuções está diretamente ligada ao número de iterações do loop for. Se o array tiver 10 elementos, a linha será executada 10 vezes; se tiver 100, será executada 100 vezes. Podemos dizer que essa linha é executada n vezes, onde n representa o tamanho do array. (n passos).
return sum: Uma única execução (1 passo).

No laço for (let i = 0; i < array.length; i++), observe que três ações principais ocorrem: a inicialização da variável i com o valor 0 (feita apenas uma vez, no começo), a verificação da condição i < array.length (realizada a cada iteração, incluindo uma vez extra para constatar que a condição falhou e o loop deve terminar, totalizando n+1 verificações se o array tem n elementos), e o incremento de i (executado ao final de cada iteração, n vezes).
Portanto, a linha do for em si contribui com 1 passo (inicialização) + (n + 1) passos (condição) + n passos (incremento), resultando em um total de $2n + 2$ passos.

Finalmente, podemos dizer que o número de passos que a função gasta é a soma dos passos de cada linha. Podemos representar isso a partir de uma função $T(n)$ , onde $n$ é o tamanho do array.

function sum(array) {
  let sum = 0; // 1 passo
  for (let i = 0; i < array.length; i++) { // 2n + 2 passos
    sum += array[i]; // n passos
  }
  return sum; // 1 passo
}

$T(n) = 1 + 2n + 2 + n + 1 = 3n + 4$ .
$T(n) = 3n + 4$ .

Podemos visualizar isso como uma função linear onde
$n$ é o tamanho do array e $T(n)$ é o número de passos que a função leva até o fim da sua execução.

n	T(n) = 3n + 4
2	10
3	13
4	16
5	19

Dizemos que esse algoritmo tem complexidade linear, pois o tempo de execução cresce linearmente com o tamanho da entrada n. Na notação assintótica, podemos representar a complexidade desse algoritmo como $O(n)$ (Leia O de n). Cheguei nesse resultado aplicando 3 regrinhas simples:

Ignore constantes → $𝑂(3𝑛)$ é $O(n)$
Termo dominante vence → O(n² + n + 1) é O(n²)
Apenas o pior caso importa → Na notação O (Big O), estamos analisando a complexidade do algoritmo no seu pior caso. Existem outras notações para analisar o melhor caso e caso médio, porém elas não fazem parte do escopo deste artigo.

Como ignoramos constantes e termos de menor ordem para focar apenas no fator dominante de crescimento, chegamos a conclusão que $O(3n + 4)$ = $O(n)$ . E se você pensar bem, qualquer loop que tenha apenas execução de constantes a cada iteração vai ter complexidade linear, porque qualquer constante vezes $n$ é $O(n)$ . Existe toda uma demonstração matemática para provar o motivo de eliminarmos as constantes e termos de menor grau, porém foge do escopo deste artigo e acho que já mostrei muita matemática até o momento.

No dia dia, essa é a metodologia que eu uso para analisar a complexidade de um algoritmo:

Foque nas Repetições (Loops): As repetições são geralmente os trechos de código que mais contribuem para a complexidade.
Verifique a Complexidade de Métodos de Terceiros: Se você estiver utilizando métodos de bibliotecas externas ou nativas da linguagem, é importante conhecer a complexidade deles.
Foque no termo de maior grau: Como já falado anteriormente, ignore termos de menor grau e constantes.

Exemplos

Exibir primeiro elemento do array

function printFirstElement(array) {
  console.log(array[0]);
}

Perceba que independente do tamanho do array, executamos apenas um console.log na primeira linha. É uma operação constante, podemos representar a complexidade desse algoritmo por $O(1)$ .

Busca em um array de inteiros

function find(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}

Nesta função, a dúvida surge porque, se o target buscado estiver no início do array, o loop for executará apenas uma vez. Contudo, o pior caso ocorre quando o target não está presente no array, forçando o loop a percorrer todos os $n$ elementos. Portanto, a complexidade deste algoritmo é $O(n)$ , pois no pior caso, ele realiza um número de operações proporcional ao tamanho do array.

Também podemos resolver esse problema utilizando o método do array find.

function find(array, target) {
  return array.find((item) => item === target);
}

Nesse caso é interessante saber a complexidade dos métodos da linguagem. No fim o método find internamente vai iterar por todos os itens do array até a condição ser satisfeita, o que nos levará a complexidade de $O(n)$ .

Checar se o array tem números repetidos

function hasDuplicates(array) {
  for (let i = 0; i < array.length; i++) {
    const isDuplicated = array.some(
      (item, itemIndex) => item === array[i] && itemIndex !== i
    );

    if (isDuplicated) {
      return true;
    }
  }
  return false;
}

Esse é um caso interessante, vamos tentar entender dividendo em duas etapas:

O for externo itera por todos os elementos do array. Isso já é $O(n)$ .
Dentro dele, o .some() também pode iterar por até todos os elementos do array no pior caso (quando não encontra nenhum duplicado logo de início). Isso é O(n) também.

Isso resulta em n chamadas ao some, cada uma fazendo até n comparações. Então temos como complexidade final: $O(n)\cdotO(n)=$ O(n²).

Podemos otimizar a solução desse algoritmo usando a Estrutura de Dados Set do Javascript.

function hasDuplicates(array) {
  const seen = new Set();
  for (const item of array) {
    if (seen.has(item)) {
      return true;
    }
    seen.add(item);
  }
  return false;
}

Cada Set.has() e Set.add() são operações $O(1)$ em média. Isso faz com que a nossa solução seja $O(n)$ .

Transformar um array em um objeto

// Queremos sair desse input
const input = [
  { id: 1, name: 'John' },
  { id: 2, name: 'Jane' },
  { id: 3, name: 'Doe' },
];

// Para esse output
const output = {
  1: { id: 1, name: 'John' },
  2: { id: 2, name: 'Jane' },
  3: { id: 3, name: 'Doe' },
};

function arrayToObject(array) {
  return array.reduce((acc, item) => {
    return {
      ...acc,
      [item.id]: item,
    };
  }, {});
}

Parece $O(n)$ à primeira vista, certo? O reduce percorre o array uma vez ( $O(n)$ ) e dentro dele, você está:

Copiando todas as chaves de acc com o spread ...acc
Adicionando uma nova chave[item.id]: item

O problema está no ...acc. O operador de spread ...acc copia todas as chaves do acumulador anterior para um novo objeto a cada iteração. O que isso significa? Vamos ilustrar o que acontece em cada iteração:

Primeira iteração:
- acc tem 0 chaves → copiar 0 → custo: $O(0)$
Segunda iteração:
- acc tem 1 chave → copiar 1 → custo: $O(1)$
Terceira iteração:
- acc tem 2 chaves → copiar 2 → custo: $O(2)$
...
Última iteração (n-ésima):
- acc tem (n-1) chaves → copiar n-1 → custo: $O(n - 1)$

Somando tudo temos:

$T(n) = 0+1+2+...+(n−1) = \frac{n(n - 1)}{2} =$ O(n²)

Apenas um detalhe do operador spread deixou a nossa solução O(n²).

Transformar um array em um objeto (Solução O(n))

function arrayToObject(array) {
  return array.reduce((acc, item) => {
    acc[item.id] = item;
    return acc;
  }, {});
}

Chegamos na solução $O(n)$ pelos seguintes fatos:

Aqui, acc[item.id] = item é $O(1)$ .
O reduce ainda é $O(n)$ .
No fim temos apenas operações constantes dentro do loop.

Big O - Curvas de crescimento mais comuns

Notação Big O	Nome da Complexidade	Crescimento	Exemplo típico
O(1)	Constante	Não cresce com o tamanho da entrada	Acesso direto a um elemento de array
O(log n)	Logarítmica	Cresce lentamente	Busca binária em array ordenado
O(n)	Linear	Cresce proporcionalmente ao tamanho da entrada	Percorrer um array com `for`
O(n log n)	Linearítmica	Cresce um pouco mais rápido que linear	Ordenações eficientes (merge sort, quicksort)
O(n²)	Quadrática	Cresce rapidamente com pares de elementos	Duplo `for`, algoritmos ingênuos de ordenação
O(n³)	Cúbica	Crescimento ainda mais intenso	Triplos `for`, problemas de grafos pesados
O(2ⁿ)	Exponencial	Crescimento explosivo	Subconjuntos possíveis, algoritmos de força bruta
O(n!)	Fatorial	Crescimento extremo	Algoritmo de permutação completa

Reflexões finais

A notação Big O abstrai detalhes e foca em como o tempo ou espaço crescem com o tamanho da entrada. Útil para decidir: devo usar um algoritmo de ordenação $O(n log n)$ ou posso me dar ao luxo de um O(n²)? Cuidado, nem sempre o algoritmo mais rápido vai ser o melhor, as vezes estamos trabalhando com um volume pequeno de dados e sinceramente pode ser super tranquilo usar um algoritmo menos eficiente e deixar o código mais compreensivo. Então cabe a você analisar o tamanho da entrada e decidir a melhor solução para o problema que você está enfrentando.

Tive alguns problemas para representar potências no formato latex. Sempre que tento representar O(n²) tenho como resultado $O(n^2)$ . Desculpem pela confusão. No preview o resultado funcionou corretamente, porém na hora de publicar esse problema ocorreu várias vezes.