← Voltar para Slide 16 (Aula 7) Cursos UNICAP Análise de Algoritmos — Polinomial vs. Exponencial (Slide 16)
📄 PDF Aula 7
› Aula 7: Introdução a Problemas P • Intuição Visual do Crescimento de Funções Prof. Pedro Ximenes • Semestre Letivo 2026.2

📈 Polinomial vs. Exponencial — Intuição Visual

Demonstração interativa do gráfico do Slide 16 da Aula 7 ↗. Observe como, para entradas pequenas ($n \le 9$), polinômios de grau alto como $n^3$ podem parecer maiores, mas a partir do limiar $n = 10$, a curva exponencial $2^n$ explode vertiginosamente e deixa qualquer polinômio para trás.

Curvas:
2ⁿ (Exponencial)
n³ (Polinomial)
n² (Polinomial)
n (Linear)
n⁴ (Polinomial)
Tamanho da Entrada: 10
⚡ Telemetria em Tempo Real (n = 10)
2ⁿ (Exponencial) Complexidade Exponencial
1.024
1.02 µs
n³ (Polinomial) Complexidade Cúbica
1.000
1.00 µs
n² (Polinomial) Complexidade Quadrática
100
0.10 µs
n (Linear) Complexidade Linear
10
0.01 µs
n⁴ (Polinomial) Complexidade Quártica
10.000
10.00 µs
Para n = 10, 2ⁿ (1.024) ultrapassa n³ (1.000) pela primeira vez!
🎯 Pontos Críticos para Mostrar em Aula

⏱️ O Teste da Realidade (CPU de 1 GHz = 10⁹ operações/segundo)

Comparação concreta do tempo necessário para resolver problemas com diferentes funções de complexidade:

Tamanho (n) Linear: n Quadrático: n² Cúbico: n³ Exponencial: 2ⁿ
n = 10 10 ns 100 ns 1 µs 1.02 µs
n = 20 20 ns 400 ns 8 µs 1.05 ms
n = 30 30 ns 900 ns 27 µs 1.07 segundos
n = 40 40 ns 1.6 µs 64 µs 18.3 minutos
n = 50 50 ns 2.5 µs 125 µs 13.0 dias ⚠️
n = 60 60 ns 3.6 µs 216 µs 36.5 anos 🛑
n = 100 100 ns 10 µs 1 ms 4×10¹³ anos (Idade Universo!)

💡 Lições Fundamentais da Aula 7 (Slide 16)

1.
Polinômios são Tratáveis (Tese de Cobham): Algoritmos polinomiais ($O(n^k)$) escalam de forma gerenciável. Dobrar o poder do processador permite resolver instâncias proporcionalmente maiores.
2.
Exponenciais são Intratáveis na Prática: Em algoritmos de força bruta ($O(2^n)$), adicionar apenas 1 elemento à entrada ($n \to n + 1$) dobra o tempo total de execução. Dobrar a velocidade da CPU adiciona apenas uma constante aditiva ao $n$ tratável.
3.
O Papel do Limiar $n_0$: Não se iluda com entradas pequenas ($n \le 5$). A análise assintótica se importa com o comportamento quando $n \to \infty$. A partir de $n = 10$, qualquer exponencial supera qualquer polinômio cúbico e cresce infinitamente mais rápido.
4.
Definição da Classe P: A Classe P é definida rigorosamente como a classe de todos os problemas de decisão que admitem um algoritmo com tempo de execução polinomial determinístico no pior caso ($O(n^k)$ para alguma constante $k$).