⚡ Aula 04 — Projeto de Algoritmos, Complexidade e Notação Assintótica Big-O

Navegação Rápida

📍 Disciplina: 02 Pensamento Computacional | 🗺️ Área: 06 Computação e Telecomunicações | 🏠 Hub Principal ⬅️ Aula Anterior: Aula 03 - Abstração e Modelagem Computacional | ➡️ Próxima Aula: Aula 05 - Representação Digital da Informação

---

📌 Sumário da Aula

1. 🧠 1. Fundamentos do Projeto de Algoritmos
2. 📐 2. Notação Assintótica Formal: Big-O, Big-Omega e Big-Theta
3. 📈 3. Classes Canônicas de Complexidade Temporal e Espacial
4. 🗺️ 4. Algoritmos em Grafos Elétricos: Dijkstra e Árvore Geradora Mínima
5. 📊 5. Diagrama de Notação Assintótica e Algoritmo de Dijkstra
6. 📝 6. Questões de Concursos e Problemas Avançados Resolvidos
7. 🔗 7. Conexões e Referências Cruzadas

---

🧠 1. Fundamentos do Projeto de Algoritmos

O quarto pilar do Pensamento Computacional é o Projeto de Algoritmos (Algorithm Design). Um algoritmo é definido formalmente como uma sequência finita, ordenada, não ambígua e mecanicamente executável de instruções de transformação lógica que recebe um conjunto de entradas válidas e produz uma saída determinística em tempo finito.

Para que um procedimento computacional seja considerado um algoritmo válido em engenharia, ele deve atender estritamente a cinco postulados fundamentais:

1. Finitude: O processo deve terminar após um número contável e limitado de passos de execução.
2. Definição / Não Ambiguidade: Cada instrução deve ser perfeitamente clara, sem margem a interpretações dúbias pela unidade de processamento.
3. Entradas Bem Definidas: O domínio das grandezas de entrada deve ser explicitado (por exemplo, tensões nodais $\mathbf{V}\in {\mathbb{C}}^N$).
4. Saídas Determinísticas: Deve produzir os resultados esperados associados às entradas dadas (por exemplo, fluxos de potência nos ramos ${\mathbf{S}}_{\text{ramo}}\in {\mathbb{C}}^M$).
5. Efetividade: Todas as operações matemáticas e lógicas devem ser suficientemente básicas para que possam, em princípio, ser executadas exatamente por um agente computacional com recursos físicos limitados.

---

📐 2. Notação Assintótica Formal: Big-O, Big-Omega e Big-Theta

A eficiência de um algoritmo não deve ser medida em segundos ou milissegundos absolutos de relógio, pois o tempo de parede (wall-clock time) varia dramaticamente em função da velocidade de clock da CPU, da tecnologia do compilador e da carga do sistema operacional.

A análise de algoritmos quantifica o consumo de operações fundamentais $T(n)$ e de memória $S(n)$ como uma função puramente matemática do tamanho da entrada $n$ quando $n\to \infty$ (comportamento assintótico).

flowchart LR
    BigO["Notação Big-O: O(g(n))<br/>Limite Superior Assintótico<br/>Pior Cenário Garantido"]
    BigTheta["Notação Big-Theta: Θ(g(n))<br/>Limite Justo / Exato<br/>Comportamento Assintótico Estrito"]
    BigOmega["Notação Big-Omega: Ω(g(n))<br/>Limite Inferior Assintótico<br/>Melhor Cenário Possível"]

    BigTheta --> BigO
    BigTheta --> BigOmega

2.1 Notação Big-O ($\mathcal{O}$) — Limite Superior Assintótico

Dadas as funções $f(n)$ e $g(n)$ definidas sobre os inteiros positivos, diz-se que $f(n)\in \mathcal{O}(g(n))$ se e somente se existirem constantes reais positivas $c>0$ e $n_0\ge 0$ tais que:

$\boxed{0\le f(n)\le c\cdot g(n),\forall n\ge n_0}$

Significado em Engenharia: Estabelece o teto de pior caso (worst-case upper bound). O algoritmo tem a garantia matemática de que jamais consumirá mais tempo de execução do que uma função proporcional a $g(n)$ para entradas suficientemente grandes.

2.2 Notação Big-Omega ($\Omega$) — Limite Inferior Assintótico

Diz-se que $f(n)\in \Omega (g(n))$ se e somente se existirem constantes reais positivas $c>0$ e $n_0\ge 0$ tais que:

$\boxed{0\le c\cdot g(n)\le f(n),\forall n\ge n_0}$

Significado em Engenharia: Estabelece o piso assintótico (lower bound). Nenhum algoritmo que resolva essa classe de problemas poderá ter um tempo menor que $g(n)$.

2.3 Notação Big-Theta ($\Theta$) — Limite Assintótico Estrito

Diz-se que $f(n)\in \Theta (g(n))$ se e somente se $f(n)$ estiver simultaneamente contida em $\mathcal{O}(g(n))$ e $\Omega (g(n))$. Isto é, existem constantes $c_1,c_2>0$ e $n_0\ge 0$ tais que:

$\boxed{0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n),\forall n\ge n_0}$

Significado em Engenharia: A função $g(n)$ descreve perfeitamente a taxa de crescimento assintótico do algoritmo, sem folgas superiores ou inferiores.

---

📈 3. Classes Canônicas de Complexidade Temporal e Espacial

A tabela a seguir sumariza a hierarquia assintótica, exemplificada com problemas clássicos de Engenharia Elétrica:

Classe de Complexidade	Notação Assintótica	Taxa de Crescimento para $n=10^3$	Aplicação Típica em Engenharia Elétrica
Constante	$\mathcal{O}(1)$	$1$ operação	Verificação de estado lógico de disjuntor em relé IED; leitura em tabela hash indexada
Logarítmica	$\mathcal{O}(\log n)$	$\approx 10$ operações	Busca binária de ponto de operação ótimo em tabela de calibração ordenada
Linear	$\mathcal{O}(n)$	$10^3$ operações	Varredura de telemetria de $n$ sensores de temperatura de transformador; cálculo de corrente RMS
Linear-Logarítmica	$\mathcal{O}(n\log n)$	$\approx 10^4$ operações	Transformada Rápida de Fourier (FFT de Cooley-Tukey); ordenação de eventos cronológicos
Quadrática	$\mathcal{O}(n^2)$	$10^6$ operações	DFT ingênua em sinais elétricos; multiplicação matricial densa ingênua; comparação par a par
Cúbica	$\mathcal{O}(n^3)$	$10^9$ operações	Eliminação de Gauss-Jordan para inversão de matrizes cheias sem esparsidade
Exponencial	$\mathcal{O}(2^n)$	$\approx 10^{301}$ operações	Despacho Unitário Hidrotérmico exaustivo (Unit Commitment); alocação combinatória exata

---

🗺️ 4. Algoritmos em Grafos Elétricos: Dijkstra e Árvore Geradora Mínima

4.1 Algoritmo de Dijkstra para Caminhos de Impedância Mínima

Em redes de distribuição urbanas interligadas, quando ocorre uma falta permanente (curto-circuito trifásico), o sistema de automação de rede (Self-Healing) deve isolar o trecho avariado e encontrar o caminho de menor impedância elétrica ou menor perda Joule para reenergizar os clientes sadios através de alimentadores adjacentes.

Dado um grafo elétrico ponderado $G=(\mathcal{V},\mathcal{E},w)$ onde os pesos das arestas $w(u,v)=R_{uv}\ge 0$ representam as resistências em ohms dos ramos:

flowchart TD
    Init["1. Inicialização<br/>d(s) = 0 para a subestação de origem s<br/>d(v) = ∞ para todas as demais barras v ≠ s<br/>Conjunto Q = V (todas as barras não visitadas)"] --> MinNode["2. Extrair Mínimo de Q<br/>u = nó em Q com menor distância d(u) estimada"]
    MinNode --> LoopArestas["3. Relaxamento das Arestas Adjacentes<br/>Para cada vizinho v de u:"]
    LoopArestas --> Rel{"d(u) + w(u,v) < d(v)?"}
    Rel -- Sim --> Atualiza["d(v) = d(u) + w(u,v)<br/>predecessor(v) = u"]
    Rel -- Não --> ProxViz["Manter d(v)"]
    Atualiza --> Remov["Remover u de Q"]
    ProxViz --> Remov
    Remov --> Cond{"Q está vazio?"}
    Cond -- Não --> MinNode
    Cond -- Sim --> Fim["Árvore de Caminhos Mínimos Calculada"]

Equação de Relaxamento de Arestas

$\boxed{d(v)\leftarrow \min (d(v),d(u)+w(u,v))}$

Complexidade Computacional de Dijkstra:

• Implementação com Vetor Simples: $T_{\text{ingeˆnuo}}(V,E)=\mathcal{O}(V^2+E)=\mathcal{O}(V^2)$
• Implementação Otimizada com Fila de Prioridade (Min-Heap Binário): A extração do nó mínimo custa $\mathcal{O}(\log V)$ executada $V$ vezes, e a atualização de chave (decrease-key) custa $\mathcal{O}(\log V)$ executada no máximo $E$ vezes: $\boxed{T_{\text{heap}}(V,E)=\mathcal{O}((V+E)\log V)}$

Para uma rede de distribuição metropolitana com $V=10000$ nós e $E=15000$ ramos:

• Implementação ingênua: $\sim 10^8$ operações;
• Implementação com Min-Heap: $\sim 25000\times {\log }_2(10000)\approx 25000\times 13,3\approx 3,3\times 10^5$ operações — uma aceleração de $\approx 300$ vezes, permitindo recomposição automática em menos de $100\text{ ms}$.

4.2 Árvore Geradora Mínima (MST) no Planejamento de Cabeamento

Ao projetar a interligação de turbinas eólicas em um parque eólico offshore até a subestação coletora central, deseja-se minimizar o comprimento total de cabos submarinos isolados de média tensão ($34,5\text{ kV}$).

Esse problema é modelado como a busca da Árvore Geradora Mínima (Minimum Spanning Tree - MST) de um grafo não direcionado conexo. Os dois algoritmos fundamentais são:

1. Algoritmo de Kruskal: Baseado em ordenação gulosa das arestas e detecção de ciclos através da estrutura de dados de Conjuntos Disjuntos (Union-Find com compressão de caminhos). Complexidade: $\mathcal{O}(E\log E)$.
2. Algoritmo de Prim: Cresce uma árvore conectada a partir de um vértice raiz selecionando a aresta de corte de menor peso. Complexidade: $\mathcal{O}(E+V\log V)$ usando Fibonacci Heap.

---

📊 5. Diagrama de Notação Assintótica e Algoritmo de Dijkstra

O diagrama abaixo, elaborado na estética Catppuccin Mocha, ilustra visualmente a taxonomia da notação Big-O e a mecânica de relaxamento do algoritmo de Dijkstra:

---

📝 6. Questões de Concursos e Problemas Avançados Resolvidos

Questão 1 (Banca CESPE/CEBRASPE - Engenheiro de Redes e Telecomunicações)

Considere dois algoritmos $A_1$ e $A_2$ desenvolvidos para processamento de transitórios eletromagnéticos em linhas de transmissão contendo $n$ pontos de amostragem no tempo:

• O algoritmo $A_1$ requer exatamente $f_1(n)=100n{\log }_{2}n$ operações;
• O algoritmo $A_2$ requer exatamente $f_2(n)=2n^2$ operações.

Determine o valor limite de $n^{\ast }$ a partir do qual o algoritmo $A_1$ torna-se rigorosamente mais rápido do que o algoritmo $A_2$ e avalie suas respectivas complexidades assintóticas na notação Big-O.

Resolução Passo a Passo:

1. Complexidades Assintóticas:

   • Para $A_1$: $f_1(n)\in \mathcal{O}(n\log n)$
   • Para $A_2$: $f_2(n)\in \mathcal{O}(n^2)$

2. Ponto de Cruzamento ($f_1(n)=f_2(n)$): $100n{\log }_{2}n=2n^2$ Para $n>0$, dividem-se ambos os lados por $2n$: $50{\log }_{2}n=n⟹\frac{n}{{\log }_{2}n}=50$

   Testando valores inteiros de $n$:

   • Para $n=256=2^8$: ${\log }_2(256)=8⟹\frac{256}{8}=32<50$
   • Para $n=512=2^9$: ${\log }_2(512)=9⟹\frac{512}{9}\approx 56,88>50$

   Refinando a busca entre 400 e 500:

   • Para $n=430$: ${\log }_2(430)\approx 8,748⟹\frac{430}{8,748}\approx 49,15$
   • Para $n=437$: ${\log }_2(437)\approx 8,771⟹\frac{437}{8,771}\approx 49,82$
   • Para $n=439$: ${\log }_2(439)\approx 8,778⟹\frac{439}{8,778}\approx 50,01$

   Portanto, para $n\ge 439$, tem-se $f_1(n)<f_2(n)$.

$\boxed{n^{\ast }=439\text{ amostras}}$

Análise Crítica: Embora para pequenas janelas amostrais ($n<439$) a constante elevada de $A_1$ ($c=100$) o torne mais lento que $A_2$ ($c=2$), a taxa de crescimento linear-logarítmica de $A_1$ supera assintoticamente o crescimento quadrático de $A_2$. Para um milhão de amostras ($n=10^6$), $A_1$ executa $\approx 2\times 10^9$ operações, enquanto $A_2$ exigiria $2\times 10^{12}$ operações (mil vezes mais lento).

---

Questão 2 (Banca VUNESP - Engenharia de Automação / Concurso Público)

Um sistema computacional embarcado em um relé de proteção digital realiza a busca de faltas em um banco de registros históricos de oscilografia contendo $N$ registros ordenados cronologicamente. Um estagiário de engenharia implementou inicialmente uma busca linear sequencial. O engenheiro sênior substituiu esse código por uma busca binária clássica. Se o banco de dados armazena $N=1048576$ registros, qual é o número máximo de comparações no pior caso para cada algoritmo?

Resolução Passo a Passo:

1. Busca Linear Sequencial ($\mathcal{O}(N)$): No pior caso (o elemento procurado está na última posição ou não pertence ao vetor), o algoritmo compara o registro com cada um dos $N$ elementos: $C_{\text{linear}}=N=1048576\text{ comparac¸o˜es}$

2. Busca Binária ($\mathcal{O}({\log }_{2}N)$): A cada iteração, a busca binária divide o espaço de busca pela metade. O número máximo de comparações no pior caso é dado por: $C_{\text{binaˊria}}=\lfloor {\log }_{2}N\rfloor +1$ Como $N=1048576=2^{20}$: $C_{\text{binaˊria}}=20+1=21\text{ comparac¸o˜es}$

$\boxed{C_{\text{linear}}=1048576;C_{\text{binaˊria}}=21}$

Conclusão: A otimização algorítmica reduziu o esforço de processamento de mais de um milhão de acessos à memória para apenas 21 passos discretos, permitindo a atuação do relé em frações infinitesimais de microssegundo.

---

Questão 3 (Problema Prático de Engenharia - Algoritmo de Dijkstra em Malha Elétrica)

Considere uma microrrede elétrica contendo 4 barras $\mathcal{V}=\{1,2,3,4\}$ e as seguintes resistências de condutores entre as barras conectadas:

• Ramo $(1,2)$: $R_{12}=3\Omega$
• Ramo $(1,3)$: $R_{13}=1\Omega$
• Ramo $(2,4)$: $R_{24}=2\Omega$
• Ramo $(3,2)$: $R_{32}=1\Omega$
• Ramo $(3,4)$: $R_{34}=5\Omega$

Determine o caminho de menor resistência ôhmica total partindo da Barra 1 (gerador) até a Barra 4 (carga crítica) através do algoritmo de Dijkstra passo a passo.

Resolução Passo a Passo:

1. Inicialização:

   • $d(1)=0$, $d(2)=\infty$, $d(3)=\infty$, $d(4)=\infty$.
   • Predecessores: $\pi (v)=\text{null}$.
   • $Q=\{1,2,3,4\}$.

2. Iteração 1:

   • Vértice com menor $d(u)$ em $Q$: $u=1$ ($d(1)=0$).
   • Relaxar vizinhos de 1:
     • Vizinho 2: $d(1)+R_{12}=0+3=3<\infty ⟹d(2)\leftarrow 3$, $\pi (2)\leftarrow 1$.
     • Vizinho 3: $d(1)+R_{13}=0+1=1<\infty ⟹d(3)\leftarrow 1$, $\pi (3)\leftarrow 1$.
   • Remover 1 de $Q$. Estado: $Q=\{2,3,4\}$, com $d=[0,3,1,\infty ]$.

3. Iteração 2:

   • Vértice com menor $d(u)$ em $Q$: $u=3$ ($d(3)=1$).
   • Relaxar vizinhos de 3:
     • Vizinho 2: $d(3)+R_{32}=1+1=2<d(2)=3$ (relaxamento realizado!) $⟹d(2)\leftarrow 2$, $\pi (2)\leftarrow 3$.
     • Vizinho 4: $d(3)+R_{34}=1+5=6<\infty ⟹d(4)\leftarrow 6$, $\pi (4)\leftarrow 3$.
   • Remover 3 de $Q$. Estado: $Q=\{2,4\}$, com $d=[0,2,1,6]$.

4. Iteração 3:

   • Vértice com menor $d(u)$ em $Q$: $u=2$ ($d(2)=2$).
   • Relaxar vizinhos de 2:
     • Vizinho 4: $d(2)+R_{24}=2+2=4<d(4)=6$ (relaxamento realizado!) $⟹d(4)\leftarrow 4$, $\pi (4)\leftarrow 2$.
   • Remover 2 de $Q$. Estado: $Q=\{4\}$, com $d=[0,2,1,4]$.

5. Iteração 4:

   • Vértice com menor $d(u)$ em $Q$: $u=4$ ($d(4)=4$). Não há arestas saindo de 4 a relaxar.
   • Remover 4 de $Q$. $Q=\varnothing$. Terminação.

6. Reconstrução do Caminho:

   • $4\stackrel{\pi }{\leftarrow }2\stackrel{\pi }{\leftarrow }3\stackrel{\pi }{\leftarrow }1$.

$\boxed{\text{Caminho Mıˊnimo: }1\to 3\to 2\to 4\text{com Resisteˆncia Total }{R}_{\text{total}}=4\Omega }$

Nota de Engenharia: Embora a aresta direta de 1 para 2 meça $3\Omega$, o percurso passando pela barra intermediária 3 ($1\to 3\to 2$) resulta em apenas $1+1=2\Omega$, ilustrando como o algoritmo encontra desvios elétricos com menor perda dissipativa total.

---

🔗 7. Conexões e Referências Cruzadas

Disciplinas Vinculadas:

• Aula 03: Teoria dos grafos elétricos e matrizes topológicas.
• Aula 05: Complexidade de algoritmos de processamento de imagens.
• 01 Lógica de Programação: Laços de repetição e complexidade ciclomática.
• 07 Planejamento e Análise de SEP: Algoritmos de Newton-Raphson e Fatoração LU de matrizes esparsas.

Materiais Didáticos Oficiais da Disciplina:

• Arquivo de Curso: 02 - Fundamentos de Softwares de Computadores.pdf
• Arquivo de Curso: 05 - Noções de Programação - Exemplos Com Manipulação de Imagens Digitais.pdf
• Arquivo de Prática: 07 - Praticando.pdf