Entendendo a Complexidade de Algoritmos com o Push Swap

Representação empírica da complexidade de algoritmos.

Introdução

Este artigo é um guia simples pra entender o que é complexidade de algoritmos na prática, sem muita formalidade nem linguagem matemática pesada. Decidi escrever isso pra ajudar os meus colegas da 42 Luanda, porque muita gente acaba fazendo o projeto Push Swap sem realmente entender o que é complexidade de algoritmos. Mas deixo claro: o conteúdo serve pra qualquer programador, mesmo que não seja cadete da 42 ou nunca tenha ouvido falar do Push Swap.

Contexto

O Push Swap é um projeto da Escola 42 que consiste em criar um programa em C capaz de ordenar números inteiros usando duas pilhas (A e B) e um conjunto limitado de operações (push, swap, rotate, reverse rotate).

A ideia parece simples: no final, os números precisam estar ordenados em ordem crescente na pilha A, e a pilha B deve estar vazia. O desafio real é outro: você não pode só fazer funcionar, precisa fazer de forma eficiente, respeitando os limites máximos de operações: até 12 operações para 5 números até 1500 operações para 100 números até 11500 operações para 500 números

Pra ter uma noção melhor da eficiência, vamos olhar um exemplo usando uma variação do Selection Sort:

1. Procuramos o menor elemento na pilha A.
2. Verificamos a posição dele: se está acima ou abaixo da metade da pilha.
3. Com base nisso, escolhemos se vale a pena usar rotate ou reverse rotate (pra economizar operações).
4. Aplicamos a operação repetidamente até o menor elemento chegar no topo.
5. Empurramos esse elemento pra pilha B.

Repetindo esse processo até a pilha A ficar vazia, no final teremos a pilha B ordenada em ordem decrescente. Depois é só mandar tudo de volta pra pilha A e ela estará ordenada.

Funcionou? Sim, mas… não é eficiente. Esse método chega a usar mais ou menos 7000 operações pra 100 números e 32000 pra 500 números. Isso estoura os limites impostos pelo projecto.

E é aí que está o verdadeiro desafio do Push Swap: não basta ordenar, precisamos ordenar bem.

É aqui que entra o estudo de complexidade de algoritmos. Ao entender como medir a eficiência de uma solução, conseguimos comparar abordagens diferentes e justificar por que certas estratégias escalam melhor que outras.

Complexidade de algoritmos e Big-O

Medir a complexidade de um algoritmo, é medir o quão eficiente é esse algoritmo levando em conta o tamanho da entrada (geralmente chamado de n), e para isso precisamos definir um critério de eficiência, que normalmente são: tempo de execução e espaço de memória ocupado.

Assim sendo, vamos definir a complexidade de um algoritmo como sendo uma medida de quanto tempo ou memória ele consome em função do tamanho da entrada . Ela é analisada usando as notações assintóticas e a mais comum é a notação Big O, que descreve como a quantidade de tempo ou espaço cresce à medida que o tamanho da entrada aumenta, focando geralmente no pior caso para garantir a eficiência máxima

Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples.

Um pouco complicado? 😅. Calma que um dos objectivos deste artigo é justamente descomplicar esses termos matemáticos. De forma simples, a notação Big-O é uma ferramenta matemática usada para descrever como uma função se comporta quando seus valores de entrada se tornam muito grandes. Essa mesma abordagem é utilizada em computação para analisar algoritmos. Ela simplifica a análise comparando a função original com outras mais fáceis de entender.

Esta notação faz parte de um conjunto maior, conhecido como notação assintótica ou notação de Landau, que inclui outros tipos de medições (Omega e Theta). Essencialmente a notação Big-O nos ajuda a prever o crescimento de uma função de forma descomplicada e sem muita rigidez.

Quando falamos em medição de tempo de execução de um algoritmo, medir o tempo absoluto (em minutos, segundos, etc.) não seria interessante porque normalmente o algoritmo terá desempenho diferente com base na linguagem de programação, processador, memória e outros componentes de hardware. Por isso usamos a notação assintótica Big-O que nos permite medir a eficiencia de um algoritmo ignorando termos de menor taxa de crescimento (termos de produtos que não dependam de n, constantes, parcelas, etc.) e nos focarmos apenas no termo de maior taxa de crescimento.

Exemplos de complexidade

Existem tipos comuns de complexidades na notação Big-O e veremos uma lista em ordem do mais eficiente ao menos eficiente usando o tempo de execução como critério de eficiência.

Comparação das curvas de crescimento das principais complexidades.

O(1) — Complexidade Constante: O tempo de execução é sempre o mesmo independentemente do tamanho da entrada. Ex: acessar um elemento de um array pelo seu índice

O(log n) — Complexidade Logarítmica: O tempo de execução cresce de forma muita lenta à medida que o tamanho da entrada (n) aumenta. Ex: buscar um item em uma lista ordenada usando busca binária.

O(n) — Complexidade Linear: O tempo de execução aumenta directamente proporcional ao tamanho da entrada. Se o tamanho da entrada dobra, o tempo de execução também dobra. Ex: Percorrer um array ou uma lista inteira para encontrar um valor.

O(n log n) — Complexidade Linearítma: O tempo de execução é uma combinação de crescimento linear e logorítmo. É muito comum em algoritmos de ordenação eficiente. Ex: Ordenar um array grande dividindo em partes menores e depois juntando novamente.

O(n²) — Complexidade Quadrática: O tempo de execução cresce proporcional ao quadrado do tamanho da entrada. Se o tamanho da entrada dobra o tempo de execução quadriplica. Ex: Comparar todos os elementos de um array com todos os outros para descobrir pares iguais. Com 100 elementos, teriamos até 100 × 100 = 10.000 comparações.

O(n³) — Complexidade Cúbica: O tempo de execução cresce proporcional ao cubo do tamanho da entrada. Se o tamanho da entrada dobra o tempo cresce cerca de oito vezes (2³ = 8). Ex: Percorrer todos os elementos de uma matriz tridimensional com três loops aninhados.

O(2ⁿ) — Complexidasde Exponencial: O tempo de execução é proporcional a 2 elevado ao tamanho da entrada, ou seja, o tempo praticamente dobra a cada novo elemento adicionado à entrada. Ex: Gerar todos os subconjuntos possíveis de um array de tamanho n. Se o array tiver 10 elementos, existem 2¹⁰ = 1.024 subconjuntos diferentes.

O(!n) — Complexidade Factorial: O tempo de execução é proporcional ao factorial do tamanho da entrada. Isso significa que, à medida que o tamanho de entrada aumenta o tempo de execução cresce de forma explosiva. Esta é a pior das complexidades mais comuns e é insustentável para a maioria das entradas. Ex: tentar encontrar todas as permutações de uma string.

Quer ver algo assustador e o porquê é importante entender sobre complexidade de algoritmos? Vamos a um exemplo prático:

Um algoritmo com complexidade O(!n) — imprimir todas as permutações de uma string: Supondo que cada combinação pode levar um tempo mínimo (por exemplo, poucos nanossegundos).

• Se n = 5, o número de operações é 5! = 120. Isso é rápido.
• Se n = 10, o número de operações é 10! = 3.628.800. Isso já começa a demorar um pouco.
• Se n = 20, o número de operações é um número com 18 dígitos: 20! = 2,4 × 10¹⁸.

Se considerarmos que: 1 ns = 10⁻⁹ s, então: 2,4 × 10¹⁸ ns / 10⁹ = 2,4 × 10⁹ s ,sabendo que: 1 dia tem 86.400 s e 1 ano tem 365 dias. Fazendo as contas: 2,4 × 10⁹ / (365 × 86.400) ≈ 77 anos Ou seja: um algoritmo que gera todas as permutações de uma string de 20 caracteres diferentes levaria cerca de 77 anos para rodar.

O impacto do crescimento fatorial: de nanossegundos a 77 anos.

Para que um algoritmo funcione bem, é crucial pensar em sua eficiência desde o início durante o seu planejamento. Embora seja possível criar um algoritmo primeiro e só depois avaliar sua perfomance, a melhor abordagem é ter a preocupação de projectar algoritmos eficientes desde a sua concepção.

Aplicação no Push Swap

No Push Swap, a conversa muda um pouco. O critério de eficiência aqui não é o número de operações internas do algoritmo (tipo percorrer a pilha, buscar elementos, comparar valores, etc.), mas sim o número de instruções usadas pra ordenar a sequência numérica.

Se fôssemos medir pelo critério tradicional de complexidade, que vimos antes, só o trabalho interno já daria pelo menos O(n²) ou pior — dependendo da implementação, claro 🙂.

Mas o que realmente conta no Push Swap são as instruções permitidas. E quais são elas? Bom, se você é cadete da 42 provavelmente já sabe, mas vamos listar aqui pra todo mundo entender.

Trocar (Swap)

• sa, sb: Trocam os dois primeiros elementos no topo da pilha ‘a’ ou ‘b’, respetivamente. Não fazem nada se houver um ou nenhum elemento na pilha.
• ss: Executa as operações sa e sb simultaneamente.

Mover (Push)

• pa: Move o primeiro elemento do topo da pilha ‘b’ para o topo da pilha ‘a’. Não faz nada se a pilha ‘b’ estiver vazia.
• pb: Move o primeiro elemento do topo da pilha ‘a’ para o topo da pilha ‘b’. Não faz nada se a pilha ‘a’ estiver vazia.

Rotacionar (Rotate)

• ra, rb: Deslocam todos os elementos da pilha ‘a’ ou ‘b’, respetivamente, uma posição para cima. O primeiro elemento passa para o final da pilha.
• rr: Executa as operações ra e rb simultaneamente.

Rotacionar Inversamente (Reverse Rotate)

• rra, rrb: Deslocam todos os elementos da pilha ‘a’ ou ‘b’, respetivamente, uma posição para baixo. O último elemento passa para o início da pilha.
• rrr: Executa as operações rra e rrb simultaneamente.

Essas são as operações que o programa Push Swap deve usar para ordenar a pilha. Abaixo tem um exemplo de como isso ficaria:

Lista visual das instruções disponíveis no Push Swap.

Exemplo do programa em execução

E aí vem a pergunta: como medir a complexidade do meu algoritmo no Push Swap? Pra começar, se olharmos os limites máximos impostos, dá pra ver que a complexidade do nosso algoritmo é O(n log n). Mas como a gente pode verificar isso na prática? Como medir de verdade?

Existem duas formas principais de medir/analisar a complexidade de um algorítmo:

1- Análise teórica/matemática: Aqui nós olhamos para o algorítmo em si (códigos, loops, recursões) e deduzimos quantas operações ele faz em função de n. Por exemplo: se um algoritmo tem dois loops aninhados até n, concluímos que é O(n²) sem precisar rodar nada. Essa é a forma mais usada na teoria da computação.

2- Análise empírica/experimental: Nós rodamos o algoritmo com diferentes entradas e medimos o tempo de execução ou número de operações (ou outro critério de eficiência). Depois comparamos com funções conhecidas (n, log n, n log n, etc.) e observamos em qual intervalo ele se encaixa.

Como o Push Swap é complexo de analisar pelo código, a forma mais fácil de identificar a complexidade seria usando a segunda abordagem, mas, tendo em conta que o critério de eficiência para o Push Swap é justamente a quantidade de operações impressas para ordenar a pilha, é justamente essa abordagem que devemos utilizar.

Sendo assim, precisamos usar alguma sequência de valores (tamanho da entrada) e observar como o algoritmo se comporta. Se você prestou atenção nos exemplos de complexidades que mencionei antes, deve lembrar daquela técnica de “dobrar o tamanho da entrada”. É isso que vamos usar. Essa é uma forma rápida de observar o comportamento do algoritmo.

Pra variar um pouco e enxergar melhor, vamos usar tamanhos de entrada de 2 a 4 dígitos. As sequências que vamos testar são: S1: 10, 20, 40, 80 S2: 100, 200, 400 S3: 1.000, 2.000, 4.000

Depois de vários testes com esses tamanhos, obtivemos os seguintes intervalos de operações: 10: 15–35 operações 20: 49–83 operações 40: 146–210 operações 80: 366–483 operações 100: 502–669 operações 200: 1.300–1.622 operações 400: 3.492–4.086 operações 1.000: 12.830–14.487 operações 2.000: 35.503–37.986 operações 4.000: 98.830–101.733 operações

Número de operações no Push Swap para diferentes tamanhos de entrada.

Agora, para identificar a complexidade do algoritmo, precisamos comparar com as funções mais comuns.

Comparando com os tipos de complexidade

Já podemos descartar logo de cara as complexidades constante, logarítmica e linear: O(1), O(log n) e O(n). Por quê? A resposta é simples. Na complexidade constante, o número de operações seria o mesmo, independente do tamanho da entrada. Na linear, o número de operações cresceria na mesma proporção da entrada. Nossos resultados mostram que isso não acontece, então já descartamos a logarítmica também, porque ela cresce muito mais devagar do que a linear.

Agora vamos para a complexidade linearítmica, O(n log n). Se substituirmos os valores da nossa entrada na fórmula n×log₂​n, a gente obtém: 10 × log₂10 ≈ 33 20 × log₂20 ≈ 86 40 × log₂40 ≈ 212 80 × log₂80 ≈ 505 100 × log₂100 ≈ 664 200 × log₂200 ≈ 1.528 400 × log₂400 ≈ 3.457 1.000 × log₂1.000 ≈ 9.965 2.000 × log₂2.000 ≈ 21.931 4.000 × log₂4.000 ≈ 47.863

Agora, vamos ver a complexidade quadrática, O(n²). Substituindo os valores na fórmula n²: 10² = 100 20² = 400 40² = 1600 80² = 6.400 100² = 10.000 200² = 40.000 400² = 160.000 1.000² = 1.000.000 2.000² = 4.000.000 4.000² = 16.000.000

Comparando os resultados: fica claro que as saídas do nosso programa estão bem próximas da O(n log n), enquanto a quadrática dispara e fica absurdamente maior. Então não tem nem o que discutir: o comportamento é O(n log n).

É assim que a gente identifica a complexidade do algoritmo: testando e observando os resultados. É como em matemática: você substitui valores na função, vê os resultados, e daí consegue imaginar o gráfico e identificar o tipo de crescimento.

Observação: O resultado do algoritmo não precisa bater exatamente com os valores da complexidade. O que importa são os piores casos. E o Big-O não é rígido como outras notações, ele serve justamente pra simplificar.

Por exemplo: no caso da entrada de 2.000, o nosso Push Swap deu algo entre 35.503 e 37.986 operações, enquanto 2.000 × log₂2.000 = 21.931. Não é igual, mas lembra do que falei? O Big-O simplifica a função original, focando só no termo que cresce mais rápido. Na prática, o número de operações do algoritmo não é só n log n. Ele pode ser algo do tipo:

f(n) ≈ a·n log n + b·n + c

onde a, b e c são constantes que variam conforme a implementação. Esses termos extras fazem os valores subirem mais do que o n log n puro, principalmente em entradas maiores. Mas, no fim, o crescimento dominante continua sendo o n log n. É justamente por isso que a nós usamos o Big-O: pra ignorar esses detalhes e focar no comportamento que realmente importa quando n cresce.

Se você chegou até aqui, muito obrigado pela leitura. Espero que este artigo tenha ajudado a clarear um pouco mais o que é complexidade de algoritmos e como ela se aplica no Push Swap.

Ficarei muito feliz se você deixar um comentário com suas impressões, críticas ou correções caso tenha encontrado algum erro no conteúdo. O feedback de vocês é essencial para melhorar.

Se achou útil, compartilhe com seus colegas ou amigos programadores — pode ser que ajude alguém que esteja passando pelas mesmas dificuldades. E claro, se quiser acompanhar mais conteúdos como este, siga-me 😁.

Abaixo deixo algumas referências para quem quiser se aprofundar ainda mais no tema.

Referências

Livro Entendendo Algoritmos by Aditya Y. Bhargava

[embed]Complexidade computacional - Wikipédia, a enciclopédia livre A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática…pt.wikipedia.org

[embed]Análise de algoritmos - Wikipédia, a enciclopédia livre Origem: Wikipédia, a enciclopédia livre. Em ciência da computação, a análise de algoritmos tem como função determinar…pt.wikipedia.org

https://en.wikipedia.org/wiki/Big_O_notation

https://docentes.ifrn.edu.br/demetrioscoutinho/disciplinas/algoritmos/03-complexidade

https://www.ime.usp.br/~song/mac5710/slides/01complex.pdf