Quando se fala em algoritmos, muitos pensam logo em uma linguagem específica: C, Python, Java, JavaScript. Mas, antes de escolher qualquer linguagem, existe uma camada mais básica, que é como a ideia do algoritmo. Ou seja, como escrever o passo a passo de forma clara, organizada e independente de qualquer tecnologia específica.
É disso que trata essa parte: montar uma maneira padrão de apresentar algoritmos, usando um tipo de pseudocódigo. A ideia é ter uma “linguagem de meio de campo”: não é código de verdade que se joga num compilador, mas também não é português solto. É um misto dos dois, pensado para que qualquer pessoa com noção básica de programação consiga entender a lógica sem ficar presa à sintaxe de uma linguagem concreta.
Imagine que três pessoas diferentes queiram explicar o mesmo algoritmo:
- uma escreve em C
- outra escreve em Python
- outra escreve em Java
As três versões fazem a mesma coisa, mas quem está aprendendo vai ter que entender três sintaxes, três jeitos de declarar variáveis, três estilos de laço. O risco é que a pessoa se perca nos detalhes da linguagem e não enxergue a ideia central do algoritmo.
Por isso se usa um pseudocódigo: uma linguagem simplificada, parecida com linguagens clássicas, mas sem detalhes de compilador, biblioteca padrão, tipos exatos etc. O que importa é:
- os comandos básicos;
- a forma como blocos de código são escritos;
- o jeito de expressar condições, repetições, chamadas de procedimentos;
- e alguma convenção mínima para vetores, matrizes, registros e ponteiros.
Essa padronização permite que toda a discussão sobre algoritmos gire em torno do raciocínio, não da sintaxe.
Blocos e indentação: quem está “dentro” de quem
Um conceito essencial é o de bloco de comandos.
Bloco é um conjunto de instruções que funcionam como uma unidade, o corpo de um se, o corpo de um enquanto, o conteúdo de um procedimento, e assim por diante.
Em muitas linguagens, blocos são marcados com palavras como begin e end ou com chaves { e }. Aqui, a ideia é usar algo que você provavelmente já viu:
Indentação (recuo na margem esquerda)
Funciona assim:
- um comando que controla um bloco (por exemplo, um
se ou um enquanto) aparece mais “para a esquerda”;
- tudo o que estiver logo abaixo, um pouco mais recuado, faz parte do bloco controlado por ele;
- quando o recuo volta, o bloco terminou.
É exatamente o estilo usado em linguagens como Python. Visualmente, fica muito mais fácil ver quais comandos pertencem a qual estrutura. Isso ajuda principalmente em algoritmos com vários níveis de aninhamento, por exemplo, um se dentro de um enquanto dentro de um para.
Atribuição: o famoso “recebe”
Outro ponto importante é a forma como se escreve a atribuição, isto é, o ato de colocar um valor dentro de uma variável.
Em vez de usar o sinal de igual simples, é comum escrever:
x := 5
Isso se lê como:
“x recebe 5”
O motivo de usar := é evitar confusão com matemática pura.
Em matemática, x = 5 é uma afirmação de que x é igual a 5, simétrico. Em programação, muitas vezes o igual significa “atribuí esse valor a essa variável”, que é uma operação assimétrica: o lado esquerdo é alterado, o lado direito é avaliado.
Com o :=, fica mais claro que se trata de uma ação: o valor anterior de x é substituído por um novo.
Podem aparecer expressões como:
soma := soma + x
i := i + 1
troca := A[i]
A[i] := A[j]
A[j] := troca
Todas elas seguem a mesma ideia: calcular o valor da expressão à direita e gravar o resultado na variável à esquerda.
Comandos de controle: decisões e repetições
Para que um algoritmo seja mais do que uma lista boba de comandos em sequência, ele precisa ser capaz de:
- tomar decisões (fazer algo se uma condição for verdadeira);
- repetir ações enquanto certas condições forem satisfeitas.
Os comandos mais comuns que aparecem nessa forma de apresentação de algoritmos são:
1. se ... então e se ... então ... senão
Eles representam o famoso if da maioria das linguagens.
Exemplo:
se x > 0 então
escreve("x é positivo")
Ou, com alternativa:
se x > 0 então
escreve("x é positivo")
senão
escreve("x é menor ou igual a zero")
A condição é alguma expressão lógica (comparações, combinações com e, ou, etc.).
O bloco identado abaixo de então só é executado se a condição for verdadeira.
O bloco abaixo de senão só é executado se a condição for falsa.
2. enquanto ... faça
Representa um laço de repetição condicionada:
enquanto aindaTemPratoSujo faça
lavaPrato()
verificaSeAindaTemPratoSujo()
A leitura é: enquanto a condição for verdadeira, execute o bloco.
Assim que a condição se tornar falsa, o laço termina.
Esse tipo de laço é muito útil quando não se sabe de antemão quantas repetições serão necessárias. É como dizer “enquanto o usuário não acertar a senha, continue pedindo”.
3. para ... faça
Representa um laço de repetição em que a quantidade de iterações é conhecida ou determinada por um intervalo:
para i de 1 até n faça
soma := soma + A[i]
Aqui a leitura é mais direta: o índice i percorre todos os valores de 1 até n, e para cada valor são executados os comandos do bloco. É o padrão quando se precisa percorrer elementos de um vetor, linhas de uma matriz etc.
4. pare
É um comando usado, dentro de um laço, para interromper a repetição antes do fim “natural”.
Por exemplo:
para i de 1 até n faça
se A[i] = x então
posicao := i
pare
Nesse caso, assim que o elemento procurado é encontrado, o pare interrompe o laço, mesmo que i ainda não tenha chegado a n.
Variáveis simples: números, caracteres, lógico
Nesse estilo de algoritmos, assume-se que existem alguns tipos básicos de dados:
- Inteiros: números sem parte decimal, positivos ou negativos.
- Reais: números com parte decimal.
- Caracteres: letras, dígitos, símbolos, normalmente representados entre aspas simples:
'a', 'Z', '7'.
- Booleanos (lógicos):
verdadeiro ou falso.
Uma variável é só um “nome” que aponta para uma posição de memória onde um valor desse tipo é armazenado.
Por exemplo:
i : inteiro
media: real
letra: caractere
ok : booleano
(As declarações formais nem sempre aparecem completas no pseudocódigo, mas esse é o espírito.)
Vetores: uma fileira de caixinhas numeradas
Um vetor é uma coleção de elementos todos do mesmo tipo, guardados em posições numeradas.
Você pode imaginar como uma fileira de caixinhas:
A[1], A[2], A[3], ..., A[n]
Cada posição é acessada por um índice. Alguns exemplos:
A[1] é o primeiro elemento.A[i] é o elemento da posição i, que pode variar ao longo de um laço.A[n] é o último.
É comum ver coisas como:
para i de 1 até n faça
soma := soma + A[i]
ou:
A[i] := A[i] + 10
O importante é perceber que, quando aparece S[1..n], por exemplo, isso representa um vetor S com índices indo de 1 até n.
Matrizes: uma espécie de planilha
Uma matriz é uma generalização do vetor: em vez de uma dimensão, são duas (linha e coluna). É como uma planilha de Excel:
B[linha, coluna]
Por exemplo, uma matriz com n linhas e n colunas pode ser escrita como:
Para percorrer todos os elementos, usa-se dois laços aninhados:
para i de 1 até n faça
para j de 1 até n faça
C[i, j] := A[i, j] + B[i, j]
Aqui, C[i, j] recebe a soma dos elementos de A e B na mesma posição.
Matrizes são fundamentais em algoritmos numéricos, gráficos, simulações físicas etc.
Registros: vários campos sob um só nome
Às vezes, guardar um único valor por variável não é suficiente.
Pense em um “aluno”:
- nome
- matrícula
- idade
- média
Faria pouco sentido ter quatro vetores separados e tentar ficar sincronizando os índices. Em vez disso, entra o conceito de registro (similar ao struct em C).
Um registro é um agrupamento de campos. A notação típica é:
aluno.nome
aluno.matricula
aluno.idade
aluno.media
Ou seja, aluno é o registro, nome é um dos campos.
Dentro de algoritmos, é comum ver coisas como:
T.chave
T.info
onde T é um registro e chave, info são campos.
Registros são a base para estruturas mais ricas, como listas de alunos, tabelas de produtos, cadastros etc.
Ponteiros: referências para registros
Agora entra um conceito que, de início, assusta um pouco, mas é crucial para certas estruturas de dados: o ponteiro.
Um ponteiro é uma variável cujo valor não é um número comum, nem um caractere; é um endereço de memória. Em vez de guardar diretamente os dados, o ponteiro “aponta” para onde os dados estão.
Uma analogia:
- o registro é a casa;
- o ponteiro é o endereço da casa anotado num papel.
A notação pode usar algo como:
pt↑.info
Aqui, pt é o ponteiro. O símbolo ↑ indica “o registro para o qual ele aponta”. E .info é um campo desse registro.
Então, pt↑.info significa:
“O campo info do registro cujo endereço está armazenado em pt.”
Isso é muito útil em estruturas como listas encadeadas, em que cada nó guarda não só dados, mas também um ponteiro para o próximo nó.
Procedimentos, funções e parâmetros por referência
Para organizar algoritmos, é comum dividir o código em sub-rotinas:
- procedimentos: executam uma ação, mas não devolvem diretamente um valor;
- funções: devolvem um valor (por exemplo, o resultado de um cálculo).
A passagem de parâmetros pode ser vista de duas maneiras principais:
Por valor
O procedimento recebe uma cópia do valor. Se ele alterar a variável dentro da sub-rotina, isso não se reflete fora.
Por referência
O procedimento recebe algo que permite acessar diretamente a variável original (por exemplo, o endereço dela). Se o procedimento alterar o parâmetro, a variável do chamador também é alterada.
Na forma de apresentação que estamos usando, é comum assumir passagem por referência. Isso torna natural que um procedimento possa modificar vetores, registros etc., sem precisar devolvê-los explicitamente.
Uma analogia simples:
- Por valor: você tira uma fotocópia de um documento e deixa a cópia com a pessoa; o original não muda.
- Por referência: você entrega o documento original; a pessoa pode riscar, corrigir, grampear, e quando ele volta está diferente.
Comentários: explicando em português o que o código faz
Junto do pseudocódigo, aparecem os comentários, geralmente marcados por um símbolo especial, como %.
Tudo o que vier depois desse símbolo, na mesma linha, é ignorado na interpretação do algoritmo, e serve apenas para seres humanos.
Por exemplo:
soma := 0 % zera o acumulador
para i de 1 até n faça
soma := soma + A[i] % adiciona o elemento i
Comentários ajudam muito a entender a intenção do algoritmo:
- explicar o que uma variável representa;
- indicar por que um laço termina em tal condição;
- apontar detalhes importantes que, só olhando o código, podem não ficar claros.
Para quem está estudando, vale a pena ler os comentários com calma, porque eles carregam a explicação em linguagem natural.
Um exemplo prático: inverter uma sequência em um vetor
Tudo isso ganha mais sentido com um exemplo.
Considere um vetor S[1..n] com n elementos. O objetivo é inverter a ordem desses elementos dentro do próprio vetor.
Se a sequência for:
S = [ 10, 20, 30, 40, 50 ]
quer-se obter:
S = [ 50, 40, 30, 20, 10 ]
A ideia intuitiva é:
- Trocar o primeiro com o último.
- Trocar o segundo com o penúltimo.
- Continuar assim até chegar no meio do vetor.
Não faz sentido trocar o elemento do meio com ele mesmo. Por isso, se n é ímpar, esse elemento central fica onde está.
Como transformar isso em pseudocódigo?
Primeiro, pensa-se em um laço:
- Vamos usar um índice
i começando em 1 e indo até a metade de n.
- Para cada
i, vamos trocar S[i] com S[n − i + 1].
Por que n − i + 1?
- Quando
i = 1, temos n − 1 + 1 = n, o último elemento.
- Quando
i = 2, temos n − 2 + 1 = n − 1, o penúltimo.
- E assim por diante.
A “metade de n” é formalizada usando a função piso (a parte inteira da divisão):
Se n = 5, por exemplo, ⌊5/2⌋ = 2 (a parte inteira de 2,5). Então i vai de 1 a 2:
- i = 1 → troca o 1º com o 5º;
- i = 2 → troca o 2º com o 4º;
- o 3º (do meio) permanece.
O pseudocódigo fica algo assim, em espírito:
para i de 1 até ⌊n/2⌋ faça
temp := S[i]
S[i] := S[n - i + 1]
S[n - i + 1] := temp
Repare na variável temp: ela é uma variável temporária usada para não perder o valor de S[i] enquanto se sobrescreve S[i] com S[n − i + 1]. É como usar um copo extra para trocar o conteúdo de dois copos com água, sem derramar.
Esse pequeno algoritmo mostra:
- como usar vetores;
- como usar o laço
para;
- como manipular índices;
- como usar atribuições e uma variável temporária;
- como a indentação deixa claro qual é o bloco repetido.
Recursividade
Quando o assunto é algoritmos, uma palavra que sempre aparece e causa certo arrepio em quem está começando é recursividade. Ela tem cara de conceito difícil, parece algo meio filosófico, mas a ideia central é bem direta: um procedimento que se chama a si mesmo para resolver versões menores do mesmo problema.
Dá para imaginar como uma pessoa que recebe uma tarefa complicada, divide em partes menores, passa uma parte para outra pessoa, que por sua vez divide de novo e assim por diante, até o pedaço ficar simples o suficiente para ser resolvido na hora. A recursão faz algo assim, só que todas “essas pessoas” são, na verdade, o mesmo procedimento sendo chamado várias vezes, com parâmetros diferentes.
O que é recursividade
Um algoritmo recursivo é aquele em que uma função ou procedimento, em algum ponto do seu corpo, chama a si próprio.
Para não virar um loop infinito, sempre aparecem dois ingredientes:
Casos base
Situações simples, em que o problema já está pequeno o bastante para ser resolvido diretamente, sem nova chamada.
Passo recursivo
Regras que dizem como transformar o problema grande em um ou mais problemas menores do mesmo tipo.
Se só existir passo recursivo, o algoritmo entra em chamada atrás de chamada e nunca termina. Se só existir caso base, não há recursão. O jogo está no equilíbrio entre os dois.
Exemplo clássico: o fatorial
Um exemplo muito usado para explicar recursividade é o fatorial de um número inteiro n ≥ 0.
Definição:
- 0! = 1
- 1! = 1
- n! = n × (n − 1)! para n ≥ 2
Ou seja, o fatorial de n é n vezes o fatorial de n − 1. A própria definição já é recursiva.
Se n = 5, por exemplo:
- 5! = 5 × 4!
- 4! = 4 × 3!
- 3! = 3 × 2!
- 2! = 2 × 1!
- 1! = 1
Quando o algoritmo recursivo é escrito, ele costuma seguir exatamente essa definição:
- Caso base: se n é 0 ou 1, retorna 1.
- Passo recursivo: se n é maior que 1, retorna n × fatorial(n − 1).
De forma conceitual:
função fat(n)
se n ≤ 1
devolve 1
senão
devolve n × fat(n − 1)
Cada chamada guarda uma “tarefa pendente”: “preciso multiplicar n pelo resultado da função em n − 1”. Essas tarefas ficam empilhadas na memória até atingir o caso base. Quando o caso base devolve 1, as multiplicações começam a ser feitas na volta.
Essa combinação de “definição recursiva” com “prova por indução” é muito forte em matemática e programação: primeiro se mostra como resolver o problema para o caso simples, depois se mostra como resolver o caso geral supondo que o caso menor já está resolvido. A recursão traduz isso em código.
O que acontece nos bastidores da recursão
Visualmente, quando um procedimento recursivo é chamado, o computador:
- Guarda o estado atual da execução (variáveis locais, posição onde deve voltar) em uma pilha.
- Entra na nova chamada com parâmetros diferentes.
- Repete esse processo a cada chamada recursiva.
- Quando encontra um caso base, começa a “desempilhar”, voltando passo a passo.
Essa pilha é uma estrutura de dados do próprio sistema: o último a entrar é sempre o primeiro a sair. Por isso, em problemas com recursão muito profunda, pode acontecer de “estourar a pilha” (stack overflow), porque há chamadas demais pendentes ao mesmo tempo.
Do ponto de vista de quem está aprendendo, não é preciso dominar todos os detalhes de implementação da pilha para entender recursividade, mas é fundamental ter em mente que:
- cada chamada recursiva ocupa memória;
- recursão muito profunda exige cuidado;
- muitas vezes, um algoritmo recursivo elegante pode ser reescrito de forma iterativa (com laços) para economizar memória.
Outro exemplo: sequência de Fibonacci
Outro exemplo famoso é a sequência de Fibonacci:
- F(0) = 0
- F(1) = 1
- F(n) = F(n − 1) + F(n − 2), para n ≥ 2
Mais uma vez, a própria definição é recursiva. Um algoritmo simples copia isso exatamente:
função fib(n)
se n ≤ 1
devolve n
senão
devolve fib(n − 1) + fib(n − 2)
Esse código é curto e parece muito bonito, mas esconde um problema: explosão de chamadas. Cada fib(n) chama duas vezes a função para valores menores, que por sua vez chamam outras duas e assim por diante. O número de chamadas cresce de forma muito rápida, quase como 2.
Esse exemplo costuma ser usado para mostrar dois pontos:
- recursão pode deixar o código mais próximo da definição matemática;
- recursão inocente, sem cuidado, pode ter uma complexidade de tempo péssima.
Para resolver isso, é comum reescrever Fibonacci de forma iterativa ou usar técnicas como memoização, em que se guardam os resultados já calculados para evitar recomputações.
Exemplo visual: a Torre de Hanói
A Torre de Hanói é um quebra-cabeça perfeito para enxergar recursividade em ação.
Cenário:
- existem três pinos (A, B, C);
- vários discos de tamanhos diferentes empilhados no pino A, com o maior embaixo e o menor em cima;
- objetivo: mover toda a pilha para o pino B;
- regras: só é permitido mover um disco por vez e nunca se pode colocar um disco maior sobre um menor.
Parece complexo, mas recursão organiza o raciocínio.
Para n discos:
- mover os n − 1 discos de cima de A para C, usando B como apoio;
- mover o disco maior (o último) de A para B;
- mover os n − 1 discos de C para B, usando A como apoio.
Aqui aparecem claramente:
- o caso base: se n = 1, basta mover um disco de um pino a outro;
- o passo recursivo: resolver o problema com n discos supondo que existe uma solução para n − 1.
Cada chamada da função para n discos gera duas chamadas para n − 1 discos. O número total de movimentos cresce como 2 − 1, ou seja, rapidamente.
Esse problema é muito usado não só porque é visual, mas porque mostra bem o padrão:
“Para resolver o caso grande, imagine que já sabe resolver o caso menor.”
Essa frase é praticamente o coração da recursão.
Como pensar recursivamente
Para quem está começando, pensar recursivamente é quase como trocar o “modo manual” de raciocínio por um “modo declarativo”.
Em vez de ficar imaginando todos os passos de baixo nível, tenta-se responder a duas perguntas:
Qual é a versão mais simples desse problema?
Esse será o caso base.
Como posso reduzir o problema atual a uma ou mais versões menores do mesmo problema?
Esse será o passo recursivo.
Por exemplo, ao pensar no fatorial:
- caso simples: fatorial de 0 ou 1 é igual a 1;
- redução: fatorial de n é n vezes o fatorial de n − 1.
Na Torre de Hanói:
- caso simples: mover 1 disco de um pino para outro;
- redução: para n discos, mover n − 1 para o pino auxiliar, depois o maior, depois os n − 1 de volta.
Um ponto importante: é preciso garantir que essas reduções realmente aproximem o problema do caso base. Se o problema ficar do mesmo tamanho ou maior, não há progresso e a recursão nunca termina.
Relação entre recursão e laços
Quase todo algoritmo recursivo pode ser reescrito de forma iterativa, usando laços enquanto ou para.
No caso do fatorial, por exemplo, é simples escrever:
- começar com um acumulador igual a 1;
- multiplicar esse acumulador por 2, depois por 3, depois por 4, até chegar em n.
A recursão, nesse caso, não é a única opção, mas é uma forma natural de traduzir a definição matemática.
Há problemas em que a recursão facilita muito o raciocínio, como em árvores (percorrer uma árvore de diretórios, por exemplo) ou em algoritmos de divisão e conquista (quebrar o problema em subproblemas). Em outros, a recursão só complica ou gasta recursos à toa, e é melhor ficar nos laços.
De forma prática:
- recursão favorece clareza em muitos cenários;
- iteração costuma ser melhor em termos de uso de memória e, às vezes, de desempenho.
Alguns compiladores conseguem transformar internamente certas recursões em laços, principalmente nos casos de recursão de cauda, em que a chamada recursiva é a última instrução do procedimento. Isso reduz o custo de memória, mas depende de otimizações específicas.
Medindo o custo de algoritmos recursivos
Quando se analisa a eficiência de um algoritmo recursivo, uma técnica comum é:
- Contar quantas chamadas recursivas são feitas em função do tamanho da entrada.
- Calcular o custo de cada chamada isolada, sem considerar o custo das outras chamadas recursivas.
- Combinar as duas coisas para obter uma fórmula de tempo total.
No fatorial recursivo:
- cada chamada reduz n em 1;
- há n chamadas até chegar a 1;
- cada chamada faz, basicamente, uma multiplicação;
- resultado: tempo proporcional a n (complexidade linear).
Na Torre de Hanói:
- o número de movimentos satisfaz a relação T(n) = 2·T(n − 1) + 1;
- isso leva a T(n) = 2 − 1;
- resultado: tempo cresce de forma exponencial.
Na sequência de Fibonacci com a definição ingênua:
- cada
fib(n) chama fib(n − 1) e fib(n − 2);
- o número de chamadas cresce de forma aproximadamente proporcional a ϕ, onde ϕ é o número de ouro;
- o custo explode rapidamente.
Essa análise mostra que recursão não é sinônimo de lentidão, mas que é importante entender a relação de chamadas para não ser surpreendido por algoritmos aparentemente inocentes.
Quando usar recursão vale a pena
Alguns tipos de problemas praticamente “pedem” recursão, porque a estrutura interna deles é recursiva:
Estruturas em árvore
Percorrer pastas e arquivos em um sistema de arquivos; percorrer nós de uma árvore binária; interpretar expressões matemáticas aninhadas.
Dividir para conquistar
Ordenar um vetor quebrando-o em dois (como no mergesort ou quicksort); encontrar o k-ésimo menor elemento dividindo o problema em subvetores.
Problemas definidos recursivamente
Fatorial, Fibonacci, entre outros, em que a definição formal já usa o caso anterior.
Em todos esses casos, a recursão tende a dar um código mais curto e mais próximo da descrição conceitual do problema.
Cuidados ao usar recursividade
Alguns cuidados práticos:
Definir claramente o caso base
Sem caso base bem definido, o algoritmo não termina. E se o caso base estiver errado, pode terminar com resposta errada.
Garantir progresso real
Toda chamada recursiva deve aproximar a entrada do caso base. Reduzir n, encurtar uma lista, subir ou descer em uma árvore.
Pensar na profundidade da recursão
Em entradas muito grandes, o número de chamadas aninhadas pode ser alto demais e estourar a pilha de execução.
Avaliar o custo de tempo
É importante saber se a recursão gera apenas uma chamada por nível (como no fatorial) ou várias (como em Fibonacci ingênuo ou Torre de Hanói).
Reescrever recursões perigosas
Quando a recursão gera explosão de chamadas, vale buscar alternativas iterativas ou técnicas de otimização.
Recursividade não é só uma técnica de programação, é um jeito de enxergar problemas. Sempre que um problema puder ser descrito como:
“versão simples” + “versão geral em termos de versões menores”
há espaço para um raciocínio recursivo.
Dominar recursão ajuda a:
- compreender melhor provas por indução;
- entender estruturas como árvores, grafos e expressões aninhadas;
- escrever algoritmos mais próximos da descrição matemática.
Para quem está começando,:
- praticar com exemplos simples (fatorial, máximo de um vetor, soma de elementos);
- depois avançar para exemplos mais ricos (árvores, Hanói, algoritmos de ordenação recursivos);
- sempre parar para identificar o caso base e o passo recursivo, como se estivesse contando uma história que vai se simplificando até chegar no final natural.
Quando essa forma de pensar entra no repertório, recursividade deixa de parecer um “bicho de sete cabeças” e passa a ser mais uma ferramenta, poderosa, ao lado dos laços, das estruturas de dados e de todo o resto que compõe o universo dos algoritmos.
Algoritmo eficiente
Quando alguém começa a estudar programação, sempre surge aquela pergunta que parece meio abstrata: “esse algoritmo é eficiente?”. Todo mundo entende o que é “funcionar” ou “não funcionar”, mas medir o quão pesado é um algoritmo já parece conversa de matemático. É justamente disso que trata o tema complexidade de algoritmos.
Imaginar que cada algoritmo tem um “custo” para ser rodado, e que esse custo depende do tamanho da entrada. Não é a mesma coisa somar 10 números e somar 10 milhões. Não é a mesma coisa procurar um nome em uma lista com 20 pessoas e em uma com 20 milhões. Complexidade é a forma organizada de responder a perguntas como:
- Quantos passos esse algoritmo executa quando a entrada cresce?
- Quanto tempo ele tende a gastar?
- Quanta memória ele ocupa?
Tudo isso sem precisar ficar medindo com cronômetro em cada computador diferente.
À primeira vista, alguém pode pensar: “por que não roda o programa e mede o tempo?”. Essa estratégia até funciona em testes práticos, mas tem vários problemas.
O tempo medido depende de coisas que não têm nada a ver com o algoritmo em si:
- processador mais rápido ou mais lento;
- quantidade de memória;
- se o sistema operacional está ocupado com outras tarefas;
- linguagem e compilador usados.
Um mesmo algoritmo pode parecer mais rápido em um computador e mais lento em outro, apenas por causa do hardware ou da implementação. Fica difícil comparar duas ideias de solução usando só segundos como unidade.
Por isso, quando se fala de complexidade, entra outro tipo de análise, teórica, baseado em um modelo idealizado. Em vez de se preocupar com o tempo em segundos, olha-se para o número de passos que o algoritmo executa, em função do tamanho da entrada.
Tamanho da entrada: o tal do “n”
Quase sempre aparece uma letrinha para representar o tamanho do problema. Em geral se utiliza n:
- se o algoritmo recebe uma lista, n é o número de elementos;
- se mexe com uma matriz quadrada, n pode ser a quantidade de linhas (e colunas);
- se trata de um texto, n pode ser a quantidade de caracteres;
- se trabalha com um grafo, n pode ser o número de vértices ou de arestas, conforme o contexto.
Complexidade de tempo passa a ser uma função como:
- T(n) = número de passos que o algoritmo executa para uma entrada de tamanho n.
A grande pergunta deixa de ser “quantos segundos”, e vira “como T(n) cresce quando n aumenta”.
O que é um “passo” no algoritmo
Para conseguir conversar sobre complexidade sem cair em detalhes esotéricos, costuma-se definir um passo como um pequeno bloco de operações básicas:
- uma soma;
- uma comparação;
- uma atribuição de variável;
- acessar uma posição de vetor;
- coisas desse nível.
O truque é agrupar essas operações em blocos que se repetem muitas vezes. Em vez de contar uma por uma, diz-se que:
- determinado trecho é um passo;
- o algoritmo faz esse passo tantas vezes.
Por exemplo, se houver um laço que percorre um vetor do primeiro ao último elemento somando tudo, o passo pode ser:
- acessar o elemento atual;
- somá-lo a um acumulador;
- avançar o índice.
Uma repetição do laço corresponde a um passo. Se o vetor tiver n elementos, o laço executa n passos.
Operação dominante: o que realmente pesa
Nem todos os trechos do algoritmo têm o mesmo peso.
Um pequeno bloco de inicialização pode rodar só uma vez, enquanto outro bloco pode ser repetido milhares ou milhões de vezes.
Complexidade de algoritmos costuma prestar atenção na operação dominante, isto é, naquela parte do código que é repetida mais vezes e que, de fato, manda na conta final.
Se um algoritmo faz:
- um pequeno preparo inicial com 10 ou 20 passos;
- depois roda um laço que executa mil passos;
- no fim imprime um resultado;
a parte que mais contribui para o custo é o laço, não o preparo nem a impressão.
Quando se escreve a função T(n), normalmente as parcelas menores são engolidas pela que cresce mais rápido.
Ignorando detalhes que não mudam a ordem
Outro ponto fundamental: em análise de complexidade, não se liga para constantes exatas.
Se um algoritmo, para uma entrada de tamanho n, faz:
e outro faz:
ambos crescem “na mesma linha” quando n é muito grande. A diferença entre 3n e 7n é real, claro, mas em termos de ordem de grandeza ambos são proporcionais a n. Costuma-se dizer que os dois têm complexidade linear no tamanho da entrada.
Na prática, isso significa que:
- dobra o tamanho da entrada → o número de passos dobra aproximadamente;
- triplica o tamanho da entrada → o número de passos triplica, e assim por diante.
Código real sempre tem constantes e detalhes finos, mas a análise de complexidade está interessada em como o esforço cresce lá longe, quando n explode.
Exemplos concretos: somar e multiplicar matrizes
Um exemplo clássico de comparação de complexidade aparece quando se trabalha com matrizes. Imagine duas matrizes quadradas A e B, cada uma com n linhas e n colunas.
Soma de matrizes
Para somar duas matrizes, basta somar elemento a elemento:
- resultado[i, j] = A[i, j] + B[i, j].
É preciso visitar cada posição uma vez.
Em uma matriz n × n, existem n² elementos. Logo:
- o número de somas é n²;
- a complexidade de tempo cresce como n².
Esse padrão recebe o nome de complexidade quadrática: se o tamanho linear (n) dobra, a quantidade de operações cresce por um fator de quatro.
Produto de matrizes
O produto de duas matrizes já é mais trabalhoso.
O elemento C[i, j] é calculado como:
- C[i, j] = soma, para k de 1 até n, de A[i, k] × B[k, j].
Ou seja:
- para cada par (i, j), é preciso fazer n multiplicações e n − 1 somas;
- existem n² pares (i, j).
O total de operações fica proporcional a n³.
É um salto enorme: se o n dobra, o custo aumenta oito vezes; se n triplica, sobe para 27 vezes.
Aí já se fala em complexidade cúbica, típica de certos algoritmos que usam três laços aninhados.
Melhor caso, pior caso e caso médio
Um algoritmo nem sempre executa o mesmo número de passos para toda entrada de mesmo tamanho. Isso aparece bem em operações de busca.
Imagine uma função que procura um número x em um vetor de n posições, percorrendo da primeira até a última:
- Se x estiver logo na primeira posição, o algoritmo faz pouquíssimo trabalho.
- Se x não estiver no vetor, o algoritmo precisa olhar todas as posições antes de desistir.
Para falar disso com mais precisão, utiliza-se três conceitos:
Complexidade de melhor caso:
número mínimo de passos que o algoritmo pode executar para entradas de tamanho n.
No exemplo da busca, seria quando o elemento procurado está na primeira posição.
Complexidade de pior caso:
número máximo de passos entre todas as entradas de tamanho n.
Na busca, ocorre quando o elemento não está presente ou está na última posição.
Complexidade de caso médio:
média do número de passos, considerando alguma distribuição de probabilidades sobre as entradas.
Por exemplo, supondo que todas as posições sejam igualmente prováveis para o elemento procurado.
Na prática, quem projeta algoritmos costuma se preocupar bastante com o pior caso, porque ele funciona como uma espécie de “garantia de teto”: assegura que o tempo nunca extrapola certa ordem de grandeza.
O caso médio é muito interessante teoricamente, mas depende da hipótese de como as entradas são distribuídas. Se essa hipótese estiver errada, a conta não representa bem o comportamento real.
Para ficar mais claro, imagine um algoritmo muito simples:
- a entrada tem um parâmetro x, que pode ser 0 ou 1, e duas matrizes n × n;
- se x = 0, o algoritmo soma as matrizes;
- se x = 1, o algoritmo multiplica as matrizes.
Aqui, o tamanho da entrada, em termos de n, é o mesmo. Só que o “caminho interno” muda completamente:
- quando x = 0, o tempo cresce como n² (soma de matrizes);
- quando x = 1, o tempo cresce como n³ (produto de matrizes).
Olhando por esse lado:
- melhor caso: quando sempre se soma, complexidade quadrática;
- pior caso: quando sempre se multiplica, complexidade cúbica;
- caso médio: depende de com que frequência x é 0 ou 1.
Se, por exemplo, x = 0 tiver probabilidade q, e x = 1 tiver probabilidade 1 − q, a complexidade média Tm(n) seria algo como:
- Tm(n) ≈ q · n² + (1 − q) · n³.
Quando n é grande, o termo n³ domina sempre que 1 − q não for zero. Isso significa que, mesmo se multiplicar for um pouco raro, o custo do algoritmo vai ser puxado para a ordem cúbica.
Complexidade de tempo e complexidade de espaço
Embora quase sempre o foco das conversas esteja na complexidade de tempo, existe também a complexidade de espaço, que mede quanta memória o algoritmo consome.
Alguns algoritmos economizam tempo às custas de usar mais memória, guardando resultados intermediários para evitar recomputações. Outros fazem o contrário: usam pouca memória, mas repetem cálculos.
Complexidade de espaço também é expressa em função de n:
- um algoritmo que precisa de um vetor de n posições tem espaço proporcional a n;
- um algoritmo que trabalha com uma matriz auxiliar n × n usa memória proporcional a n²;
- um algoritmo recursivo pode consumir espaço proporcional à profundidade das chamadas.
Em muitos problemas, a memória disponível é tão importante quanto o tempo.
Um algoritmo teoricamente brilhante, mas que exige uma quantidade absurda de memória, pode ser inviável na prática.
Crescimentos típicos que aparecem
Quando se começa a analisar algoritmos, algumas formas de crescimento aparecem com frequência:
Constante: o esforço não depende de n (ou cresce tão pouco que é considerado fixo).
Exemplo: retornar o primeiro elemento de uma lista que já está em memória.
Logarítmico: cresce como log n, muito devagar.
Exemplo clássico: busca binária em lista ordenada.
Linear: cresce proporcionalmente a n.
Exemplo: percorrer um vetor fazendo uma operação simples em cada posição.
Quadrático: cresce como n².
Exemplo: dois laços aninhados que percorrem todos os pares (i, j) de um conjunto com n elementos.
Cúbico: cresce como n³, como no produto ingênuo de matrizes n × n.
Exponencial: cresce como 2, 3 ou algo do tipo.
Exemplo: certos algoritmos recursivos que exploram todas as combinações possíveis.
Na prática, esse tipo de classificação ajuda a ter uma intuição imediata:
- linear é, em geral, aceitável mesmo para entradas muito grandes;
- quadrático pode ser problemático se n for da ordem de milhões;
- cúbico costuma ser viável só para n relativamente pequenos;
- exponencial explode tão rápido que só serve para tamanhos bem modestos de entrada.
Um modelo mental: como olhar um algoritmo e “sentir” a complexidade
Quando se pega um algoritmo escrito, uma forma simples de começar a analisar é:
Identificar os laços principais (para, enquanto).
Ver quantas vezes cada laço se repete em função de n.
Ver se existem laços aninhados.
Um laço dentro de outro tende a gerar multiplicação de fatores: se o laço externo roda n vezes e o interno também n vezes, já aparece um n².
Observar se há chamadas recursivas.
Contar quantas chamadas são geradas e quanto cada uma custa.
Ignorar por enquanto os trechos que rodam poucas vezes (inicializações, impressões simples).
Esses trechos raramente mudam a ordem de grandeza do custo.
Por exemplo:
- Um único laço que vai de 1 até n, fazendo operações simples, costuma dar complexidade linear.
- Dois laços um dentro do outro, ambos indo de 1 até n, costumam dar complexidade quadrática.
- Três laços aninhados, cada um de 1 até n, tendem a levar a complexidade cúbica.
Claro que existem exceções, mas esse raciocínio já ajuda a criar uma espécie de “radar” intuitivo.
Por que essa história toda importa tanto
À primeira vista, toda essa conversa de “ordem de grandeza”, “n²”, “n³” pode parecer um pouco distante do mundo real. Só que, em sistemas de verdade, o impacto é enorme.
Imagine duas situações:
- Um algoritmo com complexidade n² rodando com n = 1000 precisa de algo em torno de 1 milhão de operações.
- Um algoritmo com complexidade n³ rodando com n = 1000 precisa de algo em torno de 1 bilhão de operações.
Agora pense se o n cresce para 10 mil:
- n² vira 100 milhões;
- n³ vira 1 trilhão.
Essa diferença pode ser a fronteira entre um sistema que responde em segundos e um que simplesmente não termina em tempo útil. É por isso que, em áreas como bancos de dados, redes, criptografia, inteligência artificial, tudo gira em torno de algoritmos que consigam lidar com dados enormes sem explodir o custo de tempo ou memória.
Complexidade de algoritmos é justamente o ferramental teórico para:
- comparar duas soluções possíveis;
- saber se vale a pena trocar um algoritmo por outro;
- prever como o sistema vai se comportar quando o volume de dados aumentar.
Quem domina esse jeito de pensar deixa de ver código apenas como “faz ou não faz” e passa a enxergar uma camada a mais: “faz, mas com qual custo?”. Essa mudança de olhar é o que separa um simples “programinha que funciona” de um software robusto, planejado para sobreviver a entradas cada vez maiores.
Complexidade dos algoritmos
Quando alguém começa a mexer com complexidade de algoritmos, aparece uma notação que parece meio esquisita à primeira vista: o tal do O grande, ou notação O. Muitos encaram aquilo como um símbolo misterioso grudado em fórmulas do tipo O(n²) ou O(n³) e segue em frente sem entender direito o que está acontecendo ali.
A ideia, na verdade, é bem pé no chão: a notação O é um jeito compacto de dizer “qual é a ordem de crescimento” do custo de um algoritmo, ignorando detalhes que, para entradas muito grandes, quase não fazem diferença. Em vez de anotar uma expressão cheia de termos, a notação O funciona como um resumo do que realmente manda na conta.
Por que resumir fórmulas de complexidade?
Imagine que você analisou um algoritmo e chegou nesta expressão para o número de passos:
Aqui, n é o tamanho da entrada (números em um vetor, por exemplo) e T(n) é quantos “passinhos básicos” o algoritmo faz. Em termos matemáticos, está lindo. Agora pense no que acontece quando n cresce:
- se n = 10, T(10) = 50;
- se n = 1.000, T(1000) = 3.020;
- se n = 1.000.000, T(1.000.000) ≈ 3.000.020.
Repare que aquele + 20 fica cada vez mais irrelevante. Quando se está lidando com milhões de elementos, pouco importa se faz 3.000.000 ou 3.000.020 operações. A parte que realmente manda é o 3n.
Por causa disso, em análise de algoritmos se adotam duas simplificações importantes :
Ignorar constantes multiplicativas.
Se o número de passos é 3n, diz-se que é “da ordem de n”. Aquela constante 3 some do radar.
Ignorar termos de menor grau.
Se o número de passos é n² + n, o termo n² domina quando n cresce. O + n é pequeno perto de n² para valores grandes de n.
Alguns exemplos típicos:
3n é aproximado por n;n² + n é aproximado por n²;6n³ + 4n − 9 é aproximado por n³.
Em vez de ficar repetindo “estamos ignorando constantes e termos menores”, usa-se um operador matemático que incorpora essa ideia: a notação O.
Definição intuitiva da notação O
Pense em duas funções:
- f(n): o custo real (ou uma expressão) do seu algoritmo;
- h(n): uma função mais simples, que vai servir como limite superior para f(n).
Dizer que f(n) é O(h(n)) significa, em termos informais:
“Para valores grandes de n, f(n) cresce no máximo como uma constante vezes h(n).”
Usando a definição mais formal, costuma-se escrever assim :
f(n) = O(h(n)) quando existe uma constante c > 0 e um valor n₀ tal que, para todo n > n₀,
f(n) ≤ c · h(n).
Ou seja:
- a partir de um certo ponto n₀,
- h(n) serve como um teto assintótico para f(n),
- talvez multiplicada por alguma constante c.
A palavra chave é assintótico: o interesse está no comportamento para n grande, não em valores pequenos e detalhes finos.
Exemplos concretos para pegar o jeito
Alguns exemplos clássicos ajudam a “sentir” a notação O :
f(n) = n² − 1
- Para n grande,
−1 não faz diferença.
- Dá para encontrar uma constante c que torne
n² − 1 ≤ c · n² a partir de algum n₀.
- Então se escreve:
f(n) = O(n²).
Também é verdade que f(n) = O(n³), porque n³ cresce ainda mais rápido que n². Só que O(n²) é uma descrição bem mais ajustada.
f(n) = 403
- O número de passos é constante, não depende de n.
- Diz-se que f(n) é O(1), lido como “ordem de 1”.
- É um jeito de dizer: “não cresce com o tamanho da entrada”.
f(n) = 5 + 2 log n + 3 (log n)²
Para n grande, o termo que domina é (log n)². Os outros ficam relativamente pequenos perto dele.
Então se escreve:
É verdade também que f(n) = O(n), porque n cresce ainda mais rápido que (log n)². Mas, se a intenção é descrever bem a ordem de grandeza, (log n)² é muito mais fiel.
f(n) = 3n + 5 log n + 2
Aqui, o termo dominante é o 3n. Os outros são menores para n grande.
Fica:
f(n) = 5·2ⁿ + 5n¹⁰
Mesmo que n¹⁰ pareça enorme, o termo 2ⁿ cresce MUITO mais rápido do que qualquer potência fixa de n.
Então, assintoticamente:
Esses exemplos mostram a lógica geral: procura-se o termo que cresce mais rápido quando n aumenta, e é esse termo que aparece dentro da notação O.
Propriedades úteis da notação O
A notação O se comporta de maneira bem amigável com operações simples entre funções. Algumas propriedades são usadas o tempo todo :
Se g(n) e h(n) são funções positivas e k é uma constante, então:
- O(g + h) = O(g) + O(h)
- O(k · g) = k · O(g) = O(g)
Traduzindo em linguagem mais direta:
Quando você soma duas funções, a ordem de grandeza fica na mesma escala da maior delas.
Exemplo: O(n² + n³) vira O(n³).
Multiplicar uma função por uma constante não muda sua ordem de grandeza.
Exemplo: O(7n²) continua sendo O(n²).
Isso combina com a ideia de “ignorar constantes e termos menores”. Na prática, quando você vê uma expressão com vários termos, olha para aquele que domina o crescimento e joga o resto para baixo do tapete da notação O.
Até aqui, falamos de funções em abstrato. Mas o objetivo real é descrever a complexidade de tempo (ou de espaço) de algoritmos usando essa notação.
Suponha que você já contou os passos de vários algoritmos simples:
Um algoritmo que inverte um vetor faz sempre ⌊n/2⌋ trocas.
Para n grande, isso é da ordem de n.
Diz-se: complexidade O(n).
Um algoritmo iterativo para fatorial faz n multiplicações, uma para cada valor de 2 até n.
De novo, isso é proporcional a n.
Complexidade: O(n).
A soma de duas matrizes n × n faz n² somas.
Complexidade: O(n²).
O produto de duas matrizes n × n, na forma ingênua com três laços aninhados, faz um número de operações proporcional a n³.
Complexidade: O(n³).
Repare como a notação O esconde todos os detalhes da contagem exata (se é n², n² + 3n, 2n³ etc.) e guarda só a “classe” do crescimento.
Essa simplificação tem duas grandes vantagens:
- Permite comparar algoritmos de forma independente de constante e de máquina.
- Foca no que realmente importa em aplicações grandes: como o custo explode (ou não) quando a entrada cresce.
Por que um mesmo f(n) pode ter vários “O( )” diferentes?
Uma dúvida natural: se n² − 1 é O(n³) e também é O(2ⁿ), por que escolher O(n²)? Não está tudo certo?
Sim, está. A definição permite dizer que n² − 1 é O(n³), O(n⁴), O(2ⁿ) e assim por diante, porque todas essas funções crescem mais rápido que n². A questão é que algumas descrições são bem mais informativas do que outras.
Pense em duas frases:
- “Eu moro no Brasil.”
- “Eu moro no bairro X, na cidade Y, no estado Z.”
As duas podem estar corretas, mas a segunda é bem mais específica. Quando se escreve f(n) = O(n²), está se dando um “endereço” muito mais preciso do que f(n) = O(2ⁿ).
Na prática, quem faz análise de algoritmos costuma buscar uma forma de O( ) que seja:
- correta;
- o mais apertada possível, isto é, que descreva bem a ordem de grandeza, sem exagerar.
Mais adiante entram notações como Θ (teta) e Ω (ômega) para falar de limites mais ajustados e limites inferiores, mas a notação O, sozinha, já resolve muita coisa do dia a dia.
Quando você diz que “a complexidade de pior caso de um algoritmo é O(n²)”, está afirmando:
“No pior cenário, o número de passos cresce no máximo na ordem de n².”
Se a complexidade de melhor caso é O(n), significa:
“Mesmo na situação mais favorável, o número de passos não passa de alguma constante vezes n.”
Já para o caso médio, a ideia é parecida, mas a função f(n) usada dentro do O vem de uma média ponderada (de acordo com probabilidades de cada tipo de entrada). O raciocínio da notação O continua igual.
Às vezes, um mesmo algoritmo tem:
- melhor caso com uma forma de O( );
- pior caso com outra forma de O( );
- caso médio com uma terceira.
Um exemplo clássico é o algoritmo que, dependendo de um parâmetro x, decide se vai somar ou multiplicar matrizes:
- quando x = 0, faz soma → O(n²);
- quando x = 1, faz produto → O(n³).
Nesse cenário:
- O melhor caso é O(n²);
- O pior caso é O(n³);
- O caso médio vai ser uma mistura, algo como q·n² + (1 − q)·n³, que assintoticamente fica com cara de O(n³) se a multiplicação tiver qualquer probabilidade real de ocorrer.
A notação O serve para registrar cada uma dessas situações sem sufocar a leitura com fórmulas completas.
Imagine que você está olhando prédios de uma cidade de longe, do alto de um morro.
- Lá de cima, você não enxerga se cada prédio tem 10 ou 12 andares.
- Você percebe se um bairro é de casas baixas, se outro é de prédios médios, e se uma região específica tem arranha-céus gigantes.
A análise de complexidade com notação O faz algo parecido:
- não se preocupa com detalhes milimétricos (constante a mais, termo de grau menor);
- foca em “qual bairro” de crescimento a função está: constante, logarítmico, linear, quadrático, cúbico, exponencial.
Quando alguém diz que um algoritmo é O(n log n), está basicamente te avisando:
“Esse algoritmo está na região dos prédios médios: cresce mais do que linear, mas bem menos do que quadrático.”
Quando diz que algo é O(2ⁿ), o recado é:
“Aqui estão os arranha-céus exagerados. Para entradas um pouco maiores, o custo dispara de forma violenta.”
Comparando
Quando alguém começa a estudar algoritmos, uma pergunta aparece quase automaticamente:
“Ok, eu tenho um algoritmo que funciona… mas será que dá para fazer melhor?”
É aqui que entra a ideia de algoritmo ótimo. Não é só “rápido” no sentido vago. É o melhor que se pode conseguir para aquele problema, dentro de um certo modelo de computação. Não existe outro algoritmo que resolva o mesmo problema, de forma geral, com uma ordem de complexidade assintótica menor.
Primeiro passo: lembrar o que é custo de um algoritmo
Antes de falar em “ótimo”, precisa ficar claro o que significa comparar algoritmos.
Quando se estudam algoritmos, o “tempo” não é medido em segundos, e sim em número de passos em função do tamanho da entrada, que costuma ser representado por uma variável n. Esse tempo é escrito com aquelas notações:
- O(… ) para limite superior assintótico (ordem de grandeza máxima);
- Ω(… ) para limite inferior assintótico (ordem de grandeza mínima).
De forma bem resumida:
- dizer que um algoritmo é O(n²) significa que, para n grande, o número de passos cresce no máximo proporcional a n²;
- dizer que qualquer algoritmo para um certo problema precisa de pelo menos Ω(n²) passos quer dizer: não importa o truque, ninguém escapa de uma quantidade de trabalho da ordem de n².
Esses dois lados são importantes:
- O(…): o que um algoritmo específico gasta;
- Ω(…): o que qualquer algoritmo é obrigado a gastar, só por causa da natureza do problema.
Um algoritmo é chamado de ótimo quando essas duas coisas “se encontram”, isto é, quando a complexidade de pior caso do algoritmo bate no limite inferior do problema, até fator constante.
Limite inferior: o piso do esforço
Pense num problema bem simples: inverter os elementos de um vetor com n posições.
Não importa qual algoritmo se invente, uma coisa é inevitável: ler os n elementos em algum momento. Se o vetor tem n posições e o computador nunca olha para algumas delas, como garantir que a saída está correta?
Então, qualquer algoritmo de inversão precisa, no mínimo, fazer algo proporcional a n leituras. Diz-se que o problema tem limite inferior Ω(n).
O raciocínio vale para outros casos:
- somar duas matrizes n×n exige ler todos os n² elementos; o limite inferior do problema é Ω(n²);
- não há como somar sem olhar os dados.
Esse tipo de limite é chamado, às vezes, de limite trivial, porque vem direto do tamanho da entrada: se você precisa ler tudo, já tem ali um custo mínimo.
Em termos de metáfora: é como carregar caixas de um caminhão. Mesmo que o processo seja mega organizado, existe um número mínimo de viagens ou de levantadas, porque cada caixa precisa sair de onde está. Esse número mínimo é o “Ω” do problema.
Limite superior: o teto fornecido por um algoritmo real
Agora vem o outro lado: olhar para um algoritmo concreto e perguntar:
“Qual é a ordem de grandeza do número de passos que ele executa no pior caso?”
Se o algoritmo de inverter o vetor faz um laço que troca o primeiro com o último, o segundo com o penúltimo e assim por diante, ele executa algo em torno de n/2 trocas. Isso é da ordem de n operações. Então a complexidade de pior caso é O(n).
Da mesma forma:
- somar duas matrizes n×n com dois laços aninhados (um para linha, outro para coluna) faz n² somas; complexidade O(n²).
Essas contagens fornecem o limite superior: garantem que, naquele algoritmo, o esforço nunca passa da ordem de n ou de n², de acordo com o caso.
Agora sim: o que é um algoritmo ótimo?
Juntando as duas coisas:
- se um problema tem um limite inferior Ω(f(n)), ou seja, qualquer algoritmo precisa de pelo menos uma ordem de f(n) passos;
- e se existe um algoritmo cujo pior caso é O(f(n)), isto é, que resolve o problema dentro dessa mesma ordem de esforço;
então esse algoritmo é considerado ótimo.
Em outras palavras, o problema exige pelo menos f(n) passos, e o algoritmo resolve com, no máximo, uma constante vezes f(n). Não dá para melhorar a ordem de grandeza. Tudo o que se pode brigar dali em diante são constantes (ser 2 vezes mais rápido, 3 vezes mais rápido etc.), mas a curva de crescimento é a melhor possível.
É como saber que, fisicamente, um certo trajeto só pode ser percorrido em, no mínimo, 10 minutos, dadas as leis da física e os limites de velocidade. Se alguém inventa um método que faz esse trajeto estabilizado sempre em algo como 11 ou 12 minutos, esse método é “ótimo” em termos de ordem de grandeza. Qualquer melhoria posterior vai ser em detalhes finos, não no “tipo” de tempo.
Exemplos bem concretos
1. Inversão de sequência
- Problema: inverter um vetor com n elementos.
- Limite inferior: Ω(n), porque é preciso ler a sequência.
- Algoritmo padrão: laço que faz trocas em pares da ponta para o centro, com algo em torno de n/2 trocas.
- Complexidade: O(n).
Como o limite inferior é Ω(n) e o algoritmo resolve em O(n), conclui-se que se trata de um algoritmo ótimo. Não há jeito, dentro desse modelo de custo, de inverter com menos do que uma ordem linear de operações.
2. Soma de matrizes
- Problema: somar duas matrizes n×n.
- Limite inferior: Ω(n²), pela leitura dos n² elementos.
- Algoritmo padrão: dois laços aninhados, um para linha e outro para coluna, que fazem uma soma para cada posição.
- Complexidade: O(n²).
De novo, limite inferior e limite superior batem na mesma ordem, então o algoritmo é ótimo.
Esses dois casos são, de certa forma, “fáceis” de analisar porque o limite inferior vem diretamente do fato de ser preciso ler todos os dados.
3. Produto de matrizes
Aqui as coisas ficam interessantes.
- Problema: multiplicar duas matrizes n×n.
- Limite inferior trivial: pelo menos tem que ler as matrizes, então Ω(n²).
- Algoritmo ingênuo: três laços aninhados (linha, coluna, índice de multiplicação), com cerca de n³ operações. Complexidade O(n³).
Dá para dizer que o algoritmo ingênuo é ótimo?
Com base só no limite trivial Ω(n²), não. Existe espaço entre n² e n³, e nada impede, em teoria, a existência de um algoritmo O(n²·log n), por exemplo.
Na prática, já foram descobertos algoritmos que multiplicam matrizes com complexidade assintótica menor do que n³. Isso mostra que o algoritmo com três laços não é ótimo.
Ou seja: quando o limite inferior é muito fraco, não basta bater nesse limite para dizer que o algoritmo é o melhor possível.
Quando o limite inferior não é trivial
Os exemplos anteriores usaram limites inferiores que vêm diretamente do tamanho da entrada. Só que, em vários problemas, é possível provar limites inferiores mais fortes, usando propriedades matemáticas do problema, e não só o “precisa ler os dados”.
Um exemplo clássico é o problema de ordenar uma sequência de n elementos usando apenas comparações.
- Limite trivial (ler os elementos): Ω(n).
- Mas há uma prova matemática bem conhecida de que qualquer algoritmo baseado só em comparações precisa de, pelo menos, Ω(n log n) comparações em pior caso.
Por outro lado, existem algoritmos como mergesort e heapsort cuja complexidade de pior caso é O(n log n). Ou seja:
- limite inferior: Ω(n log n);
- limite superior (de algoritmos reais): O(n log n).
Resultado: esses algoritmos são considerados ótimos dentro do modelo de comparação.
Esse tipo de encaixe é o sonho de quem trabalha com projeto de algoritmos: ter uma prova de que ninguém consegue fazer melhor (assintoticamente) e, ao mesmo tempo, ter uma técnica que chega justamente nesse limite.
A tal “distância” entre limites inferiores e algoritmos
Nem sempre a situação é tão bonita.
Para uma grande quantidade de problemas importantes, acontece algo assim:
- o melhor limite inferior conhecido é um polinômio em n (tipo n, n², n³);
- o melhor algoritmo conhecido tem complexidade exponencial, do tipo 2ⁿ, 3ⁿ ou parecido.
Ou seja, há um abismo entre o que se sabe que é necessário e o que de fato se consegue fazer com as técnicas atuais. Não se sabe se esse abismo existe porque:
- ainda não foi descoberta uma prova de limite inferior mais forte, ou
- ainda não foi inventado um algoritmo mais rápido, ou
- as duas coisas ao mesmo tempo.
Esse cenário aparece em vários problemas difíceis em teoria da computação, especialmente em temas ligados à famosa questão P vs NP: será que certos problemas que parecem exigir tempo exponencial têm, na verdade, algoritmos polinomiais escondidos?
Nesses casos, ninguém se arrisca a dizer que um algoritmo é ótimo. O máximo que se pode afirmar é:
- “Este é o melhor algoritmo conhecido até agora”
- “O maior limite inferior conhecido é tal”.
A palavra “ótimo”, nesse contexto teórico, é reservada para quando há encaixe claro entre limite inferior e limite superior.
Imagine que se quer viajar de uma cidade a outra, e um físico te diz:
“Pelas leis da física e pela distância, qualquer viagem vai demorar pelo menos 1 hora.”
Esse 1 hora é o limite inferior.
Agora compare três situações:
Você tem um meio de transporte que sempre leva 1h15.
A diferença é só um fator de 1,25. Em termos de ordem de grandeza, é praticamente a melhor coisa possível. Isso é análogo a um algoritmo ótimo: bate no limite inferior até constante.
Você tem outro meio de transporte que sempre leva 10 horas.
A diferença já é de 10 vezes o mínimo. Pode ser que exista um método muito melhor que ainda não foi inventado. Esse é o caso em que a complexidade do melhor algoritmo conhecido é bem acima do limite inferior.
Pior: o limite inferior que o físico conseguiu provar é só “pelo menos 10 minutos”, mas todo transporte real leva de horas a semanas.
Talvez a prova esteja fraca, talvez os meios de transporte sejam muito ruins, talvez os dois. Esse é o cenário de vários problemas difíceis em computação.
E na prática do dia a dia, isso importa mesmo?
Em código real, a discussão sobre “ótimo” pode parecer distante, mas ela tem impacto direto em:
- desempenho de sistemas grandes: bancos de dados, motores de busca, redes;
- custo de infraestrutura: menos tempo de CPU significa menos gasto de energia e de máquinas;
- experiência do usuário: um algoritmo quadrático pode ser aceitável em poucos dados, mas inviável quando a empresa cresce.
Saber que um algoritmo é ótimo dá uma espécie de paz de espírito: se esse problema é crítico para o sistema, não adianta ficar gastando meses tentando encontrar algo com complexidade assintoticamente menor, porque as próprias provas matemáticas dizem que isso não existe naquele modelo.
Por outro lado, quando se sabe que o algoritmo não é ótimo (como o produto ingênuo de matrizes), isso acende uma luz de oportunidade para pesquisa e melhoria: talvez haja um jeito mais esperto de reorganizar o cálculo e ganhar ordens de grandeza em desempenho.
Um detalhe importante: ótimo não quer dizer “o melhor em todos os sentidos”
Vale um cuidado final: na teoria, “ótimo” significa bater o limite inferior na ordem de grandeza. Na prática, dois algoritmos com mesma complexidade assintótica podem ter comportamentos muito diferentes:
- um pode ser mais simples de implementar, mais fácil de manter;
- outro pode ter uma constante escondida enorme, usando dezenas de estruturas auxiliares;
- um pode funcionar melhor em entradas pequenas ou médias, que são justamente o que aparece no mundo real.
Então, na hora de escolher um algoritmo para um sistema de verdade, entram outros fatores:
- simplicidade;
- robustez;
- comportamento em casos típicos, não só no pior caso;
- consumo de memória;
- facilidade de testar e depurar.
A teoria da otimização algorítmica ajuda a estabelecer o limite do que é possível. Dentro desse limite, o trabalho do engenheiro de software é encontrar o ponto de equilíbrio entre matemática, desempenho e pragmatismo.
Aqui terminamos.
