Fala, pessoal! Tudo certo?

Hoje eu quero compartilhar com vocês sobre um tópico que venho reforçando e estudando há um tempo. É algo que envolve custo de processamento... E um pouco da destemida matemática. Não se assuste! Eu te garanto que você sair daqui entendendo o básico e caro queira aprofundar darei algumas dicas no final. Ah, e não sou especialista na área, mas sou apenas um nerd como você que de desenvolve softwares. =)

O assunto é um pouco denso, mas tentei resumir o máximo possível. Pegue um café e bora lá.

Complexidade de Algoritmos

Quando se fala em complexidade, a primeira imagem que vem à mente pode ser um emaranhado de códigos, dando vida a aplicativos como Netflix, Instagram, TikTok, Youtube e games "AAA". Mas, a verdade é que a complexidade se trata de algo mais específico e mensurável. Aí que vem a tal notação assintótica.

A notação assintótica serve para calcular o tempo que um código demora para retornar um resultado ou a quantidade de memória que ele precisa. É uma forma de medir e entender o comportamento do código em diferentes cenários.

O Big O, ou "O-Grande", é a métrica mais conhecida e utilizada para medir o pior caso possível em termos de tempo e memória. Ou seja, ele indica o tempo máximo que o código pode levar para executar ou a quantidade máxima de memória que ele pode consumir.

Outras métricas importantes são:

Big Theta: Mede a média de consumo de memória e tempo de execução.
Big Omega: Indica o melhor cenário possível em termos de tempo e espaço.

Mas, aqui na publicação, nós iremos focar no Big O e especificamente em complexidade de tempo.

Vamos reforçar e pegar uma referência antes de aprofundar. De acordo com Mcdowell, autora do livro "Cracking the code interview", ela diz que:

"[...]Big O é uma língua e métrica que usamos para descrever a eficiência de algoritmos.[...]" - Cracking the code interview, pg. 38

"Eficiência" é a palavra-chave na frase de Mcdowell, pois há alguns cenários em queremos escrever algoritmos performáticos. Repare no conjunto "alguns cenários", pois hoje no mercado é difícil de ver um desenvolvedor trabalhar com otimização de códigos visto que os próprios compiladores já fazem parcialmente uma otimização para nós (ex. pesquise por LLVM) e como estamos em um mundo focado em entregas contínuas (alô Scrum) é melhor escrever um código modular, legível e fácil de testar. Ah, e fazer um serviço escalar horizontalmente é geralmente mais fácil e barato do que gastar um tempo otimizando bit por bit.

Mas, por quê então estudar complexidade de algoritmos se deixar um código modular, fácil de testar e legível é aparentemente mais importante? Não é meio contraditório esse artigo?

Entrevistas em big techs* requerem que os entrevistados resolvam problemas técnicos em white board e também auxiliará no dia-a-dia a entender qual será o comportamente aproximado de cada método / função, pois códigos em produção são demasiadamente complexos e saber analisar ajudará a fazer manutenção e até mesmo a modularizar e deixar testável. Mas, um ponto que sinto, um feeling, é que game dev geralmente precisa de um pouco de atenção nesse ponto, mas talvez não seja um fato.

*Reforço que não sou especialista no assunto e apenas um nerd que gosta de compartilhar conhecimento, pois nunca fiz uma entrevista em uma big tech, mas curto programação competitiva.

Exemplo de um cenário

Imagine que você contém a seguinte lista em python:

nums = [1, 2, 3, 5, 8, 13]

Como é que você poderá encontrar um certo x número o mais rápido possível?

Uma alternativa é olhar da esquerda para à direita, ou seja, um por um.

def linear_search(nums, x):
    result = None
    
    for e in nums:
        if e == x:
            result = e
    
    return result

Esse algoritmo é conhecido por ser chamado de "busca linear", pois como o próprio nome diz, nós iremos olhar todos os elementos da nossa lista de entrada nums. Como nós iremos olhar todos elementos a complexidade e se imaginarmos que o elemento que a gente quer é o 13 ou um elemento que não está na lista são os piores casos possíveis então o crescimento é em ordem de n e usando a notação Big O, nós falaremos que a complexidade é O(n).

Uma outra abordagem que pode ser mais rápida é seguir o principio que utilizavamos naquelas listas telefônicas (quem lembra?), pois nós começávamos do meio do livro e via se um determinado telefone de uma empresa ou pessoa está antes ou depois em relação a aquela página e quem sabe, por sorte, já está nessa página. Se não estiver, então nós dividimos pela metade algum dos lados... Se o número estiver nas páginas anteriores ou depois, nós iremos pegar a parcela anterior ou a próxima pela metade e iremos repetindo até chegar no resultado. Ah, e por curiosidade nós chamamos desse método de dividir para conquistar.

Implementando a lógica seria a seguinte:

def binary_search(nums, x):
    middle_index = len(nums) // 2
    
    if nums[middle_index] == x:
        return x
    elif len(nums) == 1:
        return None
    elif x < nums[middle_index]:
        left_side = nums[0:middle_index]
        return binary_search(left_side, x)
    
    right_side = nums[middle_index:]
    return binary_search(right_side, x)

A complexidade de tempo desse algoritmo será O(log(n)), pois se fizermos o teste de mesa:

Queremos buscar o 3

nums_atual = [1, 2, 3, 5, 8, 13] | middle = 5 e 5 > 3, logo vamos segmentar em 2 o nums_atual
nums_atual = [1, 2, 3] | middle = 2... Vamos repetir e quebrar o lado direito da lista!
nums_atual = [3] | middle = 3... Achamos!

Vamos agora fazer uma conta matemática para provar e como chegar nesse O(log(n)) e para quem também notou, eu irei explicar do o porquê de não colocar a base no logaritmo.

Tamanho da lista = 6 | Passo = 1
Tamanho da lista = 3 | Passo = 2
Tamanho da lista = 1 | Passo = 3

É igual a:

$n, n/2, n/4, ... => n, n/2, n/(2 ^ 2), ... => n/(2 ^ k)$

Agora se resgatarmos que a cada divisão na nossa sequência podemos dizer que uma hora sobrará o elemento que queremos... Apenas um único elemento:

$n/(2 ^ k) = 1$

Então aplicaremos algumas regras da matemática:

$n = 2 ^ k$

E podemos aplicar a regra dos logaritmos na base 2, pois já que dividimos toda hora por 2:

$log(n) = log(2 ^ k)$

Então:

$log(n) = k*log(2)$

E repare que não colocamos a base 2 na escrita formal, pois é uma convenção que utilizamos na ciência da computação e lembrando uma regrinha da matemática que qualquer logaritmo na base x com valor x é 1:

O resultado final será:

$log(n) = k$

Onde k é a quantidade de passos no Big O para achar o nosso valor.

Ufa, difícil né? Mas espero que tenha pegado a ideia básica de como é calculado a complexidade.

Testando as nossas notações

Vamos validar agora? Resgatando o assunto anterior. Imagine que nosso nums terá tamanho 1000. Vamos reparar a velocidade da busca linear vs busca binária.

linear_search => O(n); O(1000) terá 1000 passos

binary_search => O(log(n)); O(log(1000)) terá aproximadamente 10 passos

Por fim, podemos concluir que ela é mais rápida que a busca linear? Aí que vem a bomba. A resposta também é: depende. E não estou te enrolando. Se o tamanho de n for cada vez mais próximo de 0, a execução do código não surtirá tanto efeito. E há casos que a recursão em algumas linguagens de programação acaba tendo que gastar mais tempo para alocar um stack frame do que iterar uma lista inteira. Por isso que chamamos de anotação assintótica. Ela serve para dar uma estimativa do tempo e o espaço em relação execução dos nossos códigos.

Em resumo, tudo vai depender das ferramentas que você estiver utilizando para desenvolver o seu algoritmo, seja o hardware (ex. cpu, bus, gpu e etc) e software (ex. compilador, framework de paralelismo de gpu, s.o., etc). Aqui nós tentamos fazer uma estimativa e não um valor exato devido a essas interferências.

Escalas de Complexidade

Existem diversas escalas de complexidade e é mais popular o pessoal pegar em relação a úm único input (lista) e dizer em relação a ela, mas não é só isso que existe.

A ordem do mais rápido ao mais lento será: O(log(n)), O(n), O(n*log(n)), O(n^2), O(2^n) e O(n!).

Existem cenários em que podemos ter como O(sqrt(n)) e O(n+m). Um exemplo de O(sqrt(n)) é quando queremos achar a raíz quadrada de n e então começamos a iterar de 1 à sqrt(n) que é o próprio resultado de passos.

Conclusão

Essa é o meu primeiro post e uma introdução a complexidade de algoritmos focando no básico do básico que é o tempo versus uma única entrada (input). Há outras várias formas de calcular, como o Big Theta e Big Omega, e usar 2 ou mais inputs de tamanhos distintos.

Caso eu tenha errado algo no texto ou discorde de algo, por favor, me faça um feedback construtivo que irei adorar e aprender mais.

E caso também queira aprofundar nos tópicos, eu posso tentar escrever a parte 2. Ah, e há o livro do Thomas Cormen que é o clássico das faculdades de computação, pois lá ele aprofunda muito academicamente nesse tópico. Já para nós profissionais que gostam de programação competitiva ou que queira tentar entrar uma big tech, há o "Cracking the code interview" da Gayle Mcdowell que usei como base.

Valeu! =)

Só um detalhe, que é uma confusão que muitos fazem: complexidade não mede o tempo de execução. O único jeito de saber o tempo exato que um programa leva para executar é testando-o em condições reais.

O que funções como o Big-O fazem é determinar o "trabalho" necessário para executar o algoritmo. Na verdade, para ser mais exato, o Big-O determina o quanto esse "trabalho" aumenta conforme os dados de entrada crescem e se aproximam do infinito. É um conceito matemático bem abstrato que foi adaptado para a computação (inclusive, a definição matemática é muito mais ampla e genérica).

Como dito aqui:

Big O is not used for comparing run times, but for comparing how those run times scale as the input size grows.

Ou seja, Big-O não é usado para comparar o tempo de execução, mas sim para comparar como esses tempos aumentam conforme o tamanho da entrada cresce. Ele não diz se o algoritmo é mais rápido que outro. Ele só diz como essa "velocidade" muda quando o tamanho do problema aumenta.

Se eu digo que um algoritmo é O(n) e outro é O(n²), quer dizer que a quantidade de operações (de "trabalho executado") do primeiro aumenta em uma escala menor se comparado ao segundo, conforme o "n" (o tamanho da entrada, ou a quantidade de dados que serão processados) aumenta.

Mas isso não diz nada sobre o tempo que eles levam para executar. Por exemplo, se o primeiro faz operações mais demoradas (como escrever em arquivos) e o segundo só faz cálculos simples, pode ser que o primeiro seja até mais lento, mesmo executando menos operações. De novo: o tempo de execução só pode ser medido testando o código em condições reais, e não é isso que a complexidade de algoritmos mede. Inclusive, podemos até ter dois algoritmos O(n) que levam tempos completamente diferentes para executar.

Por fim, podemos usar a complexidade para medir diferentes aspectos, os mais comuns são tempo e espaço. Por exemplo, um algoritmo pode ser O(logn) em termos de "tempo" (lembrando que não quer dizer que mede o tempo, e sim como ele aumenta conforme o tamanho da entrada cresce) e O(n²) em termos de espaço (o algoritmo pode exigir a alocação de estruturas auxiliares que ocupam um espaço quadrático em relação à entrada, gastando mais memória).

Ou seja, complexidade é uma ferramenta para analisar algoritmos, e pode ser usado como um fator de decisão para escolha e avaliação. Vc pode ter uma ideia do tempo, ou se haverá memória suficiente, e já descartar os piores, por exemplo. Mas não dispensa o teste em condições reais, que no fim é o que vale. Afinal, funções como o Big-O são assintóticas, o que quer dizer que estão interessadas no comportamento "de longo prazo" (quando a entrada se aproxima do infinito). E como na prática não lidamos com dados infinitos, sempre precisa testar com dados reais. Inclusive, pode ter casos em que tanto faz, pois para poucos dados, tudo é rápido.

Para saber mais:

Complexidade de algoritmos. Que bicho é esse?

Complexidade de Algoritmos

Exemplo de um cenário

Testando as nossas notações

Escalas de Complexidade

Conclusão