RESUMO - Algoritmos e complexidade - Estácio

Prévia do material em texto

TEMA 2 - ANÁLISE DE ALGORITMO
Introdução
🔹 1. Conceito de Algoritmo
· Algoritmos são a base para resolver problemas em computação.
· Eles indicam o passo a passo para alcançar uma solução.
🔹 2. Modularização de Algoritmos
· Modularizar significa dividir o algoritmo em partes menores chamadas módulos ou subprogramas.
· Vantagens:
· Torna o problema mais fácil de entender.
· Facilita manutenção futura.
· Permite reutilização de código (evita retrabalho).
🔹 3. Otimização de Algoritmos
· Depois de criar o algoritmo, ele deve ser otimizado.
· Mesmo com computadores potentes, um algoritmo otimizado:
· Roda mais rápido.
· Usa menos memória.
· Oferece melhor experiência ao usuário.
🔹 4. Importância da Otimização
· A complexidade dos problemas cresceu junto com o poder dos computadores.
· É importante comparar diferentes algoritmos para escolher o mais eficiente.
Módulo 1. Definir os conceitos básicos para construção de algoritmos
🔹 1. Diferença entre Complexidade Matemática e Algorítmica
· Problemas matemáticos: são mais complexos quanto maior o número de variáveis.
· Problemas algorítmicos: são mais complexos quanto maior o número de situações diferentes a serem tratadas.
🔹 2. O que é um Algoritmo?
· É uma sequência finita de passos bem definidos para resolver um problema.
· É a base da programação: todo programa de computador nasce de um algoritmo.
🔹 3. Complexidade do Algoritmo
· Está ligada à complexidade do problema.
· Mais situações diferentes para tratar → mais complexo.
· A complexidade pode ser reduzida, reduzindo-se a variedade de problemas
· E a variedade de pode ser reduzida se o problema for dividido em partes menores.
🔸 Exemplo de Complexidade Algorítmica: Imagine que você está programando um caixa eletrônico:
· Situação simples: apenas sacar dinheiro.
· Situação complexa: sacar, transferir, pagar contas, recarregar celular etc.
➡ Quanto mais situações o algoritmo precisa prever, mais complexo ele é.
🔹 4. Subdivisão de Problemas – Estratégia Top-Down
· Definição: É uma técnica de decomposição de problemas em partes menores.
· Identifica sub-rotinas que resolvem tarefas específicas.
· De cima para baixo: começa pelo problema grande, depois divide.
🔹 5. Sub-rotinas (ou Subprogramas)
· Definição: São blocos de código que resolvem tarefas específicas.
· Tornam o código:
· Mais simples.
· Menos sujeito a erros.
· Mais organizado e reutilizável.
· Devem ser focadas em resolver apenas um problema específico.
🔹 6. Objetivos das Sub-rotinas
· Dividir o algoritmo em partes logicamente coerentes.
· Permitir testar cada parte separadamente.
· Melhorar a leitura e organização do código.
· Evitar repetição de código.
🔹 7. Vantagens das Sub-rotinas
· Garante mais clareza, organização e facilita a leitura do algoritmo.
· Desenvolvimento independente
· Testes individualizados e mais fáceis.
· Manutenção simplificada.
· Reaproveitamento de código em outros programas.
· Permite a criação de bibliotecas próprias de funções.
🔹 8. Decomposição de Problemas
· A programação estruturada é indicada para aplicar a decomposição de problemas.
· A maioria das linguagens modernas suporta esse paradigma.
· O método top-down é o mais adequado para decompor problemas (segundo Manzano e Oliveira, 2016).
🔹 9. Método Top-Down
· Possui estrutura semelhante a um organograma.
· Baseia-se em refinamentos sucessivos: divide-se o problema em partes menores.
· Cada parte gerada torna-se um módulo ou sub-algoritmo do programa.
 
🔹 10. Sub-rotina
· Também chamada de subprograma ou módulo.
· Serve para executar tarefas específicas e menores, como:
· Ler dados, calcular, comparar valores, ordenar, converter letras, etc.
· Tem nome próprio, pode ser chamada de qualquer parte do programa.
· Pode realizar operações de entrada, processamento e saída.
🔹 11. Estrutura Geral de uma Sub-rotina
sub-rotina [(tipo dos parâmetros : )] : 
 var
 ;
 Início
 comandos que formam o corpo da sub-rotina
 retorne() ; /* ou retorne; ou nada */
Fim sub-rotina
· Em uma função são obrigatórios: o nome, tipo de retorno e corpo da função.
· corpo da sub-rotina: Sequência de comandos.
· nome da sub-rotina: Segue as mesmas regras de declaração de variáveis da linguagem utilizada. 
· Sequência de declarações de parâmetros: Declarações de variáveis da sub-rotina (tipo e nome). Os parâmetros em funções não são obrigatórios. 
· parâmetros: Nomes das variáveis, seguem as mesmas regras de declaração de variáveis da linguagem utilizada. 
· variáveis locais: Declarações de variáveis que serão utilizadas dentro da sub-rotina (tipo e nome). 
· Início: Início da sub-rotina.
· tipo de retorno: Tipo de dado que a sub-rotina dará retorno. 
· retorne ( ... ): O que será retornado ou não para o algoritmo. 
· Fim sub-rotina: Fim da sub-rotina.
🔹 5. Posição da Sub-rotina no Algoritmo
· Deve ser posicionada entre a declaração de variáveis e o início do programa principal.
· Ou seja, acima do programa principal.
Exemplo em Pseudocódigo – Soma de dois números
// Declaração de variáveis
var
 n, m: inteiro;
// Declaração de sub-rotina
sub-rotina soma(inteiro: a, b): inteiro
var
 resultado: inteiro;
início
 resultado = a + b;
 retorne resultado;
fim sub-rotina
//Programa principal
início
 n = 8;
 m = 4;
 escreva(soma(n, m)); //chamada da sub-rotina (soma)
fim Algoritmo.
🐍 Exemplo em Python – Soma de dois inteiros com função
# Definição da função que soma dois números inteiros
def soma(a, b):
    resultado = a + b
    return resultado
# Programa principal
n = 8
m = 4
# Chamada da função e exibição do resultado
print(soma(n, m))
# Saída no terminal: 12
Chamada de Sub-rotinas e Parâmetros
🔹 O que é uma sub-rotina? É um bloco de código (também chamado de função ou procedimento) que realiza uma tarefa específica. 
🔹 Chamada de sub-rotina
· O acionamento de uma sub-rotina é conhecido por chamada ou ativação.
· A sub-rotina pode ser chamada (ativada) a partir de qualquer ponto do algoritmo principal ou de outra sub-rotina.
🔹 O que acontece quando uma sub-rotina é chamada?
· O controle do programa é desviado para a sub-rotina.
· Após sua execução, o controle retorna para o ponto onde ela foi chamada, continuando o fluxo normal do programa.
🧠 Exemplo: O exemplo abaixo mostra um algoritmo com duas sub-rotinas sendo chamadas, veja que o fluxo de execução passa para a sub-rotina chamada (primeira sub-rotina). Ao final da execução da primeira sub-rotina, o controle retorna para o programa principal.
O mesmo procedimento ocorre com a chamada para a segunda sub-rotina, ao final da execução o controle retorna para o programa principal que segue o seu fluxo normal de execução, conforme a figura:
🔹 Sub-rotinas com parâmetros:
· Sub-rotinas podem receber valores de entrada chamados parâmetros.
· Isso torna a sub-rotina mais genérica e reutilizável.
· Definição de Parâmetros: são os valores que uma sub-rotina pode receber antes de iniciar a sua execução.
🔹 Tipos de passagem de parâmetros:
1. Por valor:
· A sub-rotina recebe uma cópia do valor da variável.
· Alterações que ocorrem dentro da sub-rotina não afetam a variável original.
2. Por referência:
· A sub-rotina manipula diretamente a variável original.
· Alterações feitas dentro da sub-rotina afetam a variável original.
🔹 Tipos de sub-rotinas:
· Funções: Recebem parâmetros e retornam um valor.
· Procedimentos: Recebem parâmetros mas não retornam valor.
🧪 Exemplos em Python
📌 Exemplo 1: O exemplo abaixo utiliza o conceito de parâmetros para trocar o valor de dois números recebidos como parâmetros.
def troca(x, y):
    auxiliar = x
    x = y
    y = auxiliar
    print("Valor de a:", x)
    print("Valor de b:", y)
# Programa principal
a = 10
b = 5
troca(a, b)
print("Fora da função:")
print("Valor de a:", a)  # Continua 10
print("Valor de b:", b)  # Continua 5
# Saída no terminal:
Valor de a: 5
Valor de b: 10
Fora da função:
Valoressa “explosão” exponencial de chamadas para o cálculo de Fibonacci (4):
· Mostra como as chamadas se acumulam:
· Várias chamadas repetidas (ex: fibonacci(2) aparece várias vezes).
· Repetições causam desperdício de recursos.
· É vital que a quantidade de chamadas recursivas seja finita, pois funções recursivas utilizam bastante memória.
🔸 Exemplo: Cálculo da sequência de Fibonacci (Figura 9 e 10) – Versão iterativa
#include 
int main() {
    int n, i;
    int a = 1, b = 1, temp;
    printf("Digite a quantidade de termos da série: ");
    scanf("%d", &n);
    printf("Sequência de Fibonacci é:\n");
    // Imprime os primeiros termos
    if (n >= 1)
        printf("1 ");
    if (n >= 2)
        printf("1 ");
    for (i = 3; i n, termina.
início​
  soma n:
        return soma
    return calc_sigma(ind + 1, n, soma + ind)
# Exemplo:
print(calc_sigma(1, 5))  # Saída: 15
🧠 Exemplo 2: Raiz quadrada com aproximação (método de Newton)
🔍 Problema: Encontrar uma aproximação da raiz quadrada de um número x.
 Lógica recursiva:
· Parte de um palpite inicial r.
· Se r² estiver suficientemente próximo de x, retorna r.
· Caso contrário, atualiza r usando: 
e chama a função novamente.
proc raiz : real(x : real, r : real, tol : real)​
  Se | x – r2 | 1, ignora os primeiros caracteres até alcançar a posição p.
· Depois começa a construir a subcadeia com n caracteres restantes.
proc subcadeia : cadeia (c: cadeia, p : int, n: int)​​
  Se n = 0
    Então​
      retorne “ ”​
    Senão;​​​​
      Se p > 1​
        Então​​​​​​​​
          retorne subcadeia (cont c, p – 1, n)​ ​
        Senão ​
          retorne subcadeia( cont c, 1, n – 1);​​ ​
      fim-se; ​
  fim-se;​
🟢 Exemplo simplificado:
· subcadeia("abcdef", 3, 2) retorna "cd"
· Para melhor compreensão segue código em Python:
def subcadeia(c, p, n):
    if n == 0:
        return ""
    if p > 1:
        return subcadeia(c[1:], p - 1, n)
    else:
        return c[0] + subcadeia(c[1:], 1, n - 1)
# Exemplo:
print(subcadeia("abcdef", 3, 2))  # Saída: "cd"
Vai ignorando os primeiros p-1 caracteres e depois retorna os n seguintes.
🧠 Exemplo 4: Soma de elementos de um vetor por recursão
🔍 Problema: Somar todos os elementos de um vetor v com n posições.
🔁 Lógica recursiva (somavet):
· Se n = 0, retorna 0 (caso base).
· Caso contrário, soma v[n] com o resultado da função para n - 1.
proc somavet : int (v: vetor, n: int)​
  Se n = 0
    Então​
      retorne 0;
    Senão;​​​​
      retorne v [ n ] + somavet (v, n – 1)
🟢 Exemplo simplificado:
· Para v = [1, 2, 3] e n = 3:
· v[3] + somavet(v, 2) → 3 + (2 + (1 + 0)) = 6
· Para melhor compreensão segue código em Python:
✅ 4. Soma de elementos de um vetor (recursivo)
def soma_vetor(v, n):
    if n == 0:
        return 0
    return v[n - 1] + soma_vetor(v, n - 1)
# Exemplo:
vetor = [1, 2, 3, 4, 5]
print(soma_vetor(vetor, len(vetor)))  # Saída: 15
A função pega o último elemento e soma com a chamada recursiva para o restante.
🧠 Exemplo 5: Busca Binária em Vetor por pesquisa binária
🔍 Problema: Verificar se o valor r está presente em um vetor ordenado v[1...10].
🔁 Lógica: O procedimento pesqbin inicia a busca chamando pesqrec(1,10).
🔁 Função recursiva pesqrec(i, j):
· Se i == j, verifica se v[i] == r.
· Caso contrário:
· Divide o vetor ao meio.
· Busca em cada metade de forma recursiva.
proc pesqbin : log (v : vet [1...10] : real, r : real)​
  var​
    i, j : int;​​
  início​
    retorne pesqrec (1, 10);​​​​​
  fim
🟢 Exemplo simplificado:
Procurar 5 em v = [1, 3, 5, 7, 9]:
· Primeira chamada: intervalo 1 a 5 → meio = 3 → v[3] = 5
· Encontrado! Retorna verdadeiro.
· Para melhor compreensão segue código em Python:
# Função Recursiva de Busca Binária
def busca_binaria_rec(v, r, i, j):
    if i > j:
        return False  # Valor não encontrado
    meio = (i + j) // 2
    if v[meio] == r:
        return True  # Valor encontrado
    elif rna metade esquerda.
· Se r for maior, busca na metade direita.
· Repete esse processo recursivamente até encontrar o valor ou até i > j (fim da busca sem sucesso).
📌 Conclusão
· A recursão é uma técnica poderosa para resolver problemas que envolvem repetição ou decomposição.
· Os exemplos apresentados mostram que muitos problemas iterativos podem ser reescritos de forma recursiva, muitas vezes com código mais limpo e lógico.
· No entanto, é importante cuidar do caso base para evitar loops infinitos e uso excessivo da memória.
✅ Exemplos de emprego dos algoritmos recursivos
🧠 Exemplo 1: Torre de Hanói (com Recursividade) 
· Objetivo: Mover todos os discos da haste Origem para a Destino, usando uma haste Temporária.
· Regras:
· Só um disco pode ser movido por vez.
· Um disco maior nunca pode ficar sobre um menor.
· Passos da solução recursiva:
3. Mover n-1 discos da haste Origem para a Temporária.
3. Mover o maior disco (disco n) para a Destino.
3. Mover os n-1 discos da Temporária para a Destino.
· Exemplo simples com 3 discos:
A função mover(n, Orig, Temp, Dest) chama a si mesma duas vezes para resolver os subproblemas de n-1 discos.
// Resolve o jogo da Torre de Hanói utilizando recursão
#include 
#include 
// protótipo da função recursiva
void mover(int n, char Orig, char Temp, char Dest);
int main() {
    mover(3, 'O', 'T', 'D');    
    system("pause");
    return 0;
}
void mover(int n, char Orig, char Temp, char Dest) {
    if (n == 1)
        printf("\nMova o disco 1 da haste %c para a haste %c\n", Orig, Dest);
    else {
        mover(n - 1, Orig, Dest, Temp);
        printf("\nMova o disco %d da haste %c para a haste %c\n", n, Orig, Dest);
        mover(n - 1, Temp, Orig, Dest);
    }
}
A saída para o programa será a seguinte: 
· Mova o disco 1 da haste O para a haste D
· Mova o disco 2 da haste O para a haste T
· Mova o disco 1 da haste D para a haste T
· Mova o disco 3 da haste O para a haste D
· Mova o disco 1 da haste T para a haste O
· Mova o disco 2 da haste T para a haste D
· Mova o disco 1 da haste O para a haste D
🧠 Exemplo 2: Fatorial de um número
🔸 Sem Recursividade
· Usa um laço for para multiplicar os números de n até 1.
· Exemplo: Fatorial de 5:
· 5 × 4 × 3 × 2 × 1 = 120
🔸 Com Recursividade
· A função fat(n) chama a si mesma com n - 1, até n == 0, quando retorna 1.
· Critério de parada: n == 0
· Exemplo passo a passo para fat(5):
fat(5) → 5 × fat(4)
fat(4) → 4 × fat(3)
fat(3) → 3 × fat(2)
fat(2) → 2 × fat(1)
fat(1) → 1 × fat(0)
fat(0) → 1 (caso base)
Resultado: 5 × 4 × 3 × 2 × 1 = 120
// cálculo do fatorial de um número sem o uso da recursividade
#include 
#include 
int main()
{
    int fat, n;
    printf("Insira um valor para o qual deseja calcular seu fatorial: ");
    scanf("%d", &n);
    for(fat = 1; n > 1; n--)
    {
        fat = fat * n;
    }
    printf("\nFatorial calculado: %d", fat);
    return 0;
}
A saída para o programa será a seguinte: 
· Insira um valor para o qual deseja calcular seu fatorial: 5
· Fatorial calculado: 120
// cálculo do fatorial de um número com o uso da recursividade
#include // Adicionado para printf e scanf
#include 
// protótipo da função recursiva fat()
int fat(int);
int main()
{
    int n;
    printf("\n\nDigite um valor para n: "); 
    scanf("%d", &n);                       
    printf("\nO fatorial de %d e' %d\n", n, fat(n)); 
    return 0;
}
// função recursiva fat()
int fat(int n)
{
    if(n)
    {
        return n * fat(n - 1);
    }
    else
    {
        return 1;
    }
}
A saída para o programa será a seguinte: 
· Digite um valor para n: 6
· O fatorial de 6 é 720
🧠 Exemplo 3: Sequência de Fibonacci
🔸 Sem Recursividade
· Usa um laço for para somar os dois últimos termos e gerar os próximos.
· Início com a = 0 e b = 1
· Exemplo para n = 10:
· Saída: 1 1 2 3 5 8 13 21 34 55
🔸 Com Recursividade
· A função fibonacci(n) retorna:
· 1 se n == 1 ou n == 2
· fibonacci(n-1) + fibonacci(n-2) para os demais casos.
· Exemplo passo a passo para fibonacci(5):
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(2) = 1
fibonacci(1) = 1
Resultado: fibonacci(5) = 3 + 2 = 5
// cálculo da sequência de Fibonacci sem o uso da recursividade
#include 
void main()
{
    int a, b, auxiliar, i, n;
    a = 0;
    b = 1;
    printf("Digite um número: ");
    scanf("%d", &n);
    printf("Série de Fibonacci:\n");
    printf("%d\n", b);
    for(i = 1; i 
#include 
// protótipo da função Fibonacci
int fibonacci(int); 
int main()
{
    int n, i;
    printf("Digite a quantidade de termos da sequência de Fibonacci: ");
    scanf("%d", &n);
    printf("\nA sequência de Fibonacci e: \n");
    for(i = 0; iordenação?
· É um método que organiza os elementos de uma sequência (como números ou nomes) em uma ordem definida (crescente ou decrescente).
📂 Classificação dos Algoritmos de Ordenação
1. Ordenação Interna (in-place)
· Utilizada quando todos os dados cabem na memória principal (RAM).
· A ordenação acontece inteiramente na memória.
· Os dados estão geralmente em vetores ou tabelas, e a ordenação é feita com base em uma chave (como número ou nome). 
· Mais rápida do que a ordenação externa, por não depender de leitura/escrita em disco.
2. Ordenação Externa
· Utilizada quando o volume de dados é grande e não cabe na memória principal.
· Envolve leitura e escrita frequente em disco rígido, fitas ou outros meios de armazenamento secundário. 
· Otimizada para reduzir o número de acessos a disco.
· É comum em bancos de dados e sistemas com arquivos grandes. 
	Algoritmo
	Classificação
	Observação
	Bubble Sort
	Interna
	Todos os dados precisam estar na memória RAM para comparação e troca.
	Selection Sort
	Interna
	Opera sobre vetores carregados inteiramente na memória.
	Merge Sort
	Interna ou Externa
	Pode ser usado como ordenação interna (dados pequenos) ou externa (dados grandes que não cabem na memória).
	Quick Sort
	Interna
	Muito eficiente para ordenação interna; exige que os dados estejam na memória.
	Heap Sort
	Interna
	Utiliza uma estrutura de heap construída na memória.
	Shell Sort
	Interna
	Baseado em inserção com saltos; executado inteiramente na memória.
· Somente o Merge Sort pode ser classificado como interna ou externa, dependendo do volume de dados e da implementação.
· Os demais são exclusivamente algoritmos de ordenação interna.
🔧 Principais Tipos de Algoritmos de Ordenação
✅ Ordenação por Inserção
· Os elementos são inseridos na posição correta um a um.
· Exemplos:
· Insertion Sort (inserção direta): Insere cada novo elemento na posição correta da parte já ordenada.
🔁 Ordenação por Troca
· Os elementos trocam de posição até estarem na ordem correta.
· Exemplos:
· Bubble Sort (bolha): Compara dois elementos vizinhos e os troca se estiverem fora de ordem, repetidamente.
· Quick Sort (troca e partição): Escolhe um pivô e divide os dados em partes menores, ordenando cada uma separadamente.
🔎 Ordenação por Seleção
· O algoritmo seleciona repetidamente o menor (ou maior) elemento e o coloca na posição correta.
· Exemplos:
· Selection Sort (seleção direta): Encontra o menor valor e o move para a frente da lista.
· Heap Sort (seleção em árvore): Usa uma estrutura de árvore (heap) para organizar e ordenar os dados.
🔁 Algoritmos de Ordenação Interna
· Ordenam dados armazenados em memória principal (geralmente em arrays ou vetores).
· A seguir, três algoritmos básicos com complexidade O(n²) no pior caso:
🫧 Bubble Sort (Ordenação por Bolha)
🔷 O que é o Bubble Sort?
· Também chamado de "ordenação por bolha".
· É um dos algoritmos de ordenação mais simples e mais conhecidos.
· Serve para ordenar dados armazenados em arrays (ou vetores), do menor para o maior ou vice-versa.
🔧 Como o algoritmo funciona (passo a passo)?
1. Comparações em pares:
· Cada elemento é comparado com o próximo.
· Se estiverem fora de ordem, eles são trocados de lugar.
2. Repetição das comparações:
· As comparações são repetidas até que nenhuma troca seja mais necessária.
· Isso indica que o vetor está ordenado.
🎈 Por que o nome “bolha”?
· Ao comparar e trocar os valores, os maiores valores “sobem” para o final do vetor.
· Se imaginarmos o vetor como um tubo com líquido, os maiores elementos se comportam como bolhas subindo.
💡 Exemplo simples explicado
Suponha o vetor: [54, 26, 93, 17, 77]
1. Compare 54 e 26 → troca → [26, 54, 93, 17, 77]
2. Compare 54 e 93 → sem troca
3. Compare 93 e 17 → troca → [26, 54, 17, 93, 77]
4. Compare 93 e 77 → troca → [26, 54, 17, 77, 93]
✅ Agora 93 está no final — o maior valor foi empurrado. 
Na próxima rodada, o processo se repete sem precisar incluir o último elemento, pois ele já está no lugar certo.
🧑‍💻 Código do algoritmo em C (simplificado)
void bolha (int *v)    // Função que implementa o algoritmo Bubble Sort em um vetor de inteiros
{
    int troca = 1;    // Variável de controle que indica se houve troca na passada atual (inicia como verdadeiro)
    int i = 0;       // Índice usado para percorrer o vetor
    int aux;        // Variável auxiliar usada para fazer a troca de elementos
    while (troca)     // Enquanto houver troca, o vetor ainda pode estar desordenado
    {
        troca = 0;   // Reinicia a variável de controle; se nenhuma troca acontecer, o vetor estará ordenado
        while (i v[i+1])  // Se o elemento atual for maior que o próximo...
            {
                aux = v[i];     // Armazena o elemento atual
                v[i] = v[i+1];     // Coloca o próximo elemento na posição atual
                v[i+1] = aux;     // Move o elemento atual para a próxima posição
                troca = 1;         // Marca que houve troca, então é necessário mais uma passada
            }
            i++;                 // Avança para o próximo par de elementos
        }
        i = 0;                   // Reinicia o índice para começar nova passada desde o início do vetor
    }
}
🔍 O que esse código faz:
· Continua repetindo as comparações e trocas enquanto alguma troca for feita.
· Usa uma variável de controle (troca) para saber se ainda há elementos fora de ordem.
Código em Python:
def bubble_sort(v):
    troca = True  # Variável de controle para saber se houve troca na passada
    while troca:  # Enquanto houver trocas, o vetor pode não estar ordenado
        troca = False  # Assume que não haverá trocas nessa passada
        for i in range(len(v) - 1):  # Percorre o vetor até o penúltimo elemento
            if v[i] > v[i + 1]:  # Compara o elemento atual com o próximo
                v[i], v[i + 1] = v[i + 1], v[i] # Troca os elementos de posição que estão fora de ordem
                troca = True  # Indica que houve troca e o processo deve continuar
valores = [54, 26, 93, 17, 77] # Vetor de exemplo
bubble_sort(valores) # Chamada da função
print(valores)  # Saída: [17, 26, 54, 77, 93]
📊 Desempenho e complexidade
· O número de comparações segue a soma:
· No pior caso (vetor invertido), isso resulta em uma complexidade quadrática:
🔺 O(n²) → Cresce muito rápido conforme o número de elementos aumenta.
· No melhor caso (vetor já ordenado) isso resulta em uma complexidade: 
🔺 O(n) → Quando o vetor já está quase ordenado e poderá ser ordenado em uma única passada. 
🔺 No entanto, não é confiável usar o melhor caso para analisar o desempenho real do algoritmo, pois ele é muito específico e raro.
✅ Observações sobre Bubble Sort:
· Simples de entender, ineficiente para grandes vetores.
· Serve apenas para fins educacionais ou vetores muito pequenos.
🃏 Insertion Sort (Ordenação por Inserção)
🔷 O que é o Insertion Sort?
· Também chamado de ordenação por inserção.
· Algoritmo de ordenação simples e fácil de entender.
· Funciona de forma semelhante a organizar cartas na mão:
👉 Você pega uma carta por vez e a insere no lugar correto, mantendo as que já estão na mão em ordem.
🔧 Como o algoritmo funciona (passo a passo)?
1. Divisão inicial:
· O vetor é dividido em duas partes:
· Sequência destino (já ordenada): começa com o primeiro elemento.
· Sequência fonte (a ordenar): o restante dos elementos.
2. Inserção:
· A partir do segundo elemento (posição 2), cada item da sequência fonte é inserido na posição correta dentro da sequência destino.
· Para isso, os elementos maiores que ele são movidos uma posição para frente, até abrir o espaço certo. 
💡 Exemplo simples explicado
Suponha o vetor: [7, 4, 5, 2]
1. Começamos com [7] como sequência ordenada.
2. Pegamos o 4 e inserimos na posição correta → [4, 7]
3. Pegamos o 5 e colocamos entre 4 e 7 → [4, 5, 7]
4. Pegamos o 2 e movemos 4, 5 e 7 uma posição à frente → [2, 4, 5, 7]
✅ Resultado final: vetor ordenado!🧑‍💻 Código em C (simplificado)
void insertion (int *v)      // Função de ordenação usando o método de inserção (Insertion Sort)
{                                    
    int i, j, aux;    // Declaração de variáveis: 'i' e 'j' para controle de índices, 'aux' para troca de valores
 
 // Loop externo percorre os elementos do vetor a partir do índice 0 até 9 (assumindo vetor de 10 elementos)
    for (i = 0; i 0) // Enquanto o elemento atual for menor que o anterior 
        {
            aux = v[j - 1];           // Armazena temporariamente o valor anterior
            v[j - 1] = v[j];          // Move o valor atual para a posição anterior
            v[j] = aux;               // Coloca o valor anterior na posição atual
            j--;                      // Decrementa o índice para comparar com elementos anteriores
        }
    }
}
🔍 O que esse código faz:
· Percorre o vetor.
· Para cada posição, compara com os anteriores e faz trocas até o valor estar na posição correta.
Código escrito em Python
def insertion_sort(v):
    # Percorre o vetor do segundo elemento até o final
    for i in range(1, len(v)):
        chave = v[i]         # Salva o valor atual (a "carta" a ser inserida)
        j = i - 1            # Começa comparando com o elemento anterior
        # Move os elementos maiores que a chave uma posição à frente
        while j >= 0 and v[j] > chave:
            v[j + 1] = v[j]  # Desloca o elemento maior para a direita
            j -= 1           # Vai para o próximo elemento à esquerda
        v[j + 1] = chave     # Insere a chave na posição correta
valores = [7, 4, 5, 2]
insertion_sort(valores)
print(valores)  # Saída: [2, 4, 5, 7]
⚖️ Vantagens do Insertion Sort
1. ✅ Eficiência para listas quase ordenadas:
· Poucas comparações e trocas são feitas se a lista já estiver quase em ordem.
2. ✅ Estável:
· Não troca elementos com valores iguais de lugar.
· Isso é útil quando há ordenações por mais de uma chave.
📊 Desempenho (comparações e trocas)
	Situação
	Comparações
	Trocas
	Melhor caso (já ordenado)
	n – 1
	2(n – 1)
	Médio caso
	~½(n² + n)
	¼(n² – n)
	Pior caso (ordem reversa)
	½(n² + n)
	½(n² + n)
· Pior caso (vetor invertido): O(n²) — igual à do Bubble Sort e Selection Sort.
· Caso médio: O(n²), é ligeiramente melhor, mas com menos trocas que bubble sort
· Melhor caso (vetor ordenado): O(n)
🟢 Resumo final
· Insertion Sort é simples, eficiente para listas pequenas ou quase ordenadas.
· Tem melhor desempenho prático que o Bubble Sort e Selection Sort em muitos casos.
· Muito bom para listas quase ordenadas.
· Estável e ideal quando a ordem de elementos iguais precisa ser mantida.
· Sua complexidade no pior caso é quadrática (O(n²)), mas para listas quase ordenadas, é bem eficiente.
🧲 Selection Sort (Ordenação por Seleção)
🔷 O que é o Selection Sort?
· Também chamado de ordenação por seleção.
· É um algoritmo de ordenação simples e intuitivo.
· O nome vem do fato de que, a cada passo, ele seleciona o menor (ou maior) valor da parte não ordenada do vetor e o coloca na posição correta.
🔧 Como o algoritmo funciona (passo a passo)?
1. Procura o menor elemento da lista (ou o maior, se for ordem decrescente).
2. Troca esse menor elemento com o primeiro da lista.
3. Depois, repete o processo com o restante da lista:
· Encontra o menor entre os elementos restantes.
· Troca com o próximo da posição ordenada.
4. Repete isso até o vetor estar todo ordenado.
🧠 Divisão do vetor
· O vetor é dividido em duas partes:
· 🔵 Parte ordenada: começa vazia e vai crescendo.
· 🔴 Parte não ordenada: inicialmente contém todos os elementos e vai diminuindo.
· A cada passo, o menor valor da parte não ordenada é movido para a parte ordenada.
💡 Exemplo simples explicado 
Dado o vetor: [5, 3, 8, 1]
1. Encontra o menor (1) → troca com o primeiro → [1, 3, 8, 5]
2. Encontra o menor do restante (3) → já está na posição correta
3. Encontra o menor entre 8 e 5 (5) → troca com 8 → [1, 3, 5, 8]
✅ Resultado final: vetor ordenado!
🧑‍💻 Código em C (explicado)
void selection_sort (int *v)         // Função que ordena um vetor de inteiros usando o método da seleção
{
    int i, j, aux, minimo, pos_minimo; // Declara variáveis
    for (i = 0; i v[j])            // Se encontrar um valor menor...
            {
                minimo = v[j];           // Atualiza o novo valor mínimo encontrado
                pos_minimo = j;          // Atualiza a posição do novo valor mínimo
            }
        }
        if (pos_minimo != i)          // Passo 2: se a posição do mínimo mudou, realiza a troca
        {
            aux = v[pos_minimo];     // Armazena o valor mínimo
            v[pos_minimo] = v[i];    // Coloca o valor da posição 'i' na posição do mínimo
            v[i] = aux;           // Coloca o valor mínimo na posição 'i' (ordenando essa posição)
        }
    }
}
🔍 O que esse código faz:
· Para cada posição i, encontra o menor valor à direita.
· Se encontrar um valor menor, troca com o valor da posição atual i.
Código em Python:
def selection_sort(v):
    # Percorre o vetor até o penúltimo elemento
    for i in range(len(v) - 1):
        min_index = i  # Assume que o menor valor está na posição atual (i)
        # Percorre o restante do vetor à direita de i
        for j in range(i + 1, len(v)):
            if v[j]n(n–1)/2
	Número de trocas
	Alto, pode trocar a cada comparação
	Baixo, só quando necessário
	Baixo: no máximo uma troca por iteração
	Estável?
	✅ Sim
	✅ Sim
	❌ Não (pode trocar elementos com mesma chave)
	Vantagens
	Simples de entender e implementar
	Ótimo para listas pequenas e quase ordenadas
	Poucas trocas; simples
	Desvantagens
	Muito ineficiente para listas grandes
	Ineficiente no pior caso
	Desempenho sempre igual, mesmo com vetor ordenado
	Uso prático
	Ensino e vetores pequenos
	Listas quase ordenadas
	Quando se deseja minimizar o número de trocas
📌 Observações Importantes
✅ Insertion Sort – Mais eficiente em muitos casos
Por que é mais eficiente?
· Se a lista estiver quase ordenada, o Insertion Sort é muito rápido, com complexidade O(n) no melhor caso.
· Ele não faz mais trocas que o necessário — troca apenas os elementos realmente fora do lugar.
· Em listas pequenas (até algumas centenas de elementos), seu desempenho é muito bom.
· Estável, ou seja, mantém a ordem de elementos com mesma chave.
Quando usar:
· Vetores pequenos.
· Vetores quase ordenados.
· Situações onde a estabilidade importa (ex: ordenação por múltiplas chaves).
⚖️ Selection Sort – Poucas trocas, mas lento
Pontos fortes:
· Gasta menos trocas que os outros.
· Desempenho previsível: sempre faz o mesmo número de comparações.
Pontos fracos:
· Sempre realiza O(n²) comparações, mesmo com o vetor ordenado.
· Não é estável (pode mudar a ordem de elementos iguais).
· Geralmente mais lento que o Insertion Sort, exceto em casos muito específicos onde minimização de trocas é mais importante que o tempo.
❌ 3. Bubble Sort – O menos eficiente dos três
Pontos fracos:
· É o mais lento na maioria dos casos.
· Faz muitas trocas desnecessárias.
· Mesmo com otimizações (como parada antecipada), raramente supera os outros dois.
Usado principalmente para fins didáticos (por ser simples de entender), mas não recomendado na prática.
✅ Resumo: Qual o mais eficiente?
	Critério
	Melhor escolha
	Desempenho geral
	✅ Insertion Sort
	Poucas trocas
	✅ Selection Sort
	Simplicidade para aprender
	✅ Bubble Sort
	Listas quase ordenadas
	✅ Insertion Sort
	Listas grandes
	❌ Nenhum dos três (usar QuickSort, MergeSort, etc.)
🔁 Como identificar cada algoritmo de ordenação:
	Algoritmo
	Compara quem?
	Troca quando?
	Anda para trás?
	Troca múltiplas vezes?
	Bubble Sort
	v[i] com v[i+1]
	Se v[i] > v[i+1]
	❌ Não
	✅ Sim
	Insertion Sort
	v[j] com aux
	Para inserir na posição correta. 
	✅ Sim (Procure por laço interno que anda para trás, como: “j--")
	✅ Sim (desloca)
	Selection Sort
	Menor em =v[i+1] a v[n]
	Depois de encontrar o menor valor. 
→ Veja se há um laço que procura o menor valor e depois uma troca única por iteração. 
	❌ Não
	❌ Uma troca por passo
Módulo 2. Descrever o funcionamento do algoritmo de ordenação por intercalação (merge sort)
🧩 O que é o Merge Sort?
· Merge Sort, ou Ordenação por Intercalação, é um algoritmo de ordenação que:
· Usa a técnica recursiva chamada "dividir para conquistar" (divide and conquer);
· É eficiente para grandes volumes de dados;
· Divide o problema em pedaços menores, resolve cada pedaço e depois junta os resultados.
🔁 Etapas do Merge Sort
1. Dividir
· O vetor é dividido ao meio recursivamente até restarem subvetores com 1 elemento.
· Exemplo com o vetor [7, 2, 9, 4, 3, 8, 6, 1]:
· Divide em: [7, 2, 9, 4] e [3, 8, 6, 1]
· Depois: [7, 2], [9, 4], [3, 8], [6, 1]
· Finalmente: [7], [2], [9], [4], [3], [8], [6], [1]
2. Conquistar
· Cada subvetor com 1 elemento já está "ordenado".
· Começa-se a juntar e ordenar pares:
· [7] e [2] → [2, 7]
· [9] e [4] → [4, 9]
· [3] e [8] → [3, 8]
· [6] e [1] → [1, 6]
3. Combinar (intercalar)
· Intercala os pares já ordenados:
· [2, 7] e [4, 9] → [2, 4, 7, 9]
· [3, 8] e [1, 6] → [1, 3, 6, 8]
· Passo final: juntar as duas metades:
· [2, 4, 7, 9] e [1, 3, 6, 8] → vetor final ordenado: [1, 2, 3, 4, 6, 7, 8, 9]
🔁 Resumo prático das etapas do Merge Sort
· Divida o vetor em duas metades até que restem elementos individuais.
· Intercale os elementos em ordem crescente para formar subvetores ordenados.
· Repita a intercalação até obter o vetor completamente ordenado.
✅ Vantagens do Merge Sort 
· Menos acessos à memória (especialmente em listas encadeadas).
· Facilmente paralelizável: diferentes partes do vetor podem ser ordenadas ao mesmo tempo se houver múltiplos processadores.
🌳 Representação em Árvore
· Cada nó da árvore representa uma chamada recursiva. 
· Raiz: vetor completo.
· Folhas: subvetores de 1 elemento (caso base).
· Depois a árvore é "subida" intercalando os elementos.
💻 Implementação em C (Explicada)
#include 
#include 
// Protótipos das funções auxiliares
void mergesort(int *v, int n);                    // Função principal que inicia a ordenação
void sort(int *v, int *c, int i, int f);         // Função recursiva que divide o vetor
void merge(int *v, int *c, int i, int m, int f);  // Função que intercala duas partes ordenadas
// Função principal do programa
int main (void) {
  int i;
  int v[8] = { -1, 7, -3, 11, 4, -2, 4, 8 };  // Vetor a ser ordenado
  mergesort(v, 8);                           // Chamada da função de ordenação
  for (i = 0; i = f)                                // Caso base: vetor com 1 elemento já está ordenado
    return;
  int m = (i + f) / 2;                       // Calcula o meio do vetor
  sort(v, c, i, m);                          // Ordena recursivamente a primeira metade
  sort(v, c, m + 1, f);                      // Ordena recursivamente a segunda metade
  // Otimização: se o final da primeira parte já for menor que o início da segunda, já está ordenado
  if (v[m]do Merge Sort
· O algoritmo Merge Sort realiza a ordenação por meio de uma função recursiva chamada merge.
✅ 1. Estrutura do algoritmo (pseudocódigo simplificado)
· O código mostra que o vetor é dividido recursivamente em duas metades até que não possa mais ser particionado.
· Após a divisão, é chamada a função “intercala”, que junta as duas partes ordenadas.
função merge (x, inicio, fim)
    início
        var
            meio: numérico;
        Se (inicio baixo, troque os elementos nas posições a[baixo] e a[alto].
Repetição
· Continue repetindo os passos 1, 2 e 3 enquanto alto > baixo.
🔚 Finalização do particionamento
· Quando alto6
👉 Troca 53 com 6
3. baixo encontra 75
alto encontra 11
👉 Troca 75 com 11
4. baixo encontra 56
alto encontra 21
👉 Troca 56 com 21
5. baixo encontra 56
alto encontra 21
👉 Parada (porque alto limInf não seja mais satisfeita.
· Isso significa que o subvetor tem zero ou um elemento, ou seja, já está ordenado.
🧠 Resumo geral da execução
· O Quick Sort funciona separando o vetor em partes com base em um pivô.
· Usa trocas sucessivas até que o pivô esteja no lugar certo.
· O processo é repetido nos subvetores esquerdo e direito.
· O algoritmo é eficiente por fazer reorganização durante a recursão, sem a necessidade de vetores auxiliares.
🧮 Implementação: Veja, a seguir, o algoritmo que implementa o Quick Sort, com o desenvolvimento do procedimento partição:
#include // Inclui a biblioteca padrão de entrada e saída para funções como printf e scanf
#include // Inclui a biblioteca padrão para funções como malloc e free
// Função para ler os elementos de um vetor
void lerVet( int *p, int t ){
    int i; // Declara uma variável de contador para o loop
    // Loop para percorrer o vetor
    for ( i=0; i pivo )
            dir--;
        // Se os ponteiros esquerdo e direito não se cruzaram, troca os elementos
        if ( esq = sup )
        return;
    posPivo= divide(p,inf,sup); // Chama a função divide para particionar o vetor e obter a posição do pivô
    quickSort(p,inf,posPivo-1); // Chama recursivamente o quickSort para a sub-lista à esquerda do pivô
    quickSort(p,posPivo+1,sup); // Chama recursivamente o quickSort para a sub-lista à direita do pivô
}
// Função principal do programa
void main(){
    int *p, tam; // Declara um ponteiro para o vetor e uma variável para o tamanho
    printf("Quantidade de elementos do vetor?"); // Solicita a quantidade de elementos do vetor
    scanf("%d",&tam); // Lê o tamanho digitado pelo usuário
    p = (int*) malloc(tam * sizeof(int)); // Aloca dinamicamente memória para o vetor com base no tamanho
    printf("\nDigite o conteudo do vetor:\n"); // Informa ao usuário para digitar o conteúdo do vetor
    lerVet(p, tam); // Chama a função para ler os elementos do vetor
    printf("\nConteudo digitado para o vetor:\n"); // Informa que vai mostrar o conteúdo digitado
    mostrarVet(p, tam); // Chama a função para mostrar o conteúdo do vetor
    printf("\nOrdenando o vetor...\n"); // Informa que o vetor será ordenado
    quickSort(p, 0, tam-1); // Chama a função quickSort para ordenar o vetor
    printf("\nConteudo do vetor ja ordenado:\n"); // Informa que vai mostrar o vetor ordenado
    mostrarVet(p, tam); // Chama a função para mostrar o vetor ordenado
    free(p); // Libera a memória alocada para o vetor	
}
🔍 O que esse código faz:
1. Estrutura geral do programa
O programa realiza três etapas principais:
· Leitura dos elementos de um vetor.
· Ordenação com o algoritmo Quick Sort.
· Exibição do vetor ordenado.
 2. Funções principais
✅ lerVet(int *p, int t)
· Objetivo: Ler os valores digitados pelo usuário e armazená-los no vetor.
· Funcionamento:
· Percorre o vetor com um loop de 0 até t - 1.
· Pede ao usuário um valor por posição.
✅ mostrarVet(int *p, int t)
· Objetivo: Mostrar o conteúdo atual do vetor.
· Funcionamento: Imprime cada valor junto com sua posição.
✅ trocar(int *pv, int x, int y)
· Objetivo: Trocar os valores de duas posições do vetor.
· Funcionamento: Usa uma variável auxiliar aux para trocar pv[x] e pv[y].
3. com a função divide
· Objetivo: Colocar o pivô na posição correta e reorganizar os elementos.
· Funcionamento:
1. Define o pivô como o primeiro elemento (v[inf]).
2. Dois ponteiros (esq e dir) percorrem o vetor:
· esq avança até encontrar um valor maior que o pivô.
· dir recua até encontrar um valor menor ou igual ao pivô.
3. Se esq = sup, a função retorna.
· Caso recursivo:
· Chama divide para posicionar o pivô.
· Ordena o subvetor à esquerda do pivô.
· Ordena o subvetor à direita do pivô.
5. Função main (principal)
· Objetivo: Controlar a execução do programa.
· Passos:
1. Pergunta ao usuário a quantidade de elementos.
2. Aloca dinamicamente a memória para o vetor.
3. Lê os valores do vetor.
4. Mostra o vetor original.
5. Chama quickSort para ordenar o vetor.
6. Mostra o vetor ordenado.
7. Libera a memória alocada.
🧮 Exemplo simplificado do particionamento
Suponha que o vetor seja:
[23, 45, 11, 67, 8]
· Pivô = 23
· esq encontra 45 (>23)
· dir encontra 8 (23), dir encontra 11 (na ideia de particionar o vetor.
· O vetor é dividido em duas partes usando um elemento chamado pivô:
· À esquerda do pivô: ficam os elementos menores ou iguais ao pivô.
· À direita do pivô: ficam os elementos maiores que o pivô.
🔁 Procedimento de partição
· É o passo central do Quick Sort.
· Ocorre da seguinte forma:
· Dois índices percorrem o vetor:
· i começa do início e avança enquanto os elementos forem menores ou iguais ao pivô.
· j começa do final e recua enquanto os elementos forem maiores que o pivô.
· Enquanto i = 0; j = j  - gap)
                             item [ j + gap ] = item [ j ] ;
                       item [ j + gap] = x;
            }
      }
}
✅ Verificações importantes: Observe que o laço for mais interno tem duas condições de teste.
· x = 0 → evita acessar fora dos limites do vetor.
🧠 Sentinelas (opcional)
· São elementos artificiais no vetor (muito pequenos ou grandes).
· As sentinelas guardam valores especiais de terminação, ou seja, são usados para evitar testes de limite (j >= 0).
· Porém, exigem conhecimento específico dos dados → limitam a generalidade do algoritmo.
📈 Complexidade e desempenho
· Desempenho médio: proporcional a 
· Melhor que algoritmos n² como Bubble Sort e Insertion Sort.
· Gráfico (como mostrado na imagem):
· Linha n² cresce muito mais rápido que 
· Shell sort é muito mais eficiente para grandes vetores.
✅ CONCLUSÃO
· Shell Sort é simples, eficiente e ocupa pouco espaço na memória.
· Muito melhor que Bubble ou Insertion Sort para listas grandes. 
· O Shell Sort é bom para ordenar um número moderado de elementos, pois requer uma quantidade de código pequena.
· Não é o mais rápido entre os algoritmos avançados, mas é uma ótima escolha intermediária.
✅ Comparação entre Algoritmos de Ordenação
📌 1. Bubble Sort
· Muito ineficiente para grandes volumes de dados.
· Tempo de execução:
· Melhor caso: O(n) → elementos já estão ordenados.
· Médio/Pior caso: O(n²) → muitos elementos fora de ordem.
· Resumo: simples, mas lento e pouco eficiente.
📌 2. Selection Sort
· Também ineficiente para grandes volumes de dados.
· Tempo de execução: sempre O(n²), independe da ordem inicial.
· Resumo: também simples, mas não melhora mesmo se os dados estiverem ordenados.
📌 3. Insertion Sort
· Melhor para listas pequenas ou quase ordenadas.
· Tempo de execução:
· Melhor caso: O(n) → elementos já ordenados.
· Médio/Pior caso: O(n²)
· Resumo: melhor que bubble e selection, mas ainda ineficiente para grandes dados.
📌 4. Merge Sort
· Muito eficiente, mesmo com dados desordenados.
· Tempo de execução: sempre O(n log n)
· Desvantagem: usa mais memória, pois cria cópias do vetor em cada passo.
· Alternativa: usar apenas um vetor auxiliar para reduzir o uso de memória.
· Comparações com Quick Sort:
· No pior caso, o merge sort faz ~39% menos comparações.
· No melhor caso, faz metade das iterações do pior caso.
· Resumo: eficiente, estável e consistente, mas usa mais espaço.
📌 5. Quick Sort
· Muito rápido se o particionamento for balanceado.
· Tempo de execução:
· Melhor/Médio caso: O(n log n) (quando bem balanceado).
· Pior caso: O(n²) (quando mal balanceado, por exemplo, pivôs mal escolhidos).
· Resumo: rápido e eficiente, mas pode ser ruim em alguns casos.
📌 6. Shell Sort
· Boa opção para vetores de tamanho moderado.
·Vantagens:
· Simples de implementar.
· Usa pouco código e pouca memória (O(1) de espaço).
· Desvantagens:
· Desempenho depende da ordem inicial dos dados.
· Não é estável (pode mudar a ordem relativa de elementos iguais).
· Tempo de execução:
· Varia de até , dependendo da sequência de gaps.
· Resumo: intermediário entre os simples e os rápidos.
📊 Tabela Comparativa Resumida
	Algoritmo
	Comparações (melhor, médio ou pior)
	Movimentações (melhor, médio ou pior)
	Espaço
	Estável?
	Bubble
	O(n²)
	O(n²)
	O(1)
	Sim
	Selection
	O(n²)
	O(n)
	O(1)
	Não*
	Insertion
	Melhor: O(n) → Médio/Pior: O(n²)
	Melhor: O(n) → Médio/Pior: O(n²)
	O(1)
	Sim
	Merge
	O(n log n)
	-
	O(n)
	Sim
	Quick
	Melhor/Médio: O(n log n) → Pior: O(n²)
	-
	O(n)
	Não*
	Shell
	O(n1.25) ou O(n ln² n)
	-
	O(1)
	Não
✅ Conclusão
· Para dados pequenos ou quase ordenados: Insertion Sort pode ser suficiente.
· Para grandes volumes e performance consistente: Merge Sort é mais seguro.
· Para alto desempenho na prática: Quick Sort é muito rápido, mas cuidado com piores casos.
· Shell Sort: equilibrado e útil para tamanhos moderados, com código simples.
· Busca sequencial de um elemento em um vetor: Complexidade O(n)
· A busca sequencial percorre o vetor do início ao fim, podendo precisar olhar todos os elementos no pior caso.
· Busca via pesquisa binária de um elemento em um vetor ordenado de tamanho n: Complexidade O(log n)
· A pesquisa binária divide o vetor ao meio a cada passo, logo a complexidade é O(log n).
· Somar todos os números de um vetor: Complexidade O(n)
· É necessário percorrer todo o vetor somando cada elemento.
· Merge que 2 listas: Complexidade O(n)
· O merge (intercalação) de duas listas ordenadas com n elementos no total é feito em tempo linear - O(n).
· Inclusão de um elemento em um vetor ordenado de tamanho n mantendo-se a ordenação: Complexidade O(n)
· Para manter a ordenação, é preciso:
· Encontrar a posição correta (pode ser O(log n) com busca binária)
· Mover os elementos seguintes para abrir espaço (O(n) no pior caso)
· Complexidade no pior caso: O(n)
TEMA 5 - ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL
Módulo 1. Reconhecer os tipos de percursos utilizados em árvores binárias
🌳 Árvore Binária - Conceitos Principais
· Definição:
· Uma árvore binária T pode ser:
· Um conjunto vazio, ou
· Um conjunto com:
· Um nó raiz (n);
· Uma subárvore esquerda (Te);
· Uma subárvore direita (Td).
· A definição é recursiva: cada subárvore (Te e Td) também é uma árvore binária.
· Representação Gráfica:
· Cada nó pode ter até dois filhos: um à esquerda e outro à direita.
· Exemplo (Figura 1):
· Raiz: A
· Subárvore esquerda (Te): B → D, E → F
· Subárvore direita (Td): C → G
· A posição dos filhos é importante: o nó “G” é filho direito de “C” (não há filho esquerdo).
💾 Representação em Memória
· Forma mais comum: A forma mais comum de representar uma árvore em memória é utilizando alocação dinâmica, com ponteiros para os filhos.
· A árvore é representada a partir de um ponteiro para o nó raiz.
· Cada nó guarda:
· Uma chave (valor).
· Dois ponteiros:
· Um para a subárvore esquerda.
· Um para a subárvore direita.
· Um nó de árvore é geralmente uma struct (ou record) que agrupa dados de diferentes tipos (como o valor do nó e os ponteiros para seus "filhos"), permitindo que você organize e acesse essas informações de forma eficiente para construir a estrutura da árvore. 
· O struct (agregador heterogêneo) é capaz de armazenar objetos de dados de tipos diferentes acessando-os através do mesmo identificador e distinguindo-os através de um seletor.
· Estrutura do nó (em pseudocódigo):
registro no {
    Inteiro chave;
    registro no *esq;
    registro no *dir;
}
· A árvore é representada por uma referência para sua raiz, ponteiro para raiz, que, recursivamente, aponta para as raízes das subárvores esquerda e direita.
· Declaração de um ponteiro para a raiz da árvore:
registro no *raiz;
· Árvore vazia: É representada quando o ponteiro raiz aponta para o endereço 0, associado à constante NULA. Assim, para inicializar uma árvore vazia, basta inicializar o ponteiro raiz como nulo.
raiz = NULA;  // ponteiro para endereço 0
🧠 Exemplo Explicado (Figuras 2 e 3)
· Figura 2 (Árvore com valores inteiros):
· Raiz: 10
· Subárvore esquerda: 8 → 2 e 6
· Subárvore direita: 4
· Figura 3. Organização em Memória (endereços fictícios):
· O nó com chave 10 está no endereço $100.
· Ele aponta para:
· Subárvore esquerda em $150 (nó com chave 8)
· Subárvore direita em $70 (nó com chave 4)
· O nó 8 (em $150) aponta para:
· Esquerda: $20 (chave 2)
· Direita: $200 (chave 6)
· Nós 2, 4 e 6 não possuem filhos → apontam para $0.
✏️ Acesso com Ponteiros:
· Se tivermos registro no *v = $20, então:
· v->chave acessa o valor armazenado no nó no endereço $20.
· Exemplo: se $20 contém chave 2, então v->chave = 2.
🧭 Observações Importantes:
· A estrutura só tem ponteiros do pai para os filhos.
· Ex.: Do nó 10 você acessa 8 e 4.
· Mas do nó 4 não é possível acessar o pai (10).
🌳 O que é um percurso em árvore?
· Um percurso é uma visita sistemática aos nós da árvore.
· Visitar um nó: significa executar uma operação útil, por exemplo, imprimir o valor, não apenas acessá-lo.
🔁 Percursos são recursivos: Como a estrutura de árvore é recursiva, os percursos também são definidos de forma recursiva.
🛤️ Tipos de percurso em árvore binária
São três:
🟢 1. Pré-ordem (Pré = antes)
Ordem das ações:
1. Visita o nó raiz.
2. Vai para a subárvore esquerda.
3. Depois, para a subárvore direita.
📌 Lê primeiro a raiz, depois tudo à esquerda, depois à direita. 
· Cada nó pode ser acessado 3 vezes durante o percurso, mas a visita real acontece na primeira vez (acesso 1).
✅ Exemplo com essa árvore:
 A
 / \
 B C
· Percurso em pré-ordem: A, B, C
✅ Exemplo 2.
 100
 / \
 50 200
 / \
 30 80
· Percurso em pré-ordem: 100, 50, 30, 80, 200
🔵 2. Em ordem (ou "ordem simétrica")
Ordem das ações:
1. Vai para a subárvore esquerda.
2. Visita o nó raiz.
3. Vai para a subárvore direita.
📌 Lê os elementos da árvore em ordem crescente, se a árvore for de números.
✅ Exemplo 1. 
 A
 / \
 B C
Percurso em ordem: B, A, C
✅ Exemplo 2.
 100
 / \
 50 200
 / \
 30 80
Percurso em ordem: 30, 50, 80, 100, 200
🔴 3. Pós-ordem (Pós = depois)
Ordem das ações:
1. Vai para a subárvore esquerda.
2. Vai para a subárvore direita.
3. Visita o nó raiz.
📌 Lê os filhos antes do pai.
✅ Exemplo com a mesma árvore:
 A
 / \
 B C
Percurso em pós-ordem: B, C, A
✅ Exemplo 2.
 100
 / \
 50 200
 / \
 30 80
Percurso em ordem: 30, 80, 50, 200, 100
💡 Dica para lembrar:
· Pré-ordem: Pai vem primeiro.
· Em ordem: Pai vem entre os filhos.
· Pós-ordem: Pai vem por último.
🔁 Algoritmos Recursivos para Percursos em Árvores Binárias
1. Pré-Ordem (Visita (nó raiz) → Esquerda → Direita)
Exemplo de código:
função pre-ordem (registro no *p)
início
  visita(p);
  se (p->esq != NULO)
      pre-ordem(p->esq);
  se (p->dir != NULO)
      pre-ordem(p->dir);
fim
· Primeiro: visita o nó raiz.
· Depois: chama a função recursiva para o filho à esquerda.
· Por fim: chama a função recursiva para o filho à direita.
· 📌 Complexidade: Cada nó passa por 3 momentos → 3n operações elementares → O(n)
2. Ordem Simétrica (Esquerda → Visita (nó raiz) → Direita) 
Exemplo de código:
função simetrica (registro no *p)
início
  se (p->esq != NULO)
      simetrica(p->esq);
  visita(p);
  se (p->dir != NULO)
      simetrica(p->dir);
fim
Diferença da pré-ordem: a visita acontece depois de percorrer a esquerda.
· Primeiro: percorre recursivamente a subárvore esquerda.
· Depois: visita o nó raiz.
· Por fim: percorre recursivamente a subárvore direita.
📌 Complexidade: Semelhante à pré-ordem → O(n)
3. Pós-Ordem (Esquerda → Direita → Visita (nó raiz))
Exemplo de código:
função pos-ordem (registro no *p)
início
  se (p->esq != NULO)
      pos-ordem(p->esq);
  se (p->dir != NULO)
      pos-ordem(p->dir);
  visita(p);
fim
· Primeiro: percorrea subárvore esquerda.
· Depois: percorre a subárvore direita.
· Por fim: visita o nó raiz.
📌 Complexidade: Semelhante às anteriores → O(n)
🔁 Algoritmos Não Recursivos para Percursos
· Em árvores binárias, a estrutura é unidirecional, do pai para o filho, porque essa estrutura é fundamental para a definição e funcionamento da árvore. 
· A referência de pai para filho permite definir a hierarquia, a organização e o percurso através da árvore. 
· A falta de referência de filho para pai simplifica a implementação, o espaço de memória e, em muitos casos, a lógica dos algoritmos.
· Logo, como não há referência do filho para o pai, usamos uma pilha para simular a recursão.
· Cada nó é inserido na pilha com um número de "momento" (1, 2 ou 3) para identificar o estágio da visita:
· 1: Chegando no nó pela primeira vez.
· 2: Terminou o lado esquerdo.
· 3: Terminou o lado direito.
🔁 Pré-Ordem Não Recursivo
Exemplo de código:
função pre-ordem-não-recursiva (registro no *p)
inicio
    registro no *aux;
    inteiro momento;
    push (p, 1); // insere a raiz de T, no momento 1
    enquanto (pilha não vazia)
    inicio
        pop (aux, momento);
        if (momento == 1)
        inicio
            visitar (aux); // caso se deseje a pré-ordem
            push (aux, 2); // push aux na pilha, momento 2
            se (aux->esq != NULO)
                push (aux->esq, 1);
        fim
        if (momento == 2)
        inicio
            push (aux, 3); // push aux na pilha, momento 3
            se (aux->dir != NULO)
                push (aux->dir, 1);
        fim
        // na pré-ordem, não há ações no momento 3
    fim
fim
Exemplo simples:
Para a árvore:
 10
 / \
 8 7
 \
 12
Impressão (pré-ordem): 10, 8, 12, 7
Explicação:
· Começa visitando o nó raiz (10).
· Vai para a esquerda e visita 8.
· Como 8 tem filho esquerdo, visita 12.
· Volta e vai para a direita de 10 e visita 7.
Complexidade:
Cada nó é empilhado 3 vezes → 3n operações → O(n).
🔁 Ordem Simétrica Não Recursivo
Exemplo de código:
função ordem-simetrica-não-recursiva (registro no *p)
inicio
    registro no *aux;
    inteiro momento;
    push (p, 1); // insere a raiz de T, no momento 1
    enquanto (pilha não vazia)
    inicio
        pop (aux, momento);
        if (momento == 1)
        inicio
            push (aux, 2); // push aux na pilha, momento 2
            se (aux->esq != NULO)
                push (aux->esq, 1);
        fim
        if (momento == 2)
        inicio
            visitar (aux);
            se (aux->dir != NULO)
                push (aux->dir, 1);
        fim
        // na ordem simétrica, não há ações no momento 3
    fim
fim
Diferença:
· Só muda o momento da visita: agora é no momento 2.
🔁 Pós-Ordem Não Recursivo
Exemplo de código:
função pos-ordem-não-recursiva (registro no *p)
inicio
    registro no *aux;
    inteiro momento;
    push (p, 1); // insere a raiz de T, no momento 1
    enquanto (pilha não vazia)
    inicio
        pop (aux, momento);
        if (momento == 1)
        inicio
            push (aux, 2); // push aux na pilha, momento 2
            se (aux->esq != NULO)
                push (aux->esq, 1);
        fim
        if (momento == 2)
        inicio
            push (aux, 3);
            se (aux->dir != NULO)
                push (aux->dir, 1);
        fim
        if (momento == 3)
            visitar (aux);
    fim
fim
Diferença:
· Visita só acontece no momento 3, ou seja, depois de percorrer esquerda e direita.
✅ Resumo Final
	Tipo de Percurso
	Ordem da Visita
	Momento da Visita
	Complexidade
	Pré-ordem
	Nó → Esquerda → Direita
	Momento 1
	O(n)
	Simétrica
	Esquerda → Nó → Direita
	Momento 2
	O(n)
	Pós-ordem
	Esquerda → Direita → Nó
	Momento 3
	O(n)
✅ Conclusões Gerais
· Os algoritmos recursivos seguem diretamente a definição dos percursos.
· Os algoritmos não recursivos simulam o comportamento da pilha de chamadas usando uma pilha manual com controle de momentos.
· Todos os algoritmos têm complexidade O(n), onde n é o número de nós da árvore.
· O uso da pilha é essencial para reconstruir a relação de "volta" à raiz nos algoritmos não recursivos.
Módulo 2. Definir árvores binárias de busca
1. Problemas fundamentais em estruturas de dados:
· Os principais problemas são buscar, inserir e remover elementos.
2. Exemplo lúdico com bolinhas:
· Imagine um saco opaco com bolinhas de cores diferentes.
· A tarefa é encontrar a bolinha vermelha, sem olhar dentro do saco.
3. Como seria a busca:
· Você tira uma bolinha de cada vez, sem saber a cor.
· Pode ter sorte e tirar a vermelha de primeira.
· Ou pode ter azar e a vermelha ser a última a ser tirada.
4. O que isso nos ensina:
· Em situações sem nenhuma organização, a busca pode ser ineficiente.
· No pior caso, é necessário verificar todas as bolinhas → isso leva a uma complexidade de O(n).
5. Conceito de complexidade:
· A complexidade de tempo mede o esforço necessário para resolver um problema.
· Geralmente, analisa-se o pior caso possível (visão pessimista).
6. Meta: melhorar a busca:
· Para ser mais eficiente, o ideal é alcançar uma complexidade de O(log n).
· Para isso, é necessário organizar os dados de forma inteligente.
7. Solução sugerida:
· As árvores (estruturas de dados como a árvore binária de busca) são boas ferramentas para alcançar essa melhoria.
📌 Árvores Binárias de Busca
1. O que é uma árvore binária de busca?
· É uma estrutura de dados em forma de árvore usada para buscar, inserir e remover informações com eficiência.
2. Conjunto de chaves ordenadas:
· As informações (chaves) que vão ser manipuladas estão em ordem crescente: s1 chave == chave)    // Caso 2: Achou a chave
     início
        encontrada = VERDADEIRO;de a: 10
Valor de b: 5
🔎 Explicação:
· a e b são passados por valor (cópia).
· A troca acontece apenas dentro da função.
· Os valores originais de a e b não são alterados fora da função.
📌 Exemplo 2: Exemplo de sub-rotina, com uma função com um retorno e um procedimento.  
Objetivo: Somar os valores de 1 a 10, apresentando ao final o valor da soma
def soma_valores():
    soma = 0
    for i in range(1, 11):  # de 1 até 10
        soma += i
    return soma
# Programa principal
resultado = soma_valores()
print("A soma dos valores é", resultado)
# Saída no terminal: A soma dos valores é 55
🔎 Explicação:
· soma_valores() retorna o resultado.
· O valor é armazenado em resultado e exibido.
📌 Exemplo 3: Exemplo de sub-rotina, com uma função sem retorno. 
Objetivo: Somar os valores de 1 a 10, sem apresentar um retorno (procedimento)
def soma_valores():
    soma = 0
    for i in range(1, 11):  # de 1 até 10
        soma += i
    print("A soma dos valores é", soma)
# Programa principal
soma_valores()
# Saída no terminal: A soma dos valores é 55
🔎 Explicação:
· A função não retorna nenhum valor.
· Apenas executa e exibe a soma dentro dela mesma.
Módulo 2. Definir as estruturas de dados manipuladas pelos algoritmos
Arranjo unidimensional homogêneo
🔹 1. Limitação dos Tipos Primitivos
· Tipos primitivos (real, inteiro, caractere, lógico) não são suficientes para representar todos os tipos de informação, particularmente quando temos mais de uma informação relacionada.
· Exemplos: lista de nomes de alunos, endereços, notas etc.
🔹 2. Estruturas de Dados Mais Complexas
· Os tipos primitivos serão utilizados para construir outras estruturas de dados mais complexas.
· Para agrupar múltiplos dados do mesmo tipo, usamos:
· Vetores (ou arrays)
· Matrizes
· Para dados de tipos diferentes, usa-se registros (ou structs em outras linguagens).
🔹 3. Vetores (Arranjos Unidimensionais Homogêneos)
· Também conhecidos como: variáveis indexadas, variáveis compostas, variáveis subscritas, arranjos, arrays, tabelas, etc.
· Definição de Vetores (arranjo unidimensional): São coleções de dados do mesmo tipo, com um único nome e acessadas por índice. 
· Um vetor é uma variável homogênea, pois armazenam dados do mesmo tipo.
🧠 Exemplo: Um vetor de tamanho 10 armazena 10 elementos do mesmo tipo, um após o outro na memória (vetores são armazenados em blocos contíguos de memória).
💡 Sintaxe geral (pseudocódigo) de um vetor:
tipo nome_do_vetor[tamanho];
✅ Equivalente em Python:
notas = [0] * 10  # cria uma lista com 10 elementos iniciados com 0
print(notas)
# Saída no terminal: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
🔹 4. Vantagem dos vetores: Repetição e Organização
· Permite usar laços (como for) para ler, processar e imprimir os valores.
· Facilita a programação, evitando a declaração de muitas variáveis.
🔹 Exemplo 1: Sem vetor (forma ineficiente)
⚠️ Pseudocódigo (resumido):
ler n1, n2, ..., n10
media ← (n1 + n2 + ... + n10) / 10
❌ Problema:
· Muitas variáveis separadas.
· Código repetitivo e difícil de manter.
🔹 Exemplo 2: Com vetor (forma eficiente)
✅ Pseudocódigo com vetor:
notas[10], soma = 0
para i = 0 até 9 faça
    leia(notas[i])
    soma = soma + notas[i]
media = soma / 10
✅ Código equivalente em Python:
notas = [0] * 10
soma = 0
for i in range(10):
    notas[i] = float(input(f"Digite a {i+1}ª nota: "))
    soma += notas[i]
media = soma / 10
print("A média da turma é:", media)
# Números inseridos: notas[i]= [7, 8, 9, 5, 4, 3, 10, 9, 10, 8]
# Saída no terminal: A média da turma é: 7.3
🔹 7. Conclusão sobre vetores
· Vetores simplificam o código, especialmente quando lidamos com muitos dados.
· São ideais quando temos vários valores do mesmo tipo.
· Facilitam operações em massa como soma, média, ordenação, etc.
Registros (Estruturas Heterogêneas)
🔹 O que são Registros?
· São estruturas de dados heterogêneas: armazenam vários dados de tipos diferentes dentro de uma mesma variável.
· Também chamados de estruturas ou dados compostos heterogêneos, pois cada campo pode ter um tipo diferente; 
· Cada dado dentro do registro é chamado de campo. 
· Os registros são alocados em posições adjacentes de memória. Isso significa que eles são armazenados em locais de memória que estão próximos uns dos outros, não em posições aleatórias ou espalhadas.
🔹 Por que usar registros?
· Evita o uso de múltiplos vetores separados para representar uma entidade (ex: nome + notas).
· Torna o código mais organizado, legível e fácil de manipular.
🔹 Diferença entre Vetores e Registros
· Vetores: armazenam valores do mesmo tipo (ex: só números).
· Registros: armazenam vários campos de tipos diferentes (ex: nome (texto), nota (real), idade (inteiro)).
📌 Exemplo prático: Armazenar os dados de um aluno (nome + 4 notas), em vez de dois vetores separados (um de nomes e um de notas). 
· A utilização dos registros vem facilitar essa representação, conforme a Figura:
· Usamos um único registro Aluno com campos: nome, nota1, nota2, nota3, nota4
🔹 Estrutura de um Registro
· Um registro é um conjunto de campos, cada um com um nome e tipo próprio.
· Um registro pode ter quantos campos o analista quiser, mas recomenda-se um máximo de 10 para facilitar.
· Pode conter inclusive outros registros como campos (estrutura aninhada).
· Exemplo de campos:
· nome (texto)
· idade (inteiro)
· altura (real)
· sexo (caractere)
🔹 Como declarar um registro? (pseudocódigo)
tipo r = registro
  {Descrição dos campos e seus tipos} 
 fim registro;
r = REG;
Tomando como exemplo a proposta de se criar um registro denominado Aluno, será declarado da seguinte forma:
tipo r = registro
  texto: NOME;
  real: NOTA1;
   real: NOTA2;
  real: NOTA3;
  real: NOTA4;
 fim registro;
r = ALUNO;
🔹 Registros com outros registros embutidos ou Registros Aninhados (Registros dentro de Registros)
· Um campo de um registro pode ser outro registro.
📌 Exemplo: Registro FUNC (funcionário) tem um campo ENDERECO, que é outro registro com os campos RUA, NRO e CEP.
Etapas de definição (pseudocódigo):
// Registro aninhado
Tipo ender = registro
  texto: RUA;
  inteiro: NRO;
  inteiro: CEP;
fim registro;
// Registro
Tipo r = registro
  texto: NOME;
   ender: ENDERECO;
  texto: CIDADE;
  texto: ESTADO;
  real: SALARIO;
 fim registro;
r = FUNC;
Perceba que o tipo ender que está embutido no registro r.
🔹 Atribuição de valores a campos de um registro
· Usa-se o operador ponto (.) para acessar campos de um registro.
✅ Exemplo em pseudocódigo:
FUNC.NOME ← “Joana Curadora”;
FUNC.ENDERECO.RUA ← “Avenida das Américas”;
FUNC.ENDERECO.NRO ← 4200;
FUNC.ENDERECO.CEP ← 22640102;
FUNC.CIDADE ← “Rio de Janeiro”;
FUNC.ESTADO ← “RJ”;
FUNC.SALARIO ← 8000.98;
🔹 Observações Finais
· Registros são ideais para representar objetos do mundo real, como pessoas, produtos, carros, etc.
· Melhoram a organização e clareza do código.
· Permitem a manipulação unificada de dados diferentes, mas relacionados.
Ponteiros
🔹 O que é um Ponteiro?
· Um ponteiro é uma variável especial que armazena o endereço de memória de uma variável.
· Ele aponta para o local onde um valor está armazenado, ao invés de conter diretamente o valor.
🔹 Conceito de Endereço de Memória
· Toda variável ocupa um espaço na memória.
· O ponteiro armazena o endereço (posição) desse espaço.
· Exemplo conceitual (em C):
int a = 10;
int *p = &a;  // p armazena o endereço de a
🔹 Como funcionam os Ponteiros?
· Uma variável aponta para outra quando ela guarda o endereço de memória dessa outra.
· Esse endereço indica onde a variável está armazenada na memória do computador.
· Permite acessar o conteúdo de outra variável de forma indireta, ou seja, sem usar seu nome diretamente.
· Exemplo: Veja as seguintes instruções utilizando a linguagem C como referência:
#include 
int main() {
    int A = 1003;       // A variável “A” tem um valor (por exemplo, 1003)
    int *PONT = &A;    // “PONT” é um ponteiro e aponta para “A”
    // Exibe o endereço de memória de “A” e o valor de “A”retornar raiz;
     fim
  senão se (chave chave)     // Caso 3: Vai para a esquerda
     início
        se (raiz->esq != NULO)
           início
              pai = raiz;
              retornar busca (chave, raiz->esq, pai, encontrada);
           fim
        senão                          // Subárvore esquerda é vazia
           início
              encontrada = FALSO;
              retornar raiz;
           fim
     fim
  senão                                // Caso 4: Vai para a direita
     início
        se (raiz->dir != NULO)
           início
              pai = raiz;
              retornar busca (chave, raiz->dir, pai, encontrada);
           fim
        senão                          // Subárvore direita é vazia
           início
              encontrada = FALSO;
              retornar raiz;
           fim
     fim
fim
📘 3. Como usar essa função (exemplo de chamada)
pai = NULO;
encontrado = FALSO;
aux = busca(30, raiz, pai, encontrado);
· Aqui:
· raiz aponta para o nó principal da árvore.
· pai é uma referência que será atualizada com o nó pai do resultado.
· encontrado recebe VERDADEIRO se achar a chave.
· aux recebe o ponteiro para o nó onde a chave foi encontrada ou onde a busca parou.
🌳 Exemplo 1: Buscando a chave 30 
Caminho da busca:
· Início na raiz: chave 40 → 30 40 → direita (60)
· 75 > 60 → direita (70)
· 75 > 70 → tenta ir para a direita, mas não existe subárvore direita → busca termina.
Resultados:
· aux = $600 (nó com chave 70, onde a busca parou)
· pai = $800 (nó com chave 60)
· encontrado = FALSO
⚠️ Casos especiais:
1. A chave está na raiz (ex: buscar 40): 
· Exemplo: buscar chave 40 (raiz).
· pai = NULO (porque a raiz não tem pai)
· encontrado = VERDADEIRO
2. Árvore vazia (raiz = NULO):
· pai = NULO
· aux = NULO
· encontrado = FALSO
🔄 Resumindo Funcionamento do Algoritmo:
· Se a raiz for nula → chave não encontrada.
· Se a chave == raiz → achou a chave.
· Se a chave raiz → busca na subárvore direita.
📈 Análise de Complexidade da Busca
· Melhor caso: chave está na raiz → O(1)
· Pior caso: percorre até o fim da árvore → O(n)
· Isso acontece em árvores “zig-zag” (sem equilíbrio).
· Em árvores balanceadas: O(log n) 
🌱 Inserção em uma Árvore Binária de Busca (ABB) 
🔹 1. Como funciona a inserção em uma ABB?
· A nova chave sempre será inserida como uma nova folha da árvore.
· Para saber onde inserir, fazemos uma busca pela chave.
· Se a busca não encontrar a chave (o que é obrigatório, pois chaves duplicadas não são permitidas), o algoritmo:
· Retorna o nó pai onde a nova chave deverá ser adicionada.
· A nova chave será inserida como filho esquerdo ou direito, dependendo do valor.
🔸 Casos Especiais
· Árvore vazia:
· Se não existir nenhum nó (raiz é NULO), o novo nó vira a raiz da árvore.
função inserir (inteiro chave, ref registro no *raiz): booleano
inicio
    registro no *pai;
    registro no *aux;
    registro no *novono;
    booleana encontrada;
    aux = busca (chave, raiz, pai, encontrada);
    if (!encontrada)
    inicio
        alocar (novono);
        novono->chave = chave;
        novono->esq = NULO;
        novono->dir = NULO;
        se (aux == NULO)
            raiz = novono;
        senao se (chave chave)
            aux->esq = novono;
        senao
            aux->dir = novono;
        retorne VERDADEIRO;
    fim
    else
        retorne FALSO;
fim
🔧 Pseudocódigo explicado (algoritmo de inserção)
função inserir(chave, raiz):
 1. Realiza a busca da chave:
 - Se a chave já existe → retorna FALSO (não insere).
 - Se não existe:
 a) Aloca um novo nó.
 b) Atribui a chave ao novo nó.
 c) Define filhos esquerdo e direito como NULO.
 d) Se a árvore está vazia → novo nó vira a raiz.
 e) Caso contrário:
 - Se chave chave do nó atual → insere à direita.
 2. Retorna VERDADEIRO (inserção realizada com sucesso).
🌳 Estrutura atual da árvore :
📘 Exemplo 2: Inserir a chave 55
🧠 Situação:
· Chamada: inserir(55, raiz) (raiz é o nó com chave 40)
📌 Passos:
1. Inicia a busca em:
· 40 → 60
2. 55Situação
	O que fazer
	1
	Nó sem filhos
	Apenas remova o nó
	2
	Nó com 1 filho
	Substituir o nó por seu único filho
	3
	Nó com 2 filhos
	Substituir pelo menor valor da subárvore direita 
 
⚙️ O algoritmo da remoção (Algoritmo 9)
   aux = busca (chave, raiz, pai, encontrado);
   if (aux == NULO)
      retornar FALSO; // Tentativa de remoção de uma árvore vazia
   senão se (!encontrado && exato)
      retornar FALSO; // Chave não encontrada
   senão
      inicio
        se (aux->dir == NULO && aux->esq == NULO)
           inicio  
             se (pai == NULO)
               inicio
                 raiz == NULO; // A arvore era unitária, agora é vazia
                 retornar aux;
               fim
             senão
               inicio
                 se (pai->dir == aux)
                    pai->dir = NULO;
                 senão
                    pai->esq = NULO;
                 retornar aux;
               fim
           fim
        senão se (aux->dir == NULO || aux->esq == NULO)
           inicio
             se (pai == NULO)
               inicio
                 se (aux->dir == NULO)
                   raiz = aux->esq;
                 senão
                   raiz = aux->dir;
               fim
             senão
               inicio
                 se (pai->dir == aux)
                    inicio
                      se (aux->dir == NULO)
                         pai->dir = aux->esq;
                      senão
                         pai->dir = aux->dir;
                    fim
                 senão
                    inicio
                      se (aux->dir == NULO)
                         pai->esq = aux->esq;
                      senão
                         pai->esq = aux->dir;
                    fim
               fim
             retornar aux;
           fim
         senão
           inicio
             aux2 = remover (chave, aux->dir, FALSO);
             aux2->dir = aux->dir;
             aux2->esq = aux->esq;
             se (pai == NULO)
                raiz = aux2;
             senão se (pai->dir == aux)
                pai->dir = aux2;
             senão
                pai->esq = aux2;
            retornar aux;
           fim
   fim
fim
Resumo da lógica do algoritmo de remoção:
função remover(chave, raiz):
 1. Buscar o nó com valor == chave
 2. Se não encontrado → return FALSO
 3. Se é folha:
 - Desconectar do pai
 4. Se tem 1 filho:
 - Conectar o filho direto ao pai
 5. Se tem 2 filhos:
 - Achar menor da subárvore direita (sucessor)
 - Copiar valor para o nó atual
 - Remover o sucessor (terá 1 filho)
· Realiza a remoção correta, atualizando os ponteiros dos nós pais/filhos.
· Usa variáveis auxiliares para gerenciar referências (como pai, aux, aux2).
· A função não é recursiva no sentido tradicional, mas pode chamar a si mesma para remover o substituto.
 📈 Complexidade da remoção (todos os casos)
A complexidade depende da altura da árvore e do processo de busca. Em todos os casos, é:
· O(n) no pior caso, onde n é o número de nós.
🟢 Detalhes por caso:
1. Caso 1 (folha):
· Só busca o nó → custo: O(n)
2. Caso 2 (nó com 1 filho):
· Busca até o penúltimo nível → custo: O(n)
3. Caso 3 (nó com 2 filhos):
· Busca o nó original + substituto → custo: O(n)
✅ Resumo Final Simplificado
· Existem 3 tipos de remoção em uma árvore binária de busca.
· A remoção sempre começa com uma busca, que tem custo O(n) no pior caso.
· Mesmo os casos mais simples (folha) exigem uma busca.
· O algoritmo trata de atualizar corretamente os ponteiros entre os nós para manter a estrutura da árvore.
· A complexidade final da operação de remoção é O(n) nos 3 casos.
✅ Complexidade das Operações em Árvores Binárias de Busca (ABB)
	Operações
	Melhor Caso
	Pior Caso
	Árvore Balanceada (caso ideal)
	Busca
	O(1)
	O(n)
	O(log n)
	Inserção
	O(1) (inserção na raiz ou em nó folha)
	O(n)
	O(log n)
	Remoção
	O(n) (nó folha, nó com filho, nó com com dois filhos)
	O(log n)
🧠 Explicação dos termos:
· Melhor caso: a chave está na raiz ou o nó a ser inserido/removido está em posição de fácil acesso (logo no topo).
· Pior caso: a árvore está completamente desbalanceada, como uma lista encadeada, e é preciso percorrer todos os nós — custo linear.
· Árvore balanceada: uma árvore onde a altura é proporcional a log n, ou seja, bem distribuída entre esquerda e direita. É o caso ideal para performance eficiente.
📌 Observações importantes:
· Mesmo que inserção e remoção envolvam mais etapas (como realocar ponteiros ou substituir valores), a busca pela posição correta é o fator dominante de custo portanto possui complexidade O(n).
· Em árvores balanceadas (como AVL, Red-Black Tree, etc.), garante-se que as operações são feitas em tempo logarítmico.
· Em árvores binárias de busca simples desbalanceadas, o desempenho pode degradar para linear.
Módulo 3. Definir o conceito de árvore balanceada
🌳 Árvore Binária Balanceada 
✅ O que vimos antes
· Árvores binárias de busca permitem buscar, inserir e remover elementos dinamicamente.
· Porém, no pior caso, sua eficiência é igual à de uma lista desorganizada:
🔸 Complexidade O(n) para busca, inserção e remoção.
❓ Então por que usar árvores se são tão complexas quanto listas?
· Porque nem toda árvore binária tem baixa eficiência.
· A eficiência depende da forma da árvore, especialmente da sua altura. 
⚠️ Árvore Zig-Zag: Representa o pior caso
· Altura da árvore = número de nós → parece uma lista encadeada.
· Exemplo: uma árvore com 8 nós onde cada nó tem apenas um filho à direita.
· Complexidade: O(n)
🌟 O melhor tipo de árvore: São as árvores balanceadas
· ÁRVORES BALANCEADAS – Balancear uma árvore significa investir um esforço no sentido de mantê-la com um desempenho de uma árvore binária completa que é uma meta na construção de ABB, ou seja, é considerada uma árvore ótima.
· Queremos reduzir a altura da árvore, porque:
· Menor altura → menos comparações → mais eficiência.
· Árvore binária completa:
🔸Uma árvore binária T é completa se os nós de T com subárvores vazias estão no último ou no penúltimo nível.
🔸 Todos os níveis estão completamente preenchidos, exceto possivelmente o último, que deve estar preenchido da esquerda para a direita.
🔸 Altura mínima: 
🔸 Complexidade dos algoritmos arvore binária completa: O(log n) ✔️
📘 Definições importantes
· Árvore binária completa: possui altura mínima, melhor desempenho possível.
· Árvore balanceada: altura proporcional a log n, mas não precisa ser completa.
· Exemplos de árvores balanceadas não completas:
· AVL
· Rubro-Negra
	Afirmação
	Correta?
	Toda árvore binária completa é balanceada.
	✅ Sim
	Toda árvore binária balanceada é completa.
	❌ Não
 
🔍 Construir Árvores Balanceadas 
· A ideia é usar a lógica da pesquisa binária para criar a árvore balanceada.
· A pesquisa binária é um método de busca em um vetor ordenado que se baseia na estratégia dividir para conquistar.
· Para construir uma árvore balanceada com base em um vetor ordenado, deve-se seguir os seguintes passos:
1. Escolha o elemento central do vetor como a raiz da árvore.
2. Divida o vetor em duas metades:
3. Os elementos antes do valor central vão formar a subárvore esquerda.
4. Os elementos depois do valor central vão formar a subárvore direita.
5. Repita esse processo recursivamente para cada metade até os vetores ficarem vazios.
6. Resultado final: árvore binária de busca completa e balanceada.
· Esse processo segue a mesma lógica da pesquisa binária, só que ao invés de buscar um valor, você vai usando os elementos centrais como nós da árvore.
Atenção: Critério para vetor de tamanho par: Escolher o elemento da metade direita como raiz. Assim garantimos que a arvore tenha altura mínima e consequentemente seja completa.
🌳 Construção da árvore balanceada 
· Mesmo vetor ordenado: 10 20 30 40 50 60 70 80
· Passo a passo:
1. Raiz: 50
· Vetor da esquerda: [10, 20, 30, 40]
· Vetor da direita: [60, 70, 80]
2. Subárvore Direita: [60, 70, 80]
· 3 elementos →meio = 70
· Esquerda de 70: [60]
· Direita de 70: [80]
3. Subárvore Esquerda: [10, 20, 30, 40]
· 4 elementos → índice central: 1 e 2 → valores 20 e 30
✅ Escolhemos 30 (metade direita)
· Esquerda de 30: [10, 20] → meio = 30
· Direita de 30 → [40]
· Esquerda de 30 → [20]
· Esquerda de 20 → [10]
✅ Resultado: Árvore Final Completa e Balanceada:
 50
 / \
 30 70
 / \ / \
 20 40 60 80
 /
10
⚙️ Desvantagens do método
· Precisa de:
· Um vetor auxiliar ordenado
· A sequência de chaves ordenadas, o que, sem dúvida, aumenta a necessidade de alocação de memória. Logo é necessário memória extra para armazenar os dados
🛠️ Solução ideal: O ideal é aplicar um algoritmo que resolva o problema de construir uma árvore binária de busca sem utilizar nenhuma estrutura de dados auxiliar, por exemplo:
· Usar o Algoritmo DSW (Day-Stout-Warren):
· Não usa vetor auxiliar
· Constrói uma árvore binária de busca balanceada direto na estrutura existente
✅ O que é o algoritmo DSW?
· O algoritmo DSW transforma uma árvore binária de busca (ABB) em uma árvore binária de busca completa.
· Isso é feito em tempo linear, ou seja, com complexidade O(n).
· A principal operação usada no algoritmo é a rotação, que reorganiza os nós da árvore sem quebrar suas propriedades.
O que é uma rotação?
· É uma operação que troca a posição de pai e filho, reorganizando a árvore.
· Existem dois tipos:
· Rotação para a direita
· Rotação para a esquerda
Ambas mantêm a propriedade da árvore binária de busca:
· Nó à esquerda é menor que a raiz.
· Nó à direita é maior que a raiz.
Tipos de Rotações Usadas
🔄 Rotação à Direita
· Troca um nó com seu filho à esquerda, fazendo com que o filho vire o novo pai.
· Exemplo:
Explicação passo a passo:
1. O nó 8, que é o filho à esquerda de 10, sobe para a posição de 10.
2. O nó 10 desce e se torna o filho direito de 8.
3. O filho direito de 8 (nó 9) passa a ser o filho esquerdo de 10.
4. A estrutura de árvore binária de busca é mantida.
5. Aumenta a altura do lado direito
6. Diminui a altura do lado esquerdo
🔁 Rotação à Esquerda
· É o inverso da rotação para a direita.
· O nó troca de lugar com seu filho à direita.
· O filho direito sobe para ser o novo pai.
· Exemplo: 
Explicação passo a passo:
1. O nó 10, que é o filho à direita de 8, sobe para o lugar de 8.
2. O nó 8 desce e se torna o filho esquerdo de 10.
3. O filho esquerdo de 10 (nó 9) passa a ser o filho direito de 8.
4. A estrutura de árvore binária de busca é mantida.
5. Aumenta a altura do lado esquerdo
6. Diminui a altura do lado direito
🧱 Etapas do Algoritmo DSW
O algoritmo DSW é usado para transformar uma árvore binária de busca desbalanceada em uma árvore binária de busca balanceada, com altura próxima de , usando apenas rotações.
Ele funciona em duas fases:
1. Transformar a árvore em uma "lista" (árvore zig-zag) usando rotações à direita.
2. "Comprime" essa lista para aproximá-la de uma árvore completa e balanceada, fazendo rotações à esquerda.
📌 Passo 1: Transformar a árvore em uma lista “zig-zag”
· A árvore é transformada em uma estrutura linear (tipo lista), onde todos os nós têm apenas filhos à direita.
· Isso é feito com várias rotações à direita, sempre que houver um filho esquerdo.
Exemplo de transformação:
📌 Passo 2: Construir a árvore completa
· Com a estrutura em “zig-zag”, o objetivo agora é equilibrar a árvore com rotações à esquerda, por níveis, das folhas até a raiz.
👨‍🏫 Exemplo com 12 nós 
🎯 Objetivo: Transformar a árvore “zig-zag” → Na árvore balanceada:
📐 Cálculos importantes para o passo 2:
✅ Fórmulas:
· Altura da árvore completa: , onde n=total de nós
· Número de nós de uma árvore completa de altura h: , onde h=altura da arvore 
· Número de nós no último nível: , onde n=total de nós
· Número de rotações no nível 1: , onde
· Número de rotações por compressão nos níveis seguintes: , onde i=nível (1, 2, 3, ...).
🔢 Exemplo para n = 12:
· Altura da árvore completa: 
Altura: h = 1 + 3 = 4
· Número de nós de uma árvore completa:
 
Ou seja, a árvore completa mais próxima que pode conter até 15 nós.
· Número de nós no último nível:
 
Nós do último nível: 12 - 8 + 1 = 5
Ou seja, você faz 5 rotações na primeira compressão.
· Número de rotações por compressão nos níveis seguintes:
	Compressão
	Fórmula
	Rotações calculadas
	Nível
	1ª
	
	5
	4°
	2ª
	
	3
	3°
	3ª
	
	1
	2°
	4ª
	
	0 (parar)
	1°
🧩 Aplicação das rotações no passo 2:
🔸 Nível 4 (último):
· Rotacionar à esquerda nos 5 primeiros nós da lista: 1, 3, 5, 7, 9
🔸 Nível 3:
· Realizar 3 rotações: nos nós que ficam no nível 3 após ajuste do nível 4
🔸 Nível 2:
· Realizar 1 rotação
Com isso, a árvore final é completa e balanceada.
🧮 Complexidade do Algoritmo
O algoritmo DSW tem complexidade linear em tempo, porque percorre a árvore uma vez na criação da espinha e depois faz no máximo O(n) rotações na fase de compressão.
✔ Etapas detalhadas:
1. Fase 1 – Criar a espinha direita (vine):
· Visita todos os nós da árvore duas vez.
· Cada visita pode exigir uma rotação à direita.
· Custo total: O(n).
2. Fase 2 – Compressões (balanceamento com rotações à esquerda):
· A cada compressão, faz rotações.
· Soma das rotações: 
· Logo, custo total: O(n).
🧑‍💻 Pseudocódigo resumido
🔧 Rotação à direita:
função rot_dir_dsw (ref nó *r)
  aux = r->esq // auxiliar recebe filho à esquerda de “r”, que será promovido a nó raiz após a rotação 
  r->esq = aux->dir // O filho direito de 'aux' passa a ser o novo filho esquerdo de 'r'
  aux->dir = r // 'r' se torna filho direito de 'aux'
  r = aux // Atualiza 'r' para apontar para a nova raiz da subárvore (que é 'aux')
🔧 Passo 1 (gerar lista zig-zag):
função passo1_dsw (ref nó *raiz)
  aux = &raiz // 'aux' é um ponteiro para o ponteiro da raiz
  // Enquanto o nó atual não for nulo, percorre a árvore
 enquanto (*aux ≠ NULL) // identifica a criação da arvore zig-zag
    se (*aux)->esq ≠ NULL // Se o nó atual possui filho à esquerda, faz rotação à direita para remover essa ramificação
      rot_dir_dsw(aux) // reorganiza o nó para mover o filho à esquerda para cima
    senão // Caso contrário, avança para o próximo nó à direita
      aux = &((*aux)->dir) // segue para o próximo elemento na "espinha"
🔧 Rotação à esquerda:
função rot_esq_dsw (ref nó *r)
  aux = r->dir // 'aux' recebe o filho à direita de 'r', que será promovido a nó raiz após a rotação
  r->dir = aux->esq // Atualiza o filho direito de 'r' com o filho esquerdo de 'aux'
  aux->esq = r // Coloca 'r' como filho esquerdo de 'aux'
  r = aux // Atualiza 'r' para apontar para a nova raiz da subárvore (que é 'aux')
🔧 Passo 2 (construir árvore balanceada):
função passo2_dsw (ref nó *raiz, int n)
  nr_ult_nv = n - (2^⌊log2(n)⌋) + 1
  alt = 1 + ⌊log2(n)⌋
  para i = 1 até nr_ult_nv
    rot_esq_dsw(aux)
    aux = &((*aux)->dir)
  alt--
  para i = alt até 2
    aux = raiz
    para k = 1 até 2^(i-1) - 1
      rot_esq_dsw(aux)
      aux = &((*aux)->dir)
✅ Tabela Comparativa: Passos e Rotações no Algoritmo DSW
	Aspecto
	Rotação à Direita
	Rotação à Esquerda
	Passo 1 (Cria Zig-Zag)
	Passo 2 (Reconstrói Balanceada)
	Objetivo
	Levantar filho esquerdo
	Levantar filho direito
	Transformar a árvore em uma "lista" (zig-zag)
	Construir uma árvore binária de busca completa
	Quando ocorre?
	Se nó tem filho à esquerda
	Se nó tem filho à direita
	Enquanto houver filhos à esquerda
	Conforme o cálculo de níveis e rotações
	Tipo de rotação usada
	rot_dir_dsw()
	rot_esq_dsw()
	Usa rotação à direita repetidamente
	Usa rotação à esquerda por níveis
	Nome no pseudocódigo
	função rot_dir_dsw(ref no *r)
	função rot_esq_dsw(ref no *r)
	função passo1_dsw(ref no *raiz)
	função passo2_dsw(ref no *raiz, int n)
	Efeito na estrutura
	Reduz altura da subárvore esquerda
	Reduz altura da subárvore direita
	Cria uma árvorelinear com filhos só à direita
	Constrói árvore completa em forma de pirâmide
	Como identificar no código
	A linha aux = r->esq;
	A linha aux = r->dir;
	Loop enquanto (*aux != NULO) e rot_dir_dsw(aux)
	Cálculo de nr_ult_nv, log2(n), rot_esq_dsw()
Módulo 4. Definir árvores AVL
🌳 Árvores AVL
🔎 1. Motivação para usar árvores AVL
· Árvores binárias de busca comuns podem se tornar desbalanceadas, levando a operações lentas (complexidade O(n)).
· Para melhorar o desempenho, buscamos árvores com altura proporcional a log(n).
· Isso leva ao conceito de árvores balanceadas, como as árvores AVL.
🧠 2. O que é uma árvore AVL
· Uma árvore AVL é uma árvore binária de busca onde todos os nós são balanceados. 
· Permitem operações de busca, inserção e remoção em O(log n), tornando-as mais eficientes que árvores binárias de busca não balanceadas.
· Surgiram como uma evolução para garantir um desempenho otimizado.
· Criadas por Adelson-Velsky e Landis (origem da sigla AVL).
· Um nó é considerado balanceado se:
 1 
· Isso significa que: Em árvores AVL, um nó é considerado balanceado quando a diferença de altura entre suas subárvores esquerda e direita é, no máximo, 1.
· A diferença de altura entre suas subárvores esquerda e direita em árvores AVL pode ser 0, 1 ou -1, o que significa que:
· 0: as subárvores têm a mesma altura.
· ±1: a diferença de altura é 1 (ainda aceitável).
· ±2 ou mais: o nó está desbalanceado e será necessário fazer uma rotação para restaurar o equilíbrio.
🔁 3. Árvores completas são dinâmicas
· Dinâmicas e Rápidas: As árvores AVL foram criadas para serem dinâmicas, ou seja, elas se ajustam automaticamente após cada inserção ou remoção, mantendo sempre a propriedade de balanceamento. 
🌳 Árvores completas e AVL
· Todas as árvores completas são AVL, pois respeitam a definição de ambas.
· As árvores completas possuem altura mínima para um dado número n de nós.
📉 Altura mínima das árvores completas
· Árvores completas são AVL e possuem altura mínima: 
· Isso significa que a altura mínima de uma árvore AVL também é proporcional a . 
· Isso significa que, mesmo que você adicione muitos nós, a altura da árvore não cresce tão rapidamente; ela cresce de forma logarítmica, que é muito mais lenta do que um crescimento linear (como n ou n2).
🎯 Árvores AVL no Melhor caso
· No melhor caso, as árvores AVL são completas e têm altura mínima proporcional a log n, ou seja, se você quer uma árvore AVL com a menor altura possível para um dado número de nós, ela será uma árvore .
· Porém, nem todas as árvores AVL são completas.
· Exemplo: a árvore AVL da Figura 25 não é completa, pois há um nó com subárvore vazia no antepenúltimo nível.
· Assim, o teorema da altura das árvores completas não pode ser aplicado a essa árvore específica.
❌ Árvores AVL no Pior caso
· Para garantir que as árvores AVL são sempre eficientes, precisamos analisar o pior caso: qual é a maior altura possível que uma árvore AVL pode ter para um dado número de nós (n)?
· O pior caso ocorre quando uma árvore AVL tem altura máxima para um dado número n de nós.
· Se essa família de árvores AVL tiver altura proporcional a log n, então no melhor e no pior caso a altura da árvore AVL será proporcional a log n. 
· Se mesmo no pior cenário a altura for proporcional a log n, isso nos dá uma garantia importante: as árvores AVL são eficientes em termos de altura, não importa como os nós são adicionados. 
· Árvores de Fibonacci (O "Pior Caso" AVL): É uma família de árvores AVL que, para um dado número de nós, têm a maior altura possível. 
🔨 Como são construídas das árvores AVL de altura máxima
· Para entender melhor o pior caso, devemos construir uma família de árvores AVL com altura máxima e menor número de nós possível.
· Essa construção será feita de forma recursiva.
 Exemplo: 
· Altura h = 1: árvore com 1 nó.
· Altura h = 2: árvore com 2 nós, sendo um, a raiz e outro um filho.
· Para h > 2:
· Criamos uma nova raiz.
· A subárvore esquerda tem altura h-1.
· A subárvore direita tem altura h-2.
🔁 Isso garante o balanceamento AVL e o número mínimo de nós para a altura.
Explicação: Para construir uma Árvore de Fibonacci de altura 'h' com o mínimo de nós, você cria uma nova raiz e anexa a ela uma subárvore de altura 'h-1' em um lado e uma subárvore de altura 'h-2' no outro. Isso garante que a diferença de altura seja sempre 1, mantendo a propriedade AVL, mas forçando a maior altura possível com o mínimo de nós.
📊 7. Relação com a sequência de Fibonacci (Tabela 1)
· As árvores de Fibonacci têm a menor quantidade de nós possível para uma dada altura h, mas ainda mantendo-se balanceada.
· A quantidade mínima de nós é dada pela fórmula baseada na sequência de Fibonacci:
Onde: 
 : É um número mínimo de nós de uma árvore AVL .
 : É o enésimo número da sequência Fibonacci
· Altura ainda é Logarítmica: Mesmo sendo o "pior caso" de altura para uma AVL, como essas árvores também possuem altura proporcional a log n, isso confirma que todas as árvores AVL são balanceadas. 
🧩 9. Conclusão
· Melhor caso: árvores completas → altura mínima = O(log n).
· Pior caso: árvores de Fibonacci → altura máxima = O(log n).
· A altura real de qualquer árvore AVL está entre duas curvas logarítmicas.
· Portanto, todas as árvores AVL é sempre proporcional a log n, ou seja, são balanceadas e garantem desempenho eficiente.
🔍 Busca em uma Árvore AVL
· A árvore AVL é um tipo de árvore binária de busca, então o algoritmo de busca é exatamente o mesmo utilizado em árvores binárias de busca.
· A diferença no desempenho ocorre devido à altura da árvore, que impacta diretamente a complexidade da busca.
⏳ Complexidade da busca depende da altura da árvore
· O que determina a eficiência da busca é a altura da árvore.
· A operação básica da busca é a comparação, que ocorre em cada nível da árvore.
⚠️ Pior caso em árvores binárias de busca comuns
· O pior caso é quando a árvore vira uma linha (zig-zag).
· Isso acontece quando os dados são inseridos em ordem crescente ou decrescente.
· Nessa situação, a altura da árvore é n (quantidade de nós).
· Então, a complexidade da busca é O(n) → muito lenta.
✅ Pior caso em árvores AVL (Exemplo de comparação)
· Árvores AVL se autobalanceiam.
· Mesmo no pior caso, elas mantêm uma altura proporcional a log(n).
· O pior caso é uma árvore de Fibonacci, que é a árvore AVL com altura mais alta possível, mas ainda assim balanceada.
· Portanto, a complexidade da busca em árvores AVL é O(log n) → muito mais eficiente.
📌 Resumo final
· A busca em uma árvore AVL é mais rápida que em uma árvore binária comum porque:
· A altura é menor, graças ao balanceamento.
· Isso reduz o número de comparações necessárias para encontrar um valor.
Importância da Altura
· A altura da árvore define a eficiência da busca, pois o algoritmo percorre níveis até encontrar o valor desejado.
· Como a busca envolve comparações em cada nível da árvore, no pior caso, o número de comparações será igual à altura da árvore.
· Em árvores AVL, essa altura é muito menor do que em árvores binárias de busca desbalanceadas, garantindo um desempenho muito mais eficiente.
Inserção em uma árvore AVL
📌 Conceitos Gerais
· Árvore AVL é uma árvore binária de busca com a propriedade adicional de balanceamento:
Para cada nó, a diferença entre a altura das subárvores esquerda e direita (chamada de balanço) deve ser no máximo 1 em valor absoluto: 1
· A inserção em uma árvore AVL funciona como na árvore binária de busca normal:
· Localiza-se onde a nova chave deve ser inserida por meio de comparações.
· Após inserir, é preciso verificar se a árvore continua balanceada (AVL). Se não estiver, aplica-se uma rotação para corrigir.
⚖️ Quando ocorre desequilíbrio?
· Um nó está desregulado se .
· Ao inserir um novo nó, pode ocorrer desequilíbrio (desregulagem) em algum ancestral do novo nó inserido.
· O nó mais profundo desregulado (mais distante da raiz) é o foco da correção.
🌲 Casos de Desequilíbrio e Correções
· Quando um nó fica desbalanceado (ou seja, o fator de balanceamento não está entre -1 e 1),fazemos uma rotação para restaurar o equilíbrio.
· Existem dois casos principais (1 e 2), com dois subcasos cada (a e b), dependendo de onde ocorre a inserção:
✅ Caso 1 – Rotação simples à esquerda
· Condição: Inserção à direita do filho direito de um nó desregulado.
· Exemplo: Inserimos 90 numa árvore com 60 e 80.
· Correção – Rotação simples à esquerda:
Fazer o nó 80 virar a nova raiz da subárvore. 
O 60 vira filho esquerdo e o 90 filho direito.
· Após essa rotação simples à esquerda, a árvore volta a ficar balanceada.
🔁 Caso 2 – Rotação dupla à esquerda
· Condição: Inserção à esquerda do filho direito (situação em "zig-zag").
· Exemplo: Inserimos 65 numa árvore com 50 e 70. 
· Correção – Rotação dupla à esquerda:
Primeiro faz-se uma rotação à direita no filho (70 vira 65). 
Depois uma rotação à esquerda no avô (50 vira filho de 65).
✅ Caso 3 – Rotação simples à direita
· Condição: Inserção à esquerda do filho esquerdo de um nó desregulado.
· Exemplo: Inserimos 10 numa árvore com 30 e 20.
· Correção – Rotação simples à direita:
O 20 vira a nova raiz da subárvore, com o 10 à esquerda e o 30 à direita.
🔁 Caso 4 – Rotação dupla à direita
· Condição: Inserção à direita do filho esquerdo (zig-zag espelhado).
· Exemplo: Inserimos 25 numa árvore com 30 e 20.
· Correção – Rotação dupla à direita:
Primeiro faz-se uma rotação à esquerda no filho (25 vira 20). 
Depois uma rotação à direita no avô (30 vira filho de 25).
🧠 Dica para lembrar:
· Se a inserção aconteceu na mesma direção duas vezes (EE ou DD) → rotação simples.
· Se foi em direções opostas (ED ou DE) → rotação dupla.
📐 Como identificar qual rotação usar em uma árvore AVL?
· A árvore AVL usa balanceamento de altura para se manter equilibrada após inserções ou remoções.
🔢 O que é o "balanço" de um nó?
Chamamos de o fator de balanceamento (ou balanço) do nó x, e ele é calculado assim:
Regra de Balanceamento para Cada Nó:
· Nó folha: 
· No com 1 filho:
· 1 filho á esquerda: 
· 1 filho a direita: 
· Nó com 2 filhos:
· 1 filho a esquerda e 1 filho a direita: 
Exemplo: Porque o nó 50 tem fator de balanceamento igual a +2?
Explicação: O nó 50 tem 2 filhos a esquerda e 0 a direita:
O balanceamento dos demais nós, segue a regra acima demonstrada.
Fator de Balanceamento Total da Árvore: 
Deve-se calcular o fator de balanceamento do nó raiz.
	bal(x)
	Situação
	Estado da Árvore
	Altura da Árvore no Nó x
	0
	Alturas iguais
	✅ Totalmente balanceada
	✅ Altura mínima
	+1
	Esquerda 1 nível maior
	✅ Ainda balanceada
	⚠️ Altura máxima
	–1
	Direita 1 nível maior
	✅ Ainda balanceada
	⚠️ Altura máxima 
	±2 ou mais
	Diferença maior que 1
	❌ Desbalanceada – precisa de rotação
	🚨 Altura acima do permitido
Exemplo: Qual o fator de balanceamento da árvore ao lado?
Explicação: Para isso, calculamos o fator de balanceamento do nó raiz, que é o nó 10.
Sabemos que o nó 10 tem 2 filhos a esquerda e 3 a direita:
 
Logo, a árvore AVL é balanceada e possui a altura máxima.
🔍 Como identificar o tipo de rotação?
✅ Caso 1 – Excesso à direita → 
Significa que a subárvore direita está muito mais alta.
🔸 Subcaso 1: Rotação simples à esquerda
· ou 
· Crescimento foi no ramo direito do filho direito
📌 Exemplo:
✔️ Correção: Rotação simples à esquerda →
🔸 Subcaso 2: Rotação dupla à esquerda
· 
· Crescimento foi no ramo esquerdo do filho direito (zig-zag)
📌 Exemplo:
✔️ Correção: Rotação dupla à esquerda → 
1. Rotação à esquerda no filho
2. Rotação à esquerda no 
✅ Caso 2 – Excesso à esquerda → 
Significa que a subárvore esquerda está muito mais alta.
🔸 Subcaso 3: Rotação simples à direita
· ou 
· Crescimento foi no ramo esquerdo do filho esquerdo
📌 Exemplo: 
✔️ Correção: Rotação simples à direita → 
🔸 Subcaso 4: Rotação dupla à direita
· 
· Crescimento foi no ramo direito do filho esquerdo (zig-zag espelhado)
📌 Exemplo:
✔️ Correção: Rotação dupla à direita → 
🧠 Dica prática para lembrar os tipos de rotação:
	Caso
	Caminho da inserção
	Situação do 
	Situação do 
	Direção da rotação
	DD
	Direita → Direita
	-2 (excesso direita)
	-1 ou 0
	🔁 Rotação simples à esquerda (1)
	DE
	Direita → Esquerda
	-2
	+1
	🔁 Rotação dupla à esquerda (2)
	EE
	Esquerda → Esquerda
	+2 (excesso esquerda)
	+1 ou 0
	🔁 Rotação simples à direita (3)
	ED
	Esquerda → Direita 
	+2
	-1
	🔁 Rotação dupla à direita (4)
Conclusão
· Inserção em uma árvore AVL segue a lógica da busca em uma árvore binária de busca comum.
· Após a inserção, verificamos o balanço dos nós para garantir que a árvore permaneça AVL.
· Rotações simples e duplas são utilizadas para restaurar o balanceamento sem alterar a altura da árvore.
🌳 Remoção em Árvores AVL 
🧠 Conceito Geral
· A remoção em uma AVL é parecida com a inserção, mas ao invés de crescimento de um ramo, temos o encurtamento de um ramo.
· Após a remoção de um nó, a árvore pode ficar desequilibrada, e será necessário aplicar rotações para corrigir.
⚙️ Passos da Remoção
1. Etapa 1: Remova o nó como em uma árvore binária de busca comum (três subcasos):
· Nó folha → Remove diretamente.
· Nó com um filho → Substitui pelo filho.
· Nó com dois filhos → Substitua o nó pelo menor valor da subárvore direita (sucessor), e remova o sucessor recursivamente.
2. Etapa 2: Atualize os fatores de balanceamento subindo pela árvore.
· Após a remoção, a altura da árvore pode diminuir.
· Isso pode causar desequilíbrio em algum ancestral do nó removido.
· Então, verificamos os fatores de balanceamento e aplicamos rotações se necessário.
3. Etapa 3: Aplique rotações AVL sempre que:
· (excesso à direita) → rotação à esquerda
· (excesso à esquerda) → rotação à direita
· Lembrete: Remover um nó da subárvore direita equivale a inserir um nó na sub-árvore esquerda.
🔷 Exemplo: Remoção em Árvore AVL como na Árvore de Fibonacci
📌 Conceitos-chave
· A árvore da Figura 44 é chamada de Árvore de Fibonacci e representa um pior caso para remoções em árvores AVL (isto é, exige várias rotações para manter o equilíbrio).
· Quando se remove um nó, o balanceamento da árvore pode ser afetado — e por isso é necessário aplicar rotações.
· Cada rotação tem complexidade O(1) e o caminho da remoção até a raiz tem no máximo altura log(n), então a remoção continua sendo O(log n).
🔄 Rotação e Balanceamento
· Após uma remoção, a árvore pode ficar desequilibrada. O desequilíbrio é indicado pelo fator de balanço (bal) de um nó.
· 
🧩 Exemplo com a Figura 44:
1. Remoção do nó 10
· O nó 11 agora tem bal = 2 e o nó 12 tem bal = 1
· Esse é o caso 1 → rotação simples à esquerda
2. Após rotação no 11 (Figura 45)
· O nó 14 agora tem bal = 2 e o nó 17 tem bal = 1
· Novamente caso 1 → rotação simples à esquerda no 14
3. Após rotação no 14 (Figura 46)
· O nó 22 agora tem bal = 2 e o nó 30 tem bal = 1
· Novamente caso 1a → rotação simples à esquerda no 22
4. Após rotação no 22 (Figura 47)
· A árvore volta a estar balanceada
🧠 Conclusão
· Cada rotação isolada tem custo O(1).
· A remoção em árvores AVL pode envolver múltiplas rotações em cadeia, no pior caso, indo do nó removido até a raiz.
· Mesmo assim, o custo permanece O(log n) graças ao limite de altura da árvore.
· Após cada rotação, o fator de balanço dos nós deve ser recalculado e comparado com os casos já estudados na inserção:
📊 Quando aplicar cada tipo de rotação após remoção?
	Condição em v
	Condição no filho
	Sinais
	Tipo de rotação
	Caso
	bal(v) = -2
	bal(filho_dir) = 0 ou -1
	iguais
	Simples à esquerda
	DD
	bal(v) = -2
	bal(filho_dir) = +1
	diferentes
	Dupla à esquerda
	DE
	bal(v) = +2
	bal(filho_esq) = 0 ou +1
	iguais
	Simples à direita
	EE
	bal(v) = +2
	bal(filho_esq) = -1
	sinais diferentes
	Dupla à direita
	ED
	
📚 Complexidade da Árvore AVL
🌲 O que são Árvores AVL?
· Árvores AVL são árvores binárias de busca balanceadas.
· A altura de uma árvore AVL é proporcional a log(n), onde n é o número de nós.
🔍 Complexidade da Busca
· A busca percorre a árvore a partir da raiz até uma folha.
· Em uma AVL, o caminho máximo até a folha é curto (proporcional a log n).
· Portanto,a complexidade da busca é: O(log n)
➕ Complexidade da Inserção
· A inserção de uma nova chave ocorre da mesma forma que na árvore binária de busca comum.
· Como primeiro passo, buscamos a posição correta → já é O(log n).
· Após a inserção, a árvore pode se desbalancear.
✅ Se for necessário, aplica-se uma rotação (ou duas em caso de rotação dupla).
· 🌀 Rotação é uma operação simples, que ajusta no máximo 3 nós.
· Rotação individual: O(1)
· Mesmo se ocorrer rotação, a altura do ramo onde ela ocorre geralmente se mantém, o que evita a propagação de rotações para cima.
· 📌 Resultado final: 
· Inserção: O(log n)
➖ Complexidade da Remoção
· A remoção também começa com uma busca para encontrar o nó a ser removido → O(log n).
· A depender do caso (remoção de folha, de nó com 1 ou 2 filhos), a árvore pode encurtar em um ramo e desbalancear.
❗ Pior Caso:
· Ocorre na árvore de Fibonacci AVL (estrutura mais profunda permitida pela regra AVL).
· Ao remover a folha menos profunda, pode haver propagação do desbalanceamento até a raiz.
· Isso exige várias rotações consecutivas.
· 📌 Mas como cada rotação = O(1) e no máximo ocorrem O(log n) rotações...
· 🧮 Resultado final: 
· Remoção: O(log n)
✅ Conclusão Final
	Operação
	Complexidade
	Busca
	O(log n)
	Inserção
	O(log n)
	Remoção
	O(log n)
· As árvores AVL são altamente eficientes para operações dinâmicas.
· Garantem que a árvore permaneça balanceada, mesmo após muitas inserções e remoções.
· Isso mantém o desempenho ótimo e previsível.
TEMA 6. ALGORITMOS EM GRAFOS (CRÉDITO DIGITAL)
✅ Introdução à Teoria dos Grafos
· Origem antiga: A teoria dos grafos é estudada desde o século XVIII, ou seja, bem antes da criação dos computadores.
· Aplicações atuais: Mesmo sendo antiga, essa teoria é amplamente utilizada hoje em diversas áreas, especialmente em tecnologia.
📱 Aplicações dos grafos
· Grafos são usados em diversos problemas reais, incluindo redes sociais, logística e rotas.
· Nas redes sociais, os grafos ajudam a:
· Identificar quais amigos curtiram um post.
· Sugerir novos contatos com base em conexões existentes.
· Existem bancos de dados especializados para armazenar grafos e extrair informações úteis sobre a atividade dos usuários.
📚 Importância do estudo de grafos
· O estudo dos grafos permite entender diferentes tipos e classificações.
· É essencial para desenvolver algoritmos de busca, que encontram elementos específicos dentro de um grafo.
· Também é usado para criar algoritmos de menor custo, úteis para:
· Definir rotas de ônibus mais eficientes.
· Otimizar entregas e transportes.
Módulo 1. Definir os conceitos básicos de grafos
📌 Conceitos de Grafos
🧮 O que é a Teoria dos Grafos?
· É uma estrutura matemática estudada desde o século XVII.
· Permite representar e resolver problemas usando pontos (vértices) e ligações (arestas) entre eles.
· Ganhou destaque com o problema das Pontes de Königsberg, descrito por Leonhard Euler em 1736.
🌉 Exemplo Clássico: As Pontes de Königsberg
· Cenário:
A cidade de Königsberg era cortada por um rio com duas ilhas e sete pontes ligando os pedaços de terra.
· Problema proposto:
É possível cruzar todas as pontes uma única vez e retornar ao ponto de partida?
· Resposta de Euler:
Euler mostrou que isso não é possível, criando um tipo de problema conhecido como Caminho Euleriano.
👉 Explicação mais simples:
Imagine que você quer dar um passeio por essa cidade e passar por todas as pontes apenas uma vez, sem repetir nenhuma e ainda voltar de onde saiu.
Euler provou que, com esse número e arranjo de pontes, isso não pode ser feito.
Esse desafio deu origem a muitos conceitos usados hoje na Teoria dos Grafos.
🖥️ Evolução com a Computação
· Avanço dos estudos: Com o tempo, a teoria foi se desenvolvendo e ganhou aplicações práticas.
· Importância na computação: Quando os computadores surgiram, os grafos passaram a ser usados para modelar problemas e simular processos matemáticos complexos.
💡 Aplicação em Problemas Complexos
· Problemas NP-difícil e NP-completo:
Muitos desses problemas (que são muito difíceis de resolver) usam estruturas de grafos e algoritmos de caminhos para encontrar soluções eficientes.
👉 Exemplo simplificado:
Imagine que um entregador precisa visitar várias cidades e voltar para o início, gastando o menor tempo ou custo possível. Esse tipo de problema pode ser modelado com grafos e resolvido com algoritmos específicos, mesmo sendo muito difícil computacionalmente.
📌 O que é um Grafo?
· É uma estrutura matemática usada para representar relações entre objetos. 
· Representado como um par ordenado de conjuntos disjuntos (V, E):
· V: conjunto dos vértices (ou nós).
· E: conjunto das arestas, que conectam pares de vértices.
· O grafo possui a seguinte representação na notação de grafos G(V, E)
🔧 Características dos Grafos
· Vértices (nós): são os elementos conectados pelo grafo.
· Arestas: ligam dois vértices e podem ser:
· Simples (sem peso ou direção).
· Direcionadas (dígrafo) – quando possuem sentido específico.
· Com peso – usadas em problemas de otimização, como rotas.
👁️Representação Visual
· Círculos são usados para os vértices.
· Linhas representam as arestas.
· Se o grafo for direcionado, a linha será substituída por uma seta.
Exemplo: Grafo entre estados do Sudeste do Brasil
O grafo representa os estados como nós e as fronteiras geográficas entre eles como arestas.
🔤 Notação matemática:
· Vértices (V) = {ES, MG, SP, RJ}
· Arestas (E) = {(MG, SP), (RJ, SP), (MG, ES), (RJ, MG), (RJ, ES)}
🧩 Construção passo a passo: 
Consideramos como arestas apenas os estados que possuem fronteira geográfica entre si. Um grafo é construído considerando par de arestas “ligando” dois nós.
1. Figura 1.2 – Adição da aresta (SP, MG)
→ Apenas SP e MG estão conectados.
2. Figura 1.3 – Adição da aresta (RJ, SP)
→ Agora SP está conectado com RJ e MG.
3. Figura 1.4 – Adição da aresta (MG, ES)
→ ES se conecta com MG, formando mais um elo.
4. Figura 1.5 – Adição da aresta (RJ, MG)
→ RJ se conecta com MG, aumentando o número de conexões. 
5. Figura 1.6 – Adição da aresta (RJ, ES)
→ RJ agora também está conectado com ES.
👉 Finalização da construção do grafo final:
Todos os estados estão conectados com os vizinhos com quem fazem fronteira.
⚠️ Observação importante
· A ordem de construção das arestas não importa.
· O grafo é apenas um conjunto de conexões, então qualquer sequência de adição das arestas leva ao mesmo grafo final.
🧠 Aplicações práticas de grafos
· Vários problemas podem ser resolvidos através dos algoritmos de caminhos sobre grafos, por exemplo: 
· Menor caminho entre estados sem repetir cidades.
· Roteamento de entregas, carregando o máximo possível por trecho.
· Esses tipos de problemas são resolvidos com algoritmos de caminhos, que serão estudados nos próximos módulos.
Definições de Grafos 
📌 Estrutura do Grafo
· Um grafo é formado por:
· Conjunto de nós (vértices): V(G) = {a, b, c, d}
· Conjunto de arestas: E(G) = {e1, e2, e3, e4, e5, e6}
· Cada aresta conecta dois vértices, por exemplo:
· ψG(e1) = ac (liga a a c)
· ψG(e2) = ab (liga a a b)
· ψG(e6) = cc (laço, pois conecta c a ele mesmo)
🧩Conceitos Básicos
· Extremidades: Quando uma aresta conecta dois vértices, esses vértices são considerados as extremidades daquela aresta. Exemplo: a e b são extremidades de e2 e e3.
· Vértices adjacentes: Se compartilham a mesma aresta. Exemplo: a e b são adjacentes, mas c e d não são.
· Laço: Aresta que conecta um nó a ele mesmo. Exemplo: e6 é um laço, pois ψG(e6) = cc.
· Arestas paralelas: Quando duas arestas diferentes conectam os mesmos vértices. Exemplo: e2 e e3 são paralelas, pois ambas ligam a a b.
· Grafos simples: Grafos que não possuem laços nem arestas paralelas. O grafo da Figura 1.7 não é simples, mas pode ser redesenhado para ser simples (Figura 1.8).
🧮 Grau de um Vértice
· O grau de um vértice é o número de arestas ligadas a ele (Figura 1.7):
· d(a) = 3, pois há três arestas ligadas a a.
· d(b) = 4, pois há quatro arestas ligadas a b.
· Exemplo aplicado aos estados da região Sudeste (Figura 1.9):· d(SP) = 2, d(MG) = 3, d(ES) = 2, d(RJ) = 3.
· Isso indica que MG e RJ faz fronteira com três estados.
🔗 Grafo Conexo e Desconexo
· Um grafo é conexo quando é possível chegar de qualquer vértice a qualquer outro através das arestas.
· Exemplo: O grafo da Figura 1.9 é conexo, pois é possível viajar entre qualquer estado.
· Se um vértice não puder ser alcançado, o grafo é desconexo (Figura 1.8 é um exemplo), ou seja, um vertice está isolado e não se conecta a nenhum outro nó.
✅ Conclusão
· Os grafos representam conexões entre elementos (pessoas, cidades, estados, etc.).
· É possível analisar e resolver problemas visuais e computacionais com base em conceitos como grau, adjacência, conexidade e estrutura simples.
· Os grafos simples e conexos são mais fáceis de interpretar e resolver algoritmos.
📚 Importância dos tipos de grafos
· Para aplicar grafos na prática (como em algoritmos e problemas reais), é necessário:
· Conhecer diferentes tipos de grafos.
· Entender teoremas que ajudam na análise e construção de soluções.
· Utilizar algoritmos que percorrem os grafos.
Módulo 2. Identificar as diferentes representações de grafos
📌 Representação de grafos
· Os grafos podem ser representados matematicamente e têm diversas aplicações.
· Para caminhar sobre grafos, usamos algoritmos baseados em seus diferentes tipos.
· Um grafo G pode ser descrito por:
· V(G) → conjunto de vértices (nós) do grafo
· A(G) → conjunto de arestas do grafo
📏 Teorema da Soma dos Graus dos Vértices
🔹 Em todo grafo G, a soma dos graus dos vértices é igual ao dobro do número de arestas.
🔹 Fórmula: 
Onde:
· v ∈ V(G): todos os vértices do grafo.
· d(v): grau do vértice N, ou seja, quantas arestas estão ligadas a ele.
· m: número total de arestas do grafo.
🔹 Explicação do teorema:
· Quando contamos os graus dos vértices, estamos contando cada extremidade de uma aresta.
· Como cada aresta tem duas extremidades, ela é contada duas vezes.
✅ Exemplo com o grafo da região Sudeste (Figura 2.1)
Estados: SP, MG, RJ, ES
Fronteiras: representadas como arestas (ligações entre os estados) 
Valores:
· Arestas (m) = 5
· Graus:
· d(SP) = 2 (SP faz fronteira com MG e RJ)
· d(MG) = 3 (MG faz fronteira com SP, RJ, ES)
· d(RJ) = 3 (RJ faz fronteira com SP, MG, ES)
· d(ES) = 2 (ES faz fronteira com MG e RJ)
Aplicando a fórmula:
· Número de arestas: m = 5
· Soma dos graus: 10
· Confirmação: 2m = 10 
 2.5 = 10 ✅
🟢 A soma dos graus bate com o dobro do número de arestas, confirmando o teorema.
📌 Corolário: Vértices de Grau Ímpar
🔹 Todo grafo possui um número par de vértices com grau ímpar.
🔹 Demonstração do colorário:
· Se houvesse um número ímpar de vértices com grau ímpar:
· A soma total dos graus seria ímpar.
· Mas o teorema mostrou que a soma dos graus é sempre par (pois é 2⋅m).
➡️ Portanto, não pode existir número ímpar de vértices com grau ímpar.
✅ Exemplo do corolário com o grafo do Sudeste:
Graus:
· d(SP) = 2 (par)
· d(MG) = 3 (ímpar)
· d(RJ) = 3 (ímpar)
· d(ES) = 2 (par)
➡️ Existem dois vértices com grau ímpar (MG e RJ), que é um número par → corolário confirmado.
✔️ Conclusão
· A representação formal de grafos usa conjuntos de vértices e arestas.
· O teorema da soma dos graus ajuda a validar e entender a estrutura de um grafo.
· O corolário mostra que sempre teremos um número par de vértices com grau ímpar.
· Esses conceitos são a base para algoritmos e aplicações práticas com grafos.
📌 Operações em Grafos
As operações básicas em grafos envolvem remover vértices ou arestas. Cada operação altera a estrutura do grafo.
🧹 1. Remoção de Vértices
🔹 O que acontece?
· Ao remover um vértice v, também são removidas todas as arestas ligadas a ele.
· O conjunto de vértices do novo grafo será:
✅ Exemplo:
· Grafo original:
· Vértices: 
· Arestas: 
· Ação: remover o vértice e.
· Resultado:
· Vértices: 
· Arestas (somem as que envolviam o "e"): 
🔎 Explicação simples: Ao tirar o vértice e, todas as conexões dele somem também.
✂️ 2. Remoção de Arestas
🔹 O que acontece?
· Ao remover uma aresta “e5”, o conjunto de vértices permanece igual, mas o conjunto de arestas é alterado:
· O grafo resultante é 
✅ Exemplo:
· Grafo original:
· Vértices: 
· Arestas: 
· Ação: remover a aresta e5
· Resultado:
· Vértices: continuam os mesmos → 
· Arestas: todas as anteriores menos e5
📌 Explicação simples: os nós continuam, mas a ligação entre dois vértices específicos desaparece.
✔️ Conclusão
🔸 Remover vértice → apaga o nó e todas as conexões ligadas a ele.
🔸 Remover aresta → apaga apenas uma conexão, mantendo os vértices.
Essas operações são fundamentais para modificar e analisar grafos, ajudando na solução de problemas estruturais.
📌 Tipos Especiais de Grafos
🔷 Grafo Completo ()
· Todos os vértices estão conectados entre si.
· Cada par de vértices possui exatamente uma aresta ligando-os.
· Representado por: , onde é o número de vértices. 
· Fórmula para calcular o número de arestas: 
🏆 Exemplo: Considere um campeonato no qual todos os times devem jogar com todos os times. As equipes seriam formadas pelas respectivas turmas do ensino médio: 11A, 11B, 21A, 22B, 31A e 31 B. Esse tipo de exemplo apresenta uma situação que pode ser representada através de um grafo completo. Cada nó representa um time do campeonato, e cada aresta representa um jogo do campeonato. Nesse nosso exemplo é K6. 
Resposta:
· Um campeonato onde todos os times jogam entre si.
· Times formados por turmas: 11A, 11B, 21A, 22B, 31A, 31B → 6 times = 
· Fórmula para o número de jogos (arestas): 
Para 6 times: 
🔷 Grafo Complementar ()
· Um grafo complementar é um tipo de grafo que, mostra as conexões que não existem no grafo original.
· Formalmente, o grafo complementar de é denotado por , e sua definição é a seguinte:
1. Vértices: O conjunto de vértices de é o mesmo que o de , ou seja, → Vértices iguais
2. Arestas: O conjunto de arestas de tem exatamente as arestas que não tem → Possui arestas que o original (G) não tem 
Resumindo: O complementar de um grafo é construído assim:
1. Mantém os mesmos vértices.
2. Adiciona as arestas que estavam faltando.
3. Remove as arestas que já existiam.
Exemplo: Considerando o exemplo apresentado anterior do campeonato, vamos supor que exista a necessidade de construir um grafo que represente os jogos do campeonato que ainda não foram disputados.
· (a), temos o grafo que apresenta todos os jogos disputados.
· (b), que representa os jogos não disputados. Esse grafo resultante é complementar de (a).
⚠️ Observação: "O complementar de um grafo completo é um grafo sem arestas (também chamado de grafo nulo ou vazio) e vice-versa".
📌 Explicando:
· Um grafo completo já tem todas as arestas possíveis entre os vértices.
· O complementar dele será o grafo com nenhuma dessas arestas.
· Isso gera um grafo sem nenhuma ligação — ou seja, um grafo nulo. 
🔷 Grafo Nulo ou Vazio
· Não possui nenhuma aresta.
· Os vértices existem, mas não há ligações entre eles. 
🏁 Exemplo:
· No campeonato, antes do início dos jogos, nenhum time jogou ainda.
· Isso pode ser representado por um grafo nulo: os times estão lá, mas sem jogos realizados (arestas).
🔷 Grafo Regular
· Todos os vértices têm o mesmo número de conexões (arestas). 
· Um grafo é k-regular se cada vértice tem grau k.
📌 Exemplo:
· Grafo 3-regular: todos os nós têm grau 3, ou seja, cada nó está ligado a 3 outros nós.
🔷 Ciclo
· É um tipo especial de grafo regular.
· Todos os vértices têm grau 2.
· Forma um “caminho fechado”, ou seja, uma volta completa, como um círculo. 
· A notação é: 
🔷 Grafo Direcionado (ou Digrafo)
· As arestas têm direção — vão de um vértice a outro. 
· Cada aresta é representada como um par ordenado: , indicando que vai de para .
· Termos importantes:
· Divergente: sai do vértice.
· Convergente: chega no vértice.
· Cada vértice tem:
· Grau de saída: quantas arestas saem dele.
· Grau de entrada: quantas chegam nele.
🧠 Teorema:
· A soma dos graus de saída é igual à soma dos graus de entrada, e ambas são iguais ao número total de arestasno grafo.
🖼️ Exemplo (grafo com 5 nós: a, b, c, d, e):
Arestas: 
· Total de arestas: 7
· Soma dos graus de saída = 7
· Soma dos graus de entrada = 7 ✅
🔷 Grafo Subjacente 
· É o grafo obtido ao remover a direção das arestas de um grafo direcionado. 
· É o grafo que a gente obtém a partir de um grafo direcionado, removendo as direções das arestas.
📌 Em outras palavras:
· O grafo subjacente é a versão não direcionada de um grafo direcionado.
· Fica como se fosse um grafo comum, não direcionado, mas com as mesmas conexões. 
Representação dos Grafos
✅ Representação de Grafos por Matrizes
📌 Matrizes
· Uma matriz é uma tabela com linhas e colunas, muito usada em matemática e computação.
· Em grafos, a matriz mais comum é a matriz de adjacência.
🔹 O que é uma matriz de adjacência?
· É uma matriz (ou tabela) usada para representar a conexão entre os vértices de um grafo.
· Essa matriz é quadrada (n × n), onde n é o número de vértices (nós).
· Cada célula da matriz indica se existe ou não uma aresta (ligação) entre dois vértices.
🔹 Como preencher a matriz de adjacência?
Para um grafo com vértices , a matriz é definida como:
· se existe uma aresta entre os vértices e ​.
· se não existe aresta entre e ​.
🟦 Exemplo: Considerando ao grafo da figura abaixo:
· Vértices: a, b, c, d, e (5 vértices)
· Arestas:
· a–b
· a–c
· a–e
· b–c
· d–e
🔸 Cada linha e coluna da matriz corresponde a um vértice (na mesma ordem: a, b, c, d, e).
🧮 Matriz de adjacência resultante: 
	
	a
	b
	c
	d
	e
	a
	0
	1
	1
	0
	1
	b
	1
	0
	1
	0
	0
	c
	1
	1
	0
	1
	0
	d
	0
	0
	1
	0
	1
	e
	1
	0
	0
	1
	0
✅ Como interpretar?
Por exemplo, o valor 1 na posição (a,b) significa que há uma aresta entre os vértices a e b.
Como é um grafo não direcionado, a matriz é simétrica, ou seja, se (a,b) = 1, então também (b,a) = 1.
🟦Etapas para construir uma matriz de adjacência
1. Liste os vértices do grafo.
1. Crie uma matriz quadrada , onde cada linha e coluna representa um vértice.
1. Marque as arestas
Para cada aresta:
· Em grafos não direcionados: marque duas posições: e 
· Em grafos direcionados: marque apenas uma direção: 
	Característica
	Grafo Não Direcionado
	Grafo Direcionado
	Sentido da ligação
	Não tem sentido (vai e volta)
	Tem direção (vai de um para outro)
	Tipo de aresta
	Aresta (i, j) = também conecta (j, i)
	Aresta (i → j) ≠ (j → i)
	Na matriz [i][j]
	1 se existe ligação entre i e j
	1 se existe ligação de i para j
	Simetria da matriz
	Sempre simétrica
	Pode não ser simétrica
	Exemplo visual
	(i) ― (j)
	(i) → (j)
⚠️ Observações importantes:
· A complexidade de espaço dessa representação é O(n²) — ou seja, cresce rapidamente com o número de vértices.
· Não pode representar arestas paralelas (duas arestas entre os mesmos vértices).
· A diagonal principal (de a–a, b–b etc.) é zerada se o grafo não possui laços (ou seja, vértice ligado a ele mesmo).
✅ Matriz de Incidência de um Grafo
🔹 O que é uma matriz de incidência?
· É uma forma de representar grafos com vértices e arestas.
· A matriz de incidência tem n linhas (vértices) e m colunas (arestas).
· Serve para mostrar quais vértices estão ligados por quais arestas.
🔹 Como preencher a matriz?
A matriz , com:
· se o vértice está ligado à aresta .
· caso contrário (vértice não participa da aresta ).
🟦 Exemplo: Considerando ao grafo da figura abaixo:
· 
· Vértices: a, b, c, d, e 
· Arestas:
· e1: a–b
· e2: b–c
· e3: a–c
· e4: a–e
· e5: e–d
· e6: c–d
🧮 Matriz de Incidência resultante:
	
	e1
	e2
	e3
	e4
	e5
	e6
	a
	1
	0
	1
	1
	0
	0
	b
	1
	1
	0
	0
	0
	0
	c
	0
	1
	1
	0
	0
	1
	d
	0
	0
	0
	0
	1
	1
	e
	0
	0
	0
	1
	1
	0
✅ Como interpretar?
· Linha = vértices (a, b, c, d, e)
· Coluna = arestas (e1, e2, e3, e4, e5, e6)
· Por exemplo:
· Na coluna de e1, temos 1 em a e b → indica que a aresta e1 conecta a e b.
· Na coluna de e4, temos 1 em a e e → e4 liga a e e.
⚠️ Observações importantes:
· A matriz de incidência não representa laços (arestas que ligam um vértice a ele mesmo).
· A complexidade de espaço dessa matriz é O(n × m), ou seja, depende do número de vértices e arestas.
· É útil para grafos esparsos (com poucas conexões), pois mostra exatamente onde cada aresta atua.
Módulo 3. Descrever os algoritmos de busca em grafos
✅ Algoritmos de Busca em Grafos
🔍 O que são algoritmos de busca?
· São métodos usados para explorar ou percorrer um grafo (ou seja, caminhar entre seus vértices e arestas).
· Eles nos ajudam a descobrir conexões entre elementos representados por um grafo.
· Muito usados em inteligência artificial e redes sociais.
🌐 Exemplo simples (redes sociais)
· Imagine um grafo onde:
· Cada nó (vértice) representa um perfil de usuário.
· Cada aresta representa uma conexão ou amizade entre dois perfis.
🧩 Problema: Descobrir quantas conexões existem entre dois perfis (por exemplo, entre você e um amigo de um amigo).
🔄 Solução com algoritmos de busca: Explorar o grafo até encontrar o caminho entre os dois perfis e contar quantas arestas existem no trajeto.
🔄 Tipos principais de busca
1. Busca em profundidade (DFS – Depth-First Search)
· Vai profundamente em um caminho antes de explorar outros.
· Tenta ir o mais longe possível a partir de um vértice, descendo por um ramo antes de voltar.
🧠 Geralmente usa recursão (uma função que chama ela mesma) ou uma pilha.
2. Busca em largura (BFS – Breadth-First Search)
· Explora primeiro todos os vizinhos próximos de um vértice antes de ir mais longe.
· Ideal para encontrar o caminho mais curto entre dois nós.
🧠 Usa uma fila para guardar os próximos vértices a visitar.
🔍 Busca em Profundidade (DFS)
📌 O que é Busca em Profundidade (DFS)?
· É um algoritmo para percorrer grafos, visitando os vértices de forma profunda antes de voltar.
· Começa de um vértice inicial e explora cada caminho até o final, só voltando (backtracking) quando não houver mais vértices não visitados.
🧭 Funcionamento passo a passo:
1. Escolhe um vértice de início (raiz).
2. Marca o vértice como visitado.
· Isso evita que você visite o mesmo vértice mais de uma vez, prevenindo ciclos.
3. Para cada vizinho não visitado, chama recursivamente o algoritmo.
· Ou seja, você explora o caminho o mais fundo possível antes de voltar.
4. Quando não houver mais vértices vizinhos não visitados, retorna (backtrack) para o anterior.
· Isso caracteriza a profundidade: só retrocede quando termina de explorar os caminhos de um vértice.
📘 Definição de Busca em Profundidade segundo Carvalho (2005):
“Busca em profundidade escolhe, entre os vértices marcado com arestas não exploradas, aquele que foi alcançado mais recentemente.”
👉 Exemplo: Se você visitou o vértice A, e ele se conecta com B e C, mas só visitou B, então C ainda está “por explorar”.
👉 Isso significa que o DFS vai “descendo” o caminho até onde der, antes de retornar para o último vértice que ainda tem caminho não percorrido.
🎯 Analogia simples:
Imagine que você está em um labirinto, com várias bifurcações. Você faz o seguinte:
1. Sempre entra na primeira porta que vê.
2. Continua entrando nas portas seguintes, indo cada vez mais fundo.
3. Quando não tiver mais portas (beco sem saída), você volta uma sala e tenta outra porta que ainda não explorou.
4. Sempre volta para a última sala que você entrou (mais recente).
💡 Essa é a ideia de escolher “o vértice alcançado mais recentemente com arestas não exploradas.”
📋 Algoritmo (versão simplificada)
# Função principal que chama o DFS
def Busca(G: grafo, v:verticeInicial): # G é o grafo e u é o vértice inicial
    for cada vértice u em G: # Para cada vértice u no grafo G
        marcar u como não visitado # Marca o vértice como não visitado (inicialização)
    for cada vértice u em G: # Para cada vértice u no grafo G
        if u não visitado: # Se o vértice ainda não foi visitado
            Busca_Prof(u) # Inicia a busca em profundidade a partir desse vértice
# Função recursiva que realiza a busca em profundidade a partir de um vértice
def Busca_Prof(v: vertice):
    marcar v como visitado# Marca o vértice atual como visitado
    para cada vizinho w de v: # Para cada vértice vizinho w do vértice v
        se w não foi visitado: # Se o vizinho w ainda não foi visitado
            Busca_Prof(w) # Chama a busca recursiva a partir de w
🧠 Explicando o que acontece:
· A função Busca começa inicializando todos os vértices como “não visitados”.
· Depois, ela percorre todos os vértices:
· Se encontrar algum que ainda não foi visitado, chama a Busca_Prof para iniciar uma exploração em profundidade a partir dele.
· A função Busca_Prof é recursiva: ela visita o vértice atual, e depois chama a si mesma para cada vizinho ainda não visitado, indo cada vez mais fundo no grafo até não ter mais vizinhos livres.
· Esse algoritmo funciona em grafos conexos.
📌 O que é um grafo conexo?
Um grafo conexo é aquele em que existe pelo menos um caminho entre qualquer par de vértices.
✅ Exemplo de grafo conexo:
A — B — C
| |
D — E
· É possível ir de qualquer vértice a qualquer outro (ex: de A até E passando por D).
❌ Exemplo de grafo não conexo:
A — B 
C — D
· Os vértices do grupo {A, B} não têm nenhum caminho até {C, D}.
· Ou seja, o grafo está dividido em componentes desconexas.
🧩 Por que isso importa no DFS?
· Se o grafo for conexo, basta começar a busca em um único vértice: o DFS alcançará todos os outros vértices.
· Se o grafo não for conexo, o algoritmo precisa fazer várias chamadas ao Busca_Prof, uma para cada componente conexa — por isso o for na função Busca existe.
🔁 Exemplo 1: Funcionamento da execução do algoritmo para o grafo da Figura 3.2, que é conexo.
· Para facilitar a implementação do algoritmo, deve-se usar uma estrutura de adjacência como apresentada abaixo.
🗂️ Estrutura de Adjacência: É montada criando uma lista para cada vértice do grafo indicando quem são seus vizinhos. Cada vértice mantém uma lista de vizinhos.
Exemplo:
Se A é ligado a B e C, então: forma uma lista encadeada A → B → C
· Estrutura de adjacência do grafo (como listas)
A: [B, C]
B: [A, D, E]
C: [A, D]
D: [B, E, C, F]
E: [B, D]
F: [D, G, H]
G: [F, H]
H: [F, G]
Simulação da execução do algoritmo de busca em profundidade:
Busca-Prof(A)
→ Busca-Prof(B)
 →→ Busca-Prof(D)
 →→→ Busca-Prof(E)
←←← Retorna D
 →→→ Busca-Prof(C)
←←← Retorna D
 →→→ Busca-Prof(F)
 →→→→ Busca-Prof(G)
 →→→→→ Busca-Prof(H)
←←←←←←←← Retorna H
←←←←←←← Retorna G
←←←←←← Retorna F
←←←←← Retorna C
←←←← Retorna E
←←← Retorna D
←← Retorna B
← Retorna A
🔍 Etapas da execução:
1. Início da execução:
· Todos os vértices são marcados como não visitados.
2. Começamos por A (pois é o vértice inicial não visitado):
· Chamada: Busca-Prof(A)
· Marca A como visitado.
· Vizinhos de A: [B, C]
· Primeiro vizinho não visitado: B → chama Busca-Prof(B)
3. Busca-Prof(B):
· Marca B como visitado.
· Vizinhos de B: [A, D, E]
· A já foi visitado.
· Próximo vizinho: D → chama Busca-Prof(D)
4. Busca-Prof(D):
· Marca D como visitado.
· Vizinhos de D: [B, E, C, F]
· B já foi visitado.
· Próximo vizinho: E → chama Busca-Prof(E)
5. Busca-Prof(E):
· Marca E como visitado.
· Vizinhos de E: [B, D] → ambos já foram visitados.
· ❌ Não há mais vizinhos → retorna para D
6. De volta ao D:
· Próximo vizinho: C → chama Busca-Prof(C)
7. Busca-Prof(C):
· Marca C como visitado.
· Vizinhos de C: [A, D] → ambos já visitados.
· ❌ Retorna para D
8. De volta ao D:
· Próximo vizinho: F → chama Busca-Prof(F)
9. Busca-Prof(F):
· Marca F como visitado.
· Vizinhos de F: [D, G, H]
· D já foi visitado.
· Próximo: G → chama Busca-Prof(G)
10. Busca-Prof(G):
· Marca G como visitado.
· Vizinhos de G: [F, H]
· F já visitado.
· Próximo: H → chama Busca-Prof(H)
11. Busca-Prof(H):
· Marca H como visitado, chegando ao último vértice do grafo.
· Vizinhos de H: [F, G] → ambos já visitados.
12. A ordem de visita será: A → B → D → E → C → F → G → H 
🌳 Resultado: obtido após a execução do algoritmo é apresentada na Figura 3.5
· A árvore da busca mostra as conexões feitas durante o percurso.
· Somente os caminhos realmente percorridos pelo DFS aparecem na árvore.
🧪 Exemplo 2 – Busca em profundidade
· 🔢 Estrutura de adjacência do grafo (como listas)
0: [1]
1: [0, 2, 3]
2: [1, 4, 5]
3: [1]
4: [2]
5: [2]
Ordem de execução:
Busca-Prof(0)
→ Busca-Prof(1)
→→ Busca-Prof(2)
→→→ Busca-Prof(4)
← Retorna 4
→→→ Busca-Prof(5)
← Retorna 5
← Retorna 2
→ Busca-Prof(3)
← Retorna 3
← Retorna 1
← Retorna 0
🧠 Conclusão:
· A ordem de visita será: 0 → 1 → 2 → 4 → 5 → 3
· Essa ordem depende da ordem dos vizinhos nas listas de adjacência.
· Cada chamada de Busca_Prof(v) visita o vértice v, e chama recursivamente para seus vizinhos ainda não visitados.
📌 Resumo da Análise da Complexidade da Busca em Profundidade (DFS) 
✅ Estrutura utilizada: Lista de Adjacência
· A lista de adjacência é a melhor escolha para implementar a DFS.
· Isso porque a DFS precisa acessar rapidamente os vizinhos de cada vértice (e isso é eficiente com listas de adjacência).
✅ Tempo de execução geral é: 
· Onde:
· n = número de vértices do grafo.
· a = número de arestas do grafo.
· Como é no máximo a soma a + n, dizemos que a busca em profundidade tem um tempo de execução: 
✅ Chamadas do algoritmo
· A função principal chama Busca-Prof para cada vértice ainda não visitado.
· Isso pode gerar até n chamadas recursivas (uma por vértice), pois cada vértice deve ser visitado ao menos uma vez.
✅ Verificação dos vizinhos
· Em cada chamada Busca-Prof(v):
· Todos os vizinhos do vértice v são verificados.
· Isso gera, no total, uma verificação por aresta (cada aresta aparece uma vez em cada extremidade).
· Então, o tempo gasto com essas verificações (Busca-Prof) é proporcional a “a”, ou seja, .
✅ Tempo da função principal (inicialização)
· Antes de começar a busca, o algoritmo:
· Inicializa todos os vértices como "não visitados" → O(n)
· Testa para cada vértice se foi visitado → também O(n)
· Assim, o tempo gasto aqui é O(2n) → que simplificamos como O(n).
✅ Conclusão: Tempo total da DFS
· Soma dos tempos:
· O(n) (inicialização + testes)
· O(a) (visitação das arestas)
· Portanto, a complexidade total da DFS é: 
🔍 Observação:
· Esse tempo é considerado eficiente, principalmente porque:
· Cada vértice e cada aresta são vistos apenas uma vez.
· Isso vale tanto para grafos direcionados quanto não direcionados.
✅ Resumo final:
· DFS é útil para explorar caminhos até o fim e depois voltar.
· Ideal para resolver problemas como:
· Detecção de ciclos
· Geração de árvores
· Conectividade de grafos
· Simples de implementar de forma recursiva.
· Complexidade eficiente com listas de adjacência.
🔍 Busca em Largura (BFS)
✅ O que é Busca em Largura?
· É um algoritmo de busca que visita os vizinhos imediatos de um vértice antes de ir mais fundo.
· Diferente da busca em profundidade, a BFS não é recursiva.
· A busca avança por camadas: primeiro todos os nós do nível 1, depois nível 2, e assim por diante.
✅ Como funciona?
· Utiliza uma fila (FIFO- primeiro a entrar, será o primeiro a sair) para controlar a ordem de visita.
· Começa marcando o vértice inicial como visitado e o coloca na fila.
· Enquanto houver elementos na fila:
· Remove o primeiro da fila.
· Visita seus vizinhos ainda não visitados.
· Marca-os como visitados e os coloca no fim da fila.
✅ Pseudocódigo 
procedimento Busca(G:grafo)
    Para cada vértice v de G:             # Passa por todos os vértices do grafo
        Marcar v como não visitado        # Inicializa todos os vértices como "não visitados"
    Para cada vértice v de G:             # Para cada vértice
        Se v não foi visitado:            # Se o vértice ainda não foi visitado
            Busca-Largura(v)              # Inicia a busca em largura a partir dele
procedimento Busca-Largura(v:vértice)
    Inicializar F                         # Cria uma fila vazia (estrutura FIFO)
    Marcar v como visitado                # Marca o vértice inicial como visitado
    Colocar v no final de F               # Insere o vértice inicial na fila
    Enquanto F não vazio:                 #Enquanto houver elementos na fila
        u := primeiro elemento de F # Pega o primeiro elemento da fila (próximo a ser processado)
        Retirar u de F                    # Remove u da fila
        Para cada vértice w adjacente a u: # Verifica todos os vizinhos (adjacentes) de u
            Se w não foi visitado:         # Se o vizinho ainda não foi visitado
                Marcar w como visitado    # Marca o vizinho como visitado
                Colocar w no final de F # Adiciona o vizinho no final da fila para ser processado depois
✅ Exemplo 1 – Busca em Largura
Estrutura de adjacência:
· A: [B, C]
· B: [A, D, E]
· C: [A, D]
· D: [B, E, C, F]
· E: [B, D]
· F: [D, G, H]
· G: [F, H]
· H: [F, G]
🧪 Simulação de Execução passo a passo com fila:
A – Visita A e coloca A no final da Fila F
  C B – Visita C e coloca C no final da Fila F
    B E D – Visita B e coloca B no final da Fila F
      E D – Visita E e coloca E no final da Fila F
        D F – Visita D e coloca D no final da Fila F
          F G H – Visita F e coloca F no final da Fila F
            G H – Visita G e coloca G no final da Fila F
              H – Visita H e coloca H no final da Fila F
✅ Ordem de visita: A, C, B, E, D, F, G, H
✅ Exemplo 2 – Busca em Largura 
Estrutura de adjacência: 
· 0: [2, 3, 4] 
· 1: [2, 5]
· 2: [0, 1, 4]
· 3: [0, 4, 5]
· 4: [0, 3, 5]
· 5: [1, 3, 4]
🧪 Execução passo a passo com fila:
0 – Visita o ‘0’, coloca ele no final da fila → Fila: 0
 2, 3, 4 – Visita o ‘2’ coloca ele no final da fila → Fila: 0, 2, 
 3, 4 – Visita o ‘3’, coloca ele no final da fila → Fila: 0, 2, 3
 4, 5 – Visita o ‘4’, coloca ele no final da fila → Fila: 0, 2, 3, 4
 5 – Visita o ‘5’, coloca ele no final da fila → Fila: 0, 2, 3, 4, 5
 1 – Visita o ‘1’, coloca ele no final da fila → Fila: 0, 2, 3, 4, 5, 1
✅ Ordem de visita: 0, 2, 3, 4, 1, 5
✅ Complexidade da busca em largura
· Tempo de execução: A busca em largura (BFS) percorre:
· Todos os vértices (n) do grafo.
· E todas as arestas (a) do grafo.
🔹 Por isso, o tempo total de execução é: ou 
Essa é a mesma complexidade da busca em profundidade (DFS), pois ambos os algoritmos precisam percorrer todos os vértices e todas as conexões para explorar completamente o grafo.
· Uso de memória (espaço): Aqui está a grande diferença entre BFS e DFS:
🔵 BFS (Busca em largura):
· Usa uma fila para armazenar todos os vizinhos imediatos de todos os nós sendo explorados.
· Em cada nível, todos os filhos de todos os nós daquele nível são enfileirados antes de passar para o próximo nível.
🔸 Se o grafo for uma árvore binária, por exemplo, em nível k, você pode ter até nós.
🔺 Isso faz com que, em árvores muito ramificadas e largas ou grafos densos e largos, o número de elementos na fila possa crescer muito rapidamente — até de forma exponencial.
⚠️Por isso, usa mais memória que a DFS, que só guarda um caminho por vez na pilha.
⚠️ Memória ocupada: pode crescer exponencialmente no pior caso.
🔵 DFS (Busca em profundidade):
· Usa uma pilha (pode ser implícita, via recursão).
· Em qualquer momento, a pilha guarda apenas um caminho da raiz até um nó folha.
· Isso significa que, no pior caso, a pilha terá no máximo n elementos (um por nível da árvore).
🔸 Memória ocupada: proporcional a O(n)
✔️ Mais eficiente em espaço.
📌 Exemplo simplificado:
Imagine uma árvore binária com 10 níveis (não balanceada):
· No nível 0: 1 nó
· No nível 1: 2 nós
· No nível 2: 4 nós
· ...
· No nível 9: até 512 nós
🔹 Em DFS, você só armazena o caminho da raiz até a folha (10 nós).
🔹 Em BFS, se você estiver no nível 8, a fila pode conter todos os 256 nós do próximo nível (ou mais), ocupando muito mais memória.
✅ Resumo em tópicos:
	Critério
	DFS (Busca em Profundidade)
	BFS (Busca em Largura)
	🕒 Tempo de execução
	 – visita cada vertice e aresta uma única vez
	 – visita todos os vértices (n) e arestas (a)
	🧠 Uso de memória
	 – pilha guarda um caminho por vez (profundidade)
	Exponencial: Pode crescer muito – a fila guarda muitos nós por nível (largura)
	🧰 Estrutura usada
	Pilha (implícita via recursão) ou recursão 
	Fila
	📌 Forma de exploração
	Explora um caminho profundo antes de voltar
	Explora todos os vizinhos (nível) antes de descer para o próximo
	🌲 Crescimento da estrutura
	Cresce com a profundidade do grafo/árvore
	Cresce com a largura do grafo/árvore
	⚠️ Pior caso em memória
	Usa menos memória – máximo n elementos na pilha
	Pode usar muito mais memória – fila pode crescer de forma exponencial 
	🔄 Recursividade
	Pode ser implementada de forma recursiva
	Necessariamente iterativa (com fila)
	✅ Mais indicado para...
	Encontrar caminhos profundos, detectar ciclos, topologia, backtracking
	Encontrar caminho mais curto em grafos não ponderados
Módulo 4. Descrever o problema do custo mínimo sobre um grafo ponderado
✅ Caminhos em Grafos
📌 O que é um caminho?
· Um caminho em um grafo é uma sequência de vértices onde cada vértice está ligado ao próximo por uma aresta.
· Exemplo: Se temos os vértices a → b → c → d, isso é um caminho se todas as arestas (a,b), (b,c), (c,d) existirem.
🔄 Tipos de caminhos
1. Caminho simples (ou elementar):
· Não repete nenhum vértice (exceto talvez o primeiro e o último se for um ciclo).
· Exemplo: 
· [0, 2, 7, 3, 6] é um caminho simples — todos os vértices são diferentes.
2. Trajeto: É um trajeto fechado, ou seja:
· Começa e termina no mesmo vértice
· Nenhuma aresta se repete
· Pode repetir vértices, exceto o primeiro/último
· Exemplo:
· [0, 2, 7, 3, 6, 2, 6, 0] é um trajeto, porque não repete arestas, mas repete vértices (como "0", "2" e "6").
· Observação: A sequência acima é um trajeto, mas não um caminho simples.
🔁 O que é um circuito?
· Um circuito é um caminho onde o primeiro vértice é igual ao último, e todas as arestas são diferentes.
· Pode ter vértices repetidos, mas arestas não.
Exemplo de circuito: [0, 2, 7, 3, 6, 0]
🔁 O que é um ciclo?
· Um ciclo é um circuito sem vértices repetidos, exceto o primeiro e o último (que são iguais para fechar o ciclo).
· Exemplo: 
· [0, 2, 7, 3, 6, 0] também é um ciclo porque:
· Começa e termina em “0”. 
· Nenhum vértice intermediário se repete.
· As arestas são distintas.
· Observação: Um circuito pode ser um ciclo, mas nem todo circuito é um ciclo
📏 O que é distância?
· A distância entre dois vértices é o número de arestas do menor caminho entre eles.
· Exemplo: 
· A menor distância entre a e d é 2.
· Caminho possível: a → c → d
· Total de arestas: 2
🚀 Caminho Mínimo e Algoritmo de Dijkstra
✅ O que é o caminho mínimo?
· É o melhor caminho entre dois nós de um grafo. 
· Esse “melhor” pode ser:
· ✅ Menor custo
· ✅ Menor distância
· ✅ Menor tempo de viagem
Exemplo: Qual o caminho mínimo para chegar ao vértice 5 a partir da origem 1?
Caminho mínimo: [1, 2, 5] ou [1, 4, 5]
📦 Entrada e Saída do Algoritmo:
· Entrada: Grafo ponderado com pesos não negativos e um nó de origem.
· Saída:
· O caminho mais curto do nó de origem para todos os outros.
· Ou os próprios caminhos mínimos.
📌 Exemplo de uso:
· Encontrar o caminho mais curto entre duas cidades.
· Achar a rota mais rápida na internet.
· Calcular a menor distância entre pontos em um mapa.
🧠 Algoritmo de Dijkstra (passo a passo)
🎯 Objetivo do Algoritmo de Dijkstra: Descobrir o caminho de menor custo entre um nó de origem e os demais nós de um grafo.
🧩 Como funciona?
1. Comece atribuindo:
· 0 de custo para o nó de origem.
· ∞ (infinito) para os demais nós.
2. Crie um conjunto com todos os nós ainda não resolvidos.
3. Enquanto houver nós abertos (não resolvidos):
1. Escolha o nó com menor custo atual.
1. Para cada vizinho dele:
· Some o custo atual com o peso da aresta.
· Se esse novo custo for menor que o anterior, atualize-o e registre o nó atual como o precedente.
4. Repita até que todos os nós tenham sido processados.
💻 Pseudocódigo:
# Entrada: Grafo conectado com pesos nos arcos (representado pela matriz w), nós 'a' (origem) e 'z' (destino)
# Saída: L(z) - comprimento do menor caminho entre os nós 'a' e 'z'printf("O endereco de A é: %p\n", (void*)&A); // Saída: O endereco de A é: 1000
    printf("O valor de A é: %d\n", A); // Saída: O valor de A é: 1003
    // Exibe o endereço armazenado em “PONT” e o valor que “PONT” aponta
    printf("PONT armazena o endereco de A: %p\n", (void*)PONT); // Saída: PONT armazena o endereco de A: 1000
    printf("O valor apontado por PONT é: %d\n", *PONT); //Saída: O valor apontado por PONT é: 1003
    return 0;
}
· Imagine que a variável “PONT” está na posição “1000” da memória e seu conteúdo é “1003”.
· A posição “1003” é onde está armazenada a variável “A”.
· Portanto, “PONT” aponta para “A”, pois guarda o endereço de memória onde “A” está.
🔹 Vantagens do Uso de Ponteiros
1. Modificar valores dentro de funções: Permite passagem por referência, alterando diretamente variáveis externas à função.
2. Acesso indireto à memória: Aumenta a eficiência no acesso a estruturas como arrays e strings.
3. Manipulação eficiente de arrays e strings: Facilita operações com aritmética de ponteiros, sem precisar de índices.
4. Alocar e desalocar memória dinamicamente, permitindo otimização do uso de recursos, usado com malloc, calloc, realloc, free, permite usar memória sob demanda.
5. Passar funções como parâmetros para outras funções, promovendo modularidade e reutilização.
7. Economia de memória: Ao passar ponteiros em vez de estruturas grandes, economiza-se memória e melhora a performance (evita cópias desnecessárias).
8. Permitir compartilhamento de dados entre diferentes partes do programa: Várias funções podem acessar e modificar os mesmos dados usando ponteiros, promovendo integração.
9. Implementação de estruturas genéricas e flexíveis: Ponteiros permitem a criação de bibliotecas e funções que operam sobre diferentes tipos de dados.
🔹 Declaração de Ponteiros (em C)
· A sintaxe é:
tipo *nome_do_ponteiro;
· Pode-se declarar vários ponteiros do mesmo tipo:
tipo *ponteiro1, *ponteiro2;
🔹 Tamanho dos Tipos na Memória
· Dependendo da arquitetura, cada tipo ocupa uma quantidade de bytes:
	Tipo
	Tamanho (exemplo)
	char
	1 byte
	int
	4 bytes
	float
	4 bytes
	short
	2 bytes
	long
	4 bytes
	double
	8 bytes
🔹 Exemplo em C:
int *p;
float *ptr1, *ptr2;
🔎 Explicação: 
· int *p; → Declara p como ponteiro para inteiro (int). Este ponteiro aponta para o primeiro endereço de um bloco de quatro bytes.
· *: → é um operador que indica que *p é um ponteiro;
· float *ptr1, *ptr2; → Declara dois ponteiros (ptr1 e ptr2) do tipo float, que apontam para o primeiro endereço da posição de memória ocupada por cada variável.
✅ Conclusão sobre ponteiros
· Ponteiros são fundamentais em linguagens como C, pois dão controle direto da memória.
· Para quem estuda C/C++, entender ponteiros é essencial para:
· Criar estruturas eficientes;
· Manipular diretamente a memória;
· Entender como variáveis funcionam por baixo dos panos.
Exercício: Analise o trecho de código abaixo e selecione entre as alternativas o que será exibido após a execução.
var
    a, b, d : inteiro;
    v[4] : inteiro;
inicio
       aL[a] = 0  # Define o custo do caminho mínimo de 'a' para ele mesmo como 0
for x in N:  # Para cada nó x no conjunto de nós N (todos os nós do grafo)
    if x != a:
        L[x] = float('inf')  # Inicializa o custo de todos os outros nós como infinito
T = N.copy()  # T é o conjunto de nós ainda não processados
while z in T:  # Enquanto o destino 'z' ainda não tiver sido processado
    v = nó_em_T_com_menor_L  # Escolhe o nó v em T com o menor valor de L(v)
    T.remove(v)  # Remove v do conjunto T (marca como processado)
    for x in vizinhos_de_v:  # Para cada vizinho x de v que ainda está em T
        if x in T:
            # Atualiza L(x) com o menor valor entre o atual e o novo caminho passando por v
            L[x] = min(L[x], L[v] + w[v][x])
🧠 Explicação dos Componentes:
· L[x]: dicionário com as estimativas do menor custo do nó de origem a até x.
· w[v][x]: representa o peso da aresta entre os nós v e x.
· T: conjunto dos nós ainda não processados.
· nó_em_T_com_menor_L: função (ou laço) que encontra o nó com o menor valor de L dentro de T.
📌 Exemplo 1: Utilizando o algoritmo de Dijkstra, vamos calcular o menor caminho entre os vértices 1 e 6 do grafo apresentado na Figura 4.3, que apresenta os vértices, as arestas e seus respectivos pesos. 
⚙ Suponha que queremos ir do nó 1 ao nó 6: 
1. Inicialmente, vamos atribuir valor zero à estimativa do custo mínimo do nó 1 (a origem da busca) e infinito às demais estimativas (Figura 4.4)
1. Começamos no nó 1:
· Verificamos as arestas saindo dele: (1 → 2), (1 → 3), (1 → 4).
· A menor aresta é, ou seja de menor peso é (1 → 4) que tem peso 2, então o caminho inicial é: [1, 4]
2. Verificamos os vizinhos do 4:
· A menor aresta agora é (4 → 5), que tem custo 1, então temos: [1, 4, 5]
3. Por fim, do 5 vamos ao 6 pela aresta (5 → 6), que tem peso 2, chegando a: [1, 4, 5, 6]
🧮 Resultado final:
· Caminho mínimo entre 1 e 6: [1, 4, 5, 6]
· Custo total do caminho: 5 (segundo a figura citada)
✅ Recapitulando: Diferenças entre Caminho, Custo e Dijkstra
	Conceito
	Explicação simplificada
	Caminho
	Sequência de nós ligados por arestas
	Caminho mínimo
	O caminho com menor custo entre dois nós
	Custo
	Soma dos pesos (tempo, distância, etc.) das arestas do caminho
	Dijkstra
	Algoritmo que encontra os menores caminhos em grafos ponderados
🧭 Problema do Caixeiro-Viajante (Travelling Salesman Problem – TSP)
Objetivo do Problema do Caixeiro-Viajante: Encontrar o caminho de custo mínimo para visitar todas as cidades uma única vez e retornar ao ponto de partida. 
Tipo de problema: 
· NP-Completo (muito difícil de resolver quando o número de cidades cresce). 
· Ou seja, não há uma solução rápida para todos os casos.
· Soluções exatas exigem tempo exponencial ou fatorial com base no número de cidades.
Aplicações práticas:
· Rotas de entrega de encomendas.
· Planejamento de viagens.
· Leitura de medidores (água, luz).
· Coleta de objetos (como lixo ou correspondências).
⚙️ Algoritmos para resolver o problema:
💪 1. Algoritmo da Força Bruta
Como funciona:
1. Gera todas as rotas possíveis entre as cidades.
2. Calcula o custo total de cada rota.
3. Escolhe a rota mais barata.
✔️ Vantagem:
· Garante a melhor solução (ótima).
❌ Desvantagem:
· Muito lento para muitas cidades 
(crescimento fatorial: 5 cidades → 5! = 120 rotas; 
10 cidades → 10! = 3.628.800 rotas).
🏁 Resultado: 
· Caminho: A → E → C → B → D → A.
· Custo total: R$676.
· ✅ Melhor caminho possível (ótimo).
🤝 2. Algoritmo do Vizinho Mais Próximo
Como funciona:	
1. Escolhe uma cidade inicial (ex: A).
2. Vai para a cidade mais próxima (menor custo).
3. Repete o processo com a próxima cidade, sem repetir nenhuma.
4. Quando todas forem visitadas, retorna à cidade inicial.
✔️ Vantagem:
· Muito mais rápido.
· Fácil de implementar.
❌ Desvantagem:
· Nem sempre encontra o melhor caminho. 
🏁 Resultado no exemplo da imagem:
· Caminho: A → C → E → D → B → A.
· Custo total: R$773.
· ❌ Mais caro que o caminho da força bruta.
📌 Comparação entre os algoritmos:
· Força Bruta: Garante a melhor rota, mas só funciona bem com poucas cidades.
· Vizinho Mais Próximo: É rápido e prático, ideal para problemas maiores, mas pode não ser o mais econômico.
· A escolha do algoritmo depende do tamanho do problema e da necessidade de precisão vs. velocidade.
image4.jpeg
image94.png
image95.png
image96.png
image97.png
image98.png
image99.png
image100.png
image101.png
image102.png
image103.png
image5.png
image104.png
image105.png
image106.png
image107.png
image108.png
image109.png
image110.png
image111.png
image112.png
image113.png
image6.png
image114.png
image115.png
image116.png
image117.png
image118.png
image119.png
image120.png
image121.png
image7.png
image8.png
image9.png
image10.png
image11.png
image12.png
image13.png
image14.png
image15.png
image16.png
image17.png
image18.png
image19.png
image20.png
image21.png
image22.png
image23.png
image24.png
image25.png
image26.png
image27.png
image28.png
image29.png
image30.png
image31.png
image32.png
image33.png
image34.png
image35.png
image36.png
image37.png
image38.png
image39.png
image40.png
image41.png
image42.png
image43.png
image44.png
image45.png
image46.png
image47.png
image48.png
image49.png
image50.png
image51.png
image52.png
image53.png
image54.png
image55.png
image56.png
image57.png
image58.png
image59.png
image60.png
image61.png
image62.png
image63.png
image1.jpeg
image64.png
image65.png
image66.png
image67.png
image68.png
image69.png
image70.png
image71.png
image72.png
image73.png
image2.jpeg
image74.png
image75.png
image76.png
image77.png
image78.png
image79.png
image80.png
image81.png
image82.png
image83.png
image3.jpeg
image84.png
image85.png
image86.png
image87.png
image88.png
image89.png
image90.png
image91.png
image92.png
image93.pngda Análise de Algoritmos
· Determinar qual algoritmo é mais eficiente para resolver um problema.
· A eficiência é medida principalmente em tempo e espaço usados para resolver entradas de tamanho n.
🧮 Como medir a eficiência de um algoritmo?
· O cálculo é feito contando o número de passos básicos executados conforme o tamanho da entrada n.
· Passos básicos incluem:
1. Operações aritméticas
2. Comparações
3. Atribuições
4. Resolver um ponteiro ou referência
5. Acesso a posições em listas/arranjos
6. Chamadas e retornos de funções e métodos
💡 Exemplo: Um algoritmo de busca pode executar:
i = 0; achou = falso           // Passo básico 1
repita
  i = i + 1                    // Passo básico 2
  se tab[i] = chave             // Passo básico 3
     então achou = V        // Passo básico 4
até achou ou i = n         // Passo básico 5
se achou                       // Passo básico 6
    então pos = i                    // Passo básico 7
retorna (achou, pos)          // Passo básico 8
⏱️ Tipos de Complexidade
1. Espacial: representa o espaço de memória usado para executar o algoritmo, ou seja, quanto de memória o algoritmo usa.
2. Temporal: quanto tempo leva para executar (mais importante em geral e a mais usada para estudos de algoritmos).
· Pode ser medido pelo tempo real necessário à execução do algoritmo ou pelo número de instruções necessárias à execução.
📈 Análise Assintótica
· Foca em entradas muito grandes .
· Despreza constantes, ou seja, cada operação (passo básico) leva o mesmo tempo constante. Além disso, despreza termos de menor grau, focando apenas na taxa de crescimento.
· Representada por uma função , que mostra como o número de passos cresce com .
· A eficiência assintótica descreve a eficiência de um algoritmo quando torna-se grande.
📊 Exemplo Comparativo: e para 
🔢 Passo 1: Avaliar as funções para valores pequenos de : Vamos ver quanto vale cada função para alguns valores pequenos de :
	
	
	
	
	0
	4
	0
	
	1
	5
	1
	
	2
	6
	4
	→ é maior
	3
	7
	9
	
	4
	8
	16
	
	5
	9
	25
	→ cresce mais rápido
🧠 Interpretação:
· Para , a função realiza mais operações que → ou seja, parece mais lenta para n pequeno.
· A partir de , começa a crescer mais rápido que 
· Para , por exemplo:
· 
· → muito maior!
📈 Passo 2: Pensar a longo prazo (assintoticamente)
Agora, pense que pode chegar a 1000, 1 milhão...
· cresce de forma linear → só soma 4 ao valor de .
· cresce de forma quadrática → multiplica por ele mesmo.
👉 Ou seja, cresce muito mais rápido do que conforme aumenta.
⚖️ Passo 3: Conclusão da comparação assintótica
Mesmo que pareça mais eficiente nos casos pequenos (como ou ), isso não importa na análise assintótica.
· Na análise assintótica, só importa o comportamento para grande.
· Portanto, é mais eficiente que assintoticamente, pois sua taxa de crescimento é menor.
📌 Conceito-chave: Ordem de crescimento
· → é da ordem de n, ou seja, O(n).
· → é da ordem de n², ou seja, O(n²).
👉 Como para valores grandes, dizemos que f(n) é assintoticamente mais eficiente.
🧪 Analogia simples:
Imagine duas pessoas subindo uma escada:
· A primeira sobe 1 degrau por segundo.
· A segunda sobe 1, depois 2, depois 4, depois 8 degraus por segundo...
Nos primeiros segundos, a diferença é pequena, mas com o tempo, a segunda pessoa dispara. O mesmo ocorre com funções com crescimento rápido.
🧮 Ordens de Crescimento (da mais eficiente para a menos eficiente)
	Ordem
	Exemplo de Complexidade
	Constante
	
	Logarítmica
	
	Linear
	
	Log Linear 
	
	Quadrática
	
	Cúbica
	
	Exponencial
	
	Fatorial
	
· Considerando a tabela acima, as funções são classificadas em "ordens" e todas as funções de uma mesma ordem são "equivalentes". 
· Então, por exemplo, , ,  são equivalentes. Todas as funções possuem a ordem .
✅ Conclusão
· A análise de algoritmos é essencial para escolher soluções que escalem bem com o tamanho dos dados.
· Algoritmos com menor ordem de crescimento assintótica são preferíveis para entradas grandes.
· A eficiência depende mais do algoritmo escolhido do que da velocidade da máquina.
🎯 Notação O (Big Oh)
· Objetivo da análise de algoritmos:
· Comparar funções que representam o número de passos de um algoritmo.
· Determinar qual algoritmo é mais eficiente para resolver um problema.
· Pior caso:
· Todo algoritmo tem entradas que o fazem se comportar da pior maneira possível (executando mais passos).
· A análise do pior caso é comum e importante.
🔹 Exemplo de Análise de Pior Caso
Situação: Buscar um número em uma lista.
· Se a lista tem 1000 números e o número procurado é o último da lista (ou nem está nela), o programa fará 1000 comparações.
· Isso é chamado de pior caso.
· A análise do pior caso ajuda a prever o desempenho de um algoritmo em situações mais exigentes.
Exemplo: O algoritmo Quicksort ilustra bem isso: embora eficiente na média O(n log n), ele pode ter desempenho ruim em certos casos (no pior caso é O(n²)), como dados quase ordenados — o que torna a análise do pior caso essencial para entender suas limitações. 
Quando o pior caso ocorre?
· Quando os dados estão quase ordenados ou totalmente ordenados, e o pivô escolhido sempre divide mal (por exemplo, é sempre o menor ou o maior elemento).
· Isso faz com que o particionamento seja muito desequilibrado, e o número de comparações aumente bastante.
· O que é a Notação O?
· Representa o limite superior assintótico (g(n)) de uma função. 
· Indica como o tempo de execução ou uso de recursos cresce com o tamanho da entrada (n) no pior caso.
· A notação O é a forma matemática de se prever o pior caso para cada algoritmo para determinada solução de um problema.
· Definição matemática (simplificada):
· Dadas duas funções e , dizemos que:
 se existe uma constante  e um  tal que  para todo 
· Ou seja, a função  "domina" em crescimento quando fica grande.
📘 Exemplo 1: Provar que = ?
🧩 Passo 1: Relembrar a definição de notação O
Dizemos que   se existe uma constante positiva c e um número ​ tal que:
 para todo 
🧩 Passo 2: Identificar as funções
· 
· 
Queremos provar que existe uma constante e um ​ tal que:
 para todo 
🧩 Passo 3: Manipular a desigualdade
Vamos isolar :
Agora queremos saber se existe um valor de que satisfaça essa desigualdade para todo ​.
🧩 Passo 4: Escolher um 
A função ​ diminui à medida que aumenta. Então, se escolhermos um valor para ​, podemos calcular o valor máximo de ​​ a partir dali. 
Vamos tentar :
Então, para todo , temos:
🧩 Passo 5: Concluir
Achamos:
· 
· 
Logo, satisfazemos a definição de notação O: para todo 
 🎯 Conclusão final: Sim, = , pois cresce mais rápido que , e a função está limitada por uma constante vezes a partir de algum ponto.
Podemos ver que, à medida que n cresce, a função g(n) = n³ cresce muito mais rápido do que f(n) = 4n². Isso demonstra que:
f(n) = 4n² é O(n³), pois existe um ponto a partir do qual n³ sempre será maior que 4n², multiplicado por uma constante c.
📘 Exemplo 2: Provar que: 
Análise: A desigualdade diz que n deve ser menor ou igual a uma constante c, para todo valor grande de n.
Mas isso não é possível, porque:
· n cresce indefinidamente.
· c é uma constante fixa.
· Logo, sempre existirá um valor de n maior que qualquer constante c.
❌ Portanto: não existe um valor de c que satisfaça a desigualdade para todo n grande.
· Conclusão: Ou seja, n² não é O(n) porque n² cresce mais rápido que n. A função n não é uma cota superior para n².
O gráfico mostra que a função cresce muito mais rapidamente do que conforme aumenta. Isso confirma visualmente que não existe uma constante tal que para todo ​. Portanto, — ou seja, não está limitado por uma constante vezes n.
📘 Exemplo 3: Provar que: 
Dividindo termo a termo:
🔶 Análise para 
Então: 
· Conclusão: 
Ou seja, a função está assintoticamente limitada superiormente por , conforme imagem abaixo.
📘 Exemplo 3: Provar que: 
 
· Manipular a função f(n) 
· Comparar com 
· Escolher constantes 
· ❌Conclusão: A funçãonão é ou seja, não está assintoticamente limitada superiormente por , porque cresce muito mais rapidamente que a partir de . 
· Portanto, a função não é uma cota superior assintótica para .
💡 Resumo final
· A Notação O descreve o limite superior do crescimento de uma função, ajudando a prever a eficiência dos algoritmos.
· Para provar que , é necessário encontrar um número constante e um valor ​ a partir do qual .
· Essa análise é crucial para entender como os algoritmos se comportam em larga escala.
 Cota Superior de Problemas
· Definição: A cota superior (ou limite superior, do inglês upper bound) representa o máximo de complexidade conhecida que um algoritmo pode ter para resolver um problema.
· Em outras palavras: A cota superior de um problema é uma forma de dizer:
· "Sabemos que este problema pode ser resolvido em, no máximo, esse tempo."
· Em notação assintótica, usamos o O(grande) para expressar essa ideia.
🧮 Exemplo 1: Multiplicação de Matrizes 
· Problema: Existe um algoritmo trivial que multiplica duas matrizes com complexidade .
· Isso significa que: o tempo para resolver o problema não ultrapassa O(n³).
· Conclusão: a cota superior do problema de multiplicação de matrizes é O(n³) até o momento.
· Mas por que dizemos "até o momento"? Porque talvez alguém descubra um algoritmo mais rápido no futuro.
· Se um algoritmo mais eficiente for descoberto, a cota superior pode mudar
· Assim, a nova complexidade se torna o novo limite superior.
· Exemplo:
· Problemas de ordenação (como o Merge Sort, Heap Sort, Quick Sort, no caso médio) atualmente têm cota superior O(n log n).
· Se alguém descobrir um algoritmo que ordena em O(n), a nova cota superior passaria a ser O(n).
🎯 Objetivo Geral da Análise
· Comparar algoritmos matematicamente para encontrar o mais eficiente para resolver um problema.
· Isso ajuda a estabelecer a melhor cota superior possível com base nos algoritmos existentes.
Módulo 4. Empregar a análise da complexidade dos algoritmos
· A análise prática de algoritmos serve para medir o desempenho de diferentes algoritmos que resolvem um mesmo problema.
· Essa medição é feita usando a notação Big O, que mostra o quanto o tempo de execução ou o uso de memória cresce conforme o tamanho da entrada aumenta.
· Depois de calcular o Big O de cada algoritmo, escolhemos o que tem o menor Big O, ou seja, o mais eficiente segundo a ordem de crescimento.
🔹 Premissas para análise assintótica
1. Funções polinomiais e Big-O:
· Se uma função é um polinômio de grau , então sua complexidade é .
· Desprezam-se termos de menor ordem e constantes.
· Exemplo: será transformado em O(n³) (termo dominante é n³).
2. Usar a menor classe de funções possível:
· Simplifique a função para a menor complexidade que a representa.
· Por exemplo é incorreto dizer que é . O correto é — pois a constante 2 é desprezada.
3. Usar a expressão mais simples possível:
· Também se aplica a somas com constantes.
· Exemplo: → O(n) (descarta-se o 5 e o 3).
4. Comparando dois algoritmos:
· Comparando dois algoritmos com tempo de execução: e .
· → Algoritmo com tempo linear, mas um coeficiente gigantesco (10¹⁰⁰).
· → Algoritmo com crescimento mais rápido (n log n), mas coeficiente pequeno (10).
· Teoricamente, pela analise assintótica, é melhor que, pois:
· (ignoramos constantes) → é 
· (ignoramos constantes)→ é 
· Mas na prática: o primeiro algoritmo tem uma constante tão grande que ele só se torna mais rápido que o segundo para valores de gigantescos, ou seja, só quando for absurdamente grande, que o crescimento de irá ultrapassa a diferença causada por .
· Conclusão: A análise assintótica diz que é mais eficiente que , porque cresce mais devagar que . Mas essa vantagem só aparece quando é muitíssimo grande, o que não faz sentido no mundo real — pois é maior que o número de átomos no universo! Portanto, na prática, o algoritmo com menor constante pode ser melhor, mesmo que cresça mais rápido assintoticamente.
Aqui está o gráfico comparando:
· (linha azul): cresce linearmente, mas com uma constante imensa.
· (linha verde tracejada): cresce mais rápido com o tempo, embora tenha constante pequena.
🔍 Observe: o gráfico mostra que mesmo quando vai até 10 bilhões, ainda está muito acima de . Isso confirma que:
Na prática, o algoritmo com menor constante pode ser mais eficiente, mesmo que cresça mais rápido assintoticamente.
Somente para valores absurdamente grandes de (muito além da escala do gráfico), ultrapassaria .
🔹 Princípios básicos de complexidade
1. A complexidade do algoritmo mede quantos passos básicos ele executa para produzir um resultado.
2. Um algoritmo pode conter:
· Componentes sempre executadas.
· Componentes condicionais, executadas dependendo da entrada.
🔹 Componentes Conjuntivas (sempre executadas)
· Definição: Uma componente é conjuntiva quando é sempre executada em qualquer execução do algoritmo.
· Cálculo da complexidade total: Se duas componentes são conjuntivas, deve ser considerada a soma da cota superior entre os dois componentes conforme a fórmula:
· Regra prática: Como estamos lidando com o pior caso (Big-O), deve ser a soma do O das duas componentes, ou seja, somam-se os tempos de execução das componentes.
🔹 Componentes Disjuntivas (executadas dependendo de uma condição)
· Definição: Uma componente de um algoritmo é dita disjuntiva quando são executadas dependendo de uma condição. 
· Cálculo da complexidade total: Se duas componentes são disjuntivas, deve ser considerada a maior cota superior entre os dois componentes conforme a fórmula:
· Regra prática: Considera-se a mais custosa entre as duas (pior caso entre as alternativas).
🔹 Princípio da Absorção
· Se uma função é menor assintoticamente que outra , então:
· 
· Ou seja, é "absorvida" por .
· Exemplo: Seja, duas componentes disjuntivas e ,
1. Funções disjuntivas: 
2. Soma: Geram a soma de componentes
3. Resultado final: Pelo princípio da absorção, a complexidade final será , ou seja, (pois domina 1 assintoticamente)
✅ Resumo final das regras práticas:
📊 Quadro Comparativo: Análise de Complexidade Assintótica
	Conceito
	Definição
	Regra Prática
	Exemplo Simplificado
	Desprezar termos e constantes
	Em polinômios, considerar apenas o termo de maior grau
	Ignore constantes e termos de menor ordem
	 
	Menor classe possível
	Representar a função pela menor classe de crescimento
	Não incluir constantes desnecessárias na notação
	 
	Expressão mais simples
	Usar a forma mais reduzida da função
	Despreze somas com constantes
	 → O(n)
	Componentes conjuntivas
	Partes sempre executadas do algoritmo
	Soma das complexidades: 
	Sempre considera ambos os tempos
	Componentes disjuntivas
	Partes executadas dependendo de uma condição
	Máximo entre as complexidades:
 
	Considera o pior caso entre as duas
	Princípio da absorção
	A função com maior crescimento domina a soma
	
se crescer menos que 
	
	Comparação prática
	Nem sempre o menor Big-O é o melhor na prática
	Na prática, o algoritmo com menor constante pode ser mais eficiente, mesmo que cresça mais rápido assintoticamente.
	 vs 
Complexidades pessimistas de estruturas algorítmicas
📌 1. Regras Gerais da Notação O (Tabeladas)
Estas regras ajudam a simplificar e combinar expressões de complexidade:
	Regra
	Interpretação
	
	Qualquer função é O dela mesma.
	
	Constantes não alteram a ordem de crescimento.
	
	Soma de funções iguais mantém a mesma ordem.
	
	Aninhamento de O é redundante.
	
	Soma vira a maior das duas funções.
	
	Produto das ordens vira multiplicação.
	
	Função vezes ordem dá ordem do produto.
A seguir, serão analisadas as complexidades para algumas operações.
🟡 Atribuição: O tempo de execução é o tempo do comando da atribuição. 
➤ Regra:
· Uma atribuição isolada tem complexidade .
· Se a operação de atribuição for feita dentro de uma estrutura de repetição, multiplica-se pelo número de vezes que é executada
✅ Exemplo 1:
a = a * i O(1)
· Executa 1 vez → O(1)
✅ Exemplo 2:
VetA[i] = VetI[i]  // para i de 0 até (n-1) O(n)· Executa n vezes → O(n)
🟡 Repetições (Laços)
➤ Regra: Complexidade = número de repetições × instrução 
✅ Exemplo 1:
para i de 1 até n: O(n)
    a = a * i O(1)
· Laço → 
· Atribuição → 
· Total → 
✅ Exemplo 2:
para i de 1 até n: O(n)
    a = a * i O(1)
    c = c + a O(1)
· Cada comando é , laço é 
🟡 Repetições Aninhadas
➤ Regra:
· Analisa-se de dentro para fora
· Multiplica-se todas as complexidades
✅ Exemplo 1: (duplo laço)
para i de 1 até n:
    para j de 0 até (n-1):
        a = a*(i+j)
· externo × interno × 
✅ Exemplo 2: (triplo laço)
para i de 1 até n:O(n)
    para j de 0 até O(n-1):
        para k de 0 até O(n-2):
            a = a*(i+j)
· 
💡 Observação: e são simplificados para , pois constantes são desprezadas.
🟡 Condicionais (if/else)
➤ Regra: 
· Complexidade = tempo do teste + maior entre os blocos do então e senão
Fórmula:
✅ Exemplo 1:
se (a max
(6)         então max = tabela[i]
(7)     se tabela[i] max
(6)         então max = tabela[i]
(7)     se tabela[i]matemáticos complexos.
🧩 Partes de uma definição recursiva:
1. Caso base (ou base da recursão):
· Define diretamente os primeiros valores da sequência ou objeto.
· Exemplo simples:
Para fatorial: é o caso base.
2. Passo recursivo (ou passo indutivo):
· Usa o valor anterior para calcular o próximo.
· Exemplo simples:
Para fatorial: 
🧠 Onde é usada a recursividade?
· É usada para definir:
· Sequências de objetos (como Fibonacci, fatorial).
· Funções matemáticas.
· Conjuntos de dados ou estruturas (como árvores e listas encadeadas).
📌 Conclusão:
· A recursão é fundamental em matemática e computação.
· Seu funcionamento depende de:
· Um caso base bem definido.
· Um passo recursivo claro que leva de um valor ao próximo.
✅ Sequências Recursivas
· Uma sequência é uma lista ordenada de elementos (números ou objetos).
· Cada elemento é representado por uma posição:
· representa o k-ésimo termo da sequência.
🔁 Sequência Recursiva
· Uma sequência é recursiva quando:
1. Define um ou mais valores iniciais (caso base).
2. Define os próximos valores com base nos anteriores (passo recursivo).
📌 Exemplos de Sequências Recursivas
🔹 Exemplo1: Potências de 2 (Exponencial)
· Fórmula geral: 
· Definição recursiva:
· → (caso base)
· → (passo recursivo)
✅ Gerando a seguinte sequência: 
	
	Cálculo
	Resultado
	
	 
	1
	
	
	2
	
	
	4
	
	
	8
🔹 Exemplo 2: Sequência Aritmética (com razão 3)
· Definição recursiva:
· (caso base)
· , para 
✅ Gerando a seguinte sequência:
	
	Cálculo
	Resultado
	
	 
	1
	
	
	4
	
	
	7
	
	
	10
	
	
	13
📍 Observação Importante
· Indução pode ser usada para provar propriedades das sequências recursivas.
· Isso significa usar os termos anteriores para demonstrar que a regra funciona para os próximos.
✅ Funções Recursivas
· Uma função recursiva é definida por dois passos:
1. Passo básico: Define o valor da função para um caso inicial (geralmente ).
2. Passo recursivo: Define o valor da função com base em ou valores anteriores.
· Essa forma de definição também é chamada de definição indutiva.
📌 Exemplos de Funções Recursivas
🔹 Exemplo 1:
· Definição: Encontre , , e , supondo que f é definida recursivamente por:
· 
· 
· Solução: 
· 
· 
· 
· 
🔹 Exemplo 2: 
· Definição: Encontre , e se é definida recursivamente por: ; e para a função: 
· 
· 
· Solução:
· 
· 
· 
· 
· 
🔹 Exemplo 3:
· Definição: Encontre , e se é definida recursivamente por: ; e para a função: .
· 
· 
· Cálculos:
· 
· 
· 
· 
· 
🧮 Função Fatorial (Exemplo Clássico de Recursão)
· Definição matemática: O fatorial do inteiro 5 é calculado da seguinte forma:
· Definição recursiva:
· 
· 
· Cálculo de :
· 
· 
· 
· 
· 
· 
➡️ Resultado: 
✅ Indução Matemática e Funções Recursivas
· A indução matemática é uma ferramenta lógica usada para garantir que funções definidas recursivamente sejam bem definidas, ou seja, que sempre forneçam o mesmo resultado, independentemente da forma de aplicação da regra.
· Para funções recursivas:
· A base da definição dá os primeiros valores.
· A regra recursiva permite encontrar os próximos termos com base nos anteriores.
· Quando a definição usa mais de um termo anterior (como os dois últimos termos), é comum aplicar a indução forte, que garante a consistência mesmo em definições mais complexas.
🌀 Sequência de Fibonacci (Exemplo clássico)
· Os números de Fibonacci formam uma sequência infinita em que cada termo é a soma dos dois anteriores.
· Definição comum: Em termos matemáticos, a sequência é definida recursivamente pela fórmula a seguir, sendo o primeiro termo e , isto é, que a sequência começa em 0 e 1.
· Encontre os números de Fibonacci : ; ; ; e .
· 
· 
· para 
· Solução: 
· 
· 
· 
· 
· 
✅ Somatório
· Somatório é o nome dado à soma de uma sequência de números (também chamados de parcelas ou somandos).
· Exemplo: somar 2 + 4 + 6 é um somatório.
· O resultado do somatório é a soma total desses valores.
· Regras básicas:
· Se há um único número, o resultado é ele mesmo.
· Se não há nenhum número (sequência vazia), o resultado é 0 (por convenção).
🧮 Notação de Somatório
É representado pelo símbolo (sigma maiúsculo), com uma fórmula que define a sequência:
· → índice da soma (varia passo a passo)
· → valor inicial do índice (limite inferior)
· → valor final do índice (limite superior)
· → expressão ou valor em função de i
O índice começa em , aumenta de 1 em 1, até chegar em .
🔢 Número de termos do somatório
· É uma forma de se descobrir a quantidade de itens que serão executados na definição recursiva.
O número de termos da expressão resultante será dado por , onde:
· → número de termos
· → limite superior
· → limite inferior
· → número de restrições (se não houver, r = 0)
✏️ Exemplo simplificado
· Aqui, vai de 1 até 5.
· Cada termo é .
Número de termos:
· 
· → são 5 termos no total.
Passo a passo:
✅ Conjuntos e Definições Recursivas
📌 O que são Conjuntos
· Conjuntos: São estruturas formadas por elementos finitos e sem ordem específica (desordenados).
· Diferente de sequências e funções, que têm ordem definida entre os elementos.
🔁O que é um Conjuntos Recursivos?  
· Um conjunto recursivo é um conjunto de elementos que pode ser:
· Gerado por uma regra recursiva, e
· Reconhecido por um algoritmo que sempre termina (isto é, que sempre responde sim ou não para qualquer entrada).
· ✅ Em outras palavras: Conjunto recursivo é um conjunto onde podemos escrever um programa (algoritmo) que nos diz, para qualquer número, se ele pertence ou não ao conjunto, e esse programa sempre termina (não entra em loop infinito).
· 📘 Exemplo 1: Certos conjuntos podem ser definidos recursivamente, por exemplo os ancestrais de um ser vivo:
 
🔁 Definições Recursivas de Conjuntos
· Assim como funções, conjuntos também podem ser definidos recursivamente em duas etapas:
· Passo básico: define os primeiros elementos que pertencem ao conjunto.
· Passo recursivo (ou indutivo): define regras para formar novos elementos a partir dos já existentes.
· Também pode incluir, regra de extensão: Garante que o conjunto só contém:
· Elementos do passo básico.
· Elementos gerados pelas regras do passo recursivo.
📘 Exemplo 2 – Conjunto de inteiros S
Definição: Considere o subconjunto dos inteiros definido por:
· Passo básico: pertence ao conjunto : 
· Passo recursivo: Se e , então 
· Ou seja, se dois números e já estão em , então a soma também está em .
· O que isso significa? Isso significa que a partir do número 2, podemos gerar outros números, apenas somando elementos que já estão em .
Explicando passo a passo:
1. Passo básico: Começa com o 2 → está em S
2. Aplicando o passo recursivo/indutivo: 
	Etapa
	Números usados
	Novo número gerado
	Atualização do conjunto SS
	1
	Começamos com 2
	—
	
	2
	
	4
	
	3
	
	6
	
	4
	
	8
	
	5
	
	8, 10, 12...
	
· Ou seja, o conjunto S contém os múltiplos de 2 que podem ser construídos com somas repetidas de 2.
🎯 Resumo Conjunto Recursivo
	Termo
	Significado simples
	Conjunto
	Coleção de elementos (ex: pares, primos, etc.)
	Conjunto recursivo
	Um conjunto em que podemos testar com algoritmo se um elemento pertence a ele ou não
	Requisitos
	Deve ter uma regra (ou função) que sempre termina e responde sim/não corretamente
	Exemplo
	Conjunto dos pares, múltiplos de 3, primos, etc.
	Contraexemplo
	Conjunto de programas que não param (entram em Loop) — não recursivo
🧵 Conjuntos de Strings (cadeias de caracteres)
· Conjunto de string são muito usados em computação e linguagens formais. 
· Definições recursivas são muito importantes no estudo de strings, pois estas são composições de outras strings, ou seja, você sempre forma novas strings a partir de strings menores
🧵 O que são conjuntos de strings?
· String (ou cadeia de caracteres) é uma sequência finita de símbolos.
· Esses símbolos vêm de um alfabeto, por exemplo, o alfabeto (sigma)⅀ = {0,1}.
🔤 O que é o alfabeto ⅀ ?
· Definição: O alfabeto ⅀ é um conjunto finito de símbolos que usamos para formar strings (cadeias de caracteres).
· Exemplo 1: Se: 
· Então estamosdizendo que o nosso alfabeto tem dois símbolos: 0 e 1.
· Com esses símbolos, podemos formar strings como:
	Tamanho
	Strings possíveis
	0
	λ (string vazia)
	1
	"0", "1"
	2
	"00", "01", "10", "11"
	3
	"000", "001", ..., "111"
	...
	(e assim por diante)
· O conjunto completo de todas as combinações possíveis é chamado de: (Sigma estrela). 
· ⅀* = todas as strings formadas com 0 e 1, de qualquer tamanho, inclusive a vazia (λ). 
📌 Definição recursiva de ⅀* (conjunto de todas as strings):
· Passo básico: a string vazia (λ) ⅀*. Isso significa que, mesmo sem usar nenhum símbolo, temos uma string válida.
· Passo recursivo: 
Se:
· ⅀* (ou seja, é uma string já gerada)
· (ou seja, é um símbolo do alfabeto)
Então:
· ⅀* 👉 Ou seja: podemos formar novas strings adicionando símbolos ao final de strings que já existem.
📘 Exemplo: Se 
✅ Começamos com: λ (string vazia)
✅Passo recursivo/indutivo:
Adicionando símbolos:
· Primeira aplicação: 0, 1 → Agora temos: ⅀*= {λ, 0, 1}
· Segunda aplicação: 00, 01, 10, 11 → Agora temos: ⅀*= {λ, 0, 1, 00, 01, 10, 11}
· Terceira aplicação: 000, 001, 010, 011, 100, 101, 110, 111. → Agora temos: ⅀*= {λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111} e assim por diante.
· Ou seja, o ⅀* é formado por todas as combinações possíveis de bits com qualquer quantidade de símbolos (inclusive nenhum) do alfabeto ⅀.
🧩 Importância:
· A definição recursiva mostra como strings podem ser construídas passo a passo.
· É muito usada em:
· Linguagens formais
· Autômatos
· Compiladores
· Expressões regulares
Módulo 2. Identificar as situações de uso da recursividade
📌 Recursão
· Definição geral: Recursão (ou recursividade) é uma técnica de programação em que uma função chama a si mesma para resolver um problema.
· Presente em várias linguagens: Usada em linguagens como C, Java, Python, C++, entre outras.
· Aplicações comuns:
· Problemas com definições recursivas, como:
· Fatorial
· Sequência de Fibonacci
· Problemas com conjuntos ou sequência de valores
· Importância atual:
· Base para programação dinâmica
· Muito usada em linguagens funcionais
· Aplicada na resolução de problemas complexos
· Vantagens da Recursão:
· Soluções mais elegantes e simples
· Substitui laços de repetição (for, while) com chamadas recursivas
· Desvantagem / Cuidado necessário:
· A simplicidade pode esconder complexidade na implementação
· Requer atenção extra para evitar erros, como chamadas infinitas ou uso excessivo de memória
📌 O que é Recursão?
· Definição:
· Recursão é um método de resolver problemas quebrando-os em partes menores, até chegar a um caso simples que possa ser resolvido facilmente (caso base).
· Como funciona:
· Envolve uma função que chama a si mesma para resolver partes do problema.
· Estratégia usada:
· Essa técnica é conhecida como "dividir para conquistar" (segundo Miller e Ranum, 2020).
· Muito utilizada em algoritmos eficientes.
· Vantagem principal:
· Permite escrever soluções mais elegantes e simples, principalmente para problemas que seriam difíceis com laços tradicionais.
· Comentário adicional:
· Alguns problemas podem ser mais facilmente resolvidos com recursão do que com estruturas iterativas (for, while).
📌 Diferença entre Algoritmo Recursivo e Iterativo
✅ Conceito de fatorial:
· O fatorial de um número N (N!) é o produto de todos os números inteiros positivos de 1 até N.
· Por definição:
· (caso base ou condição de parada)
· A solução do fatorial se define matematicamente da seguinte forma:
🔁 Algoritmo Recursivo
· Como funciona o Algoritmo Recursivo:
· A função chama a si mesma, reduzindo o valor de N até chegar ao caso base (n = 0).
· Exemplo simplificado (fatorial de 5):
· fatorial(5) chama fatorial(4), que chama fatorial(3), até chegar em fatorial(0) = 1
Depois, os valores são multiplicados na volta: 
· 
· Pontos importantes:
· Mais intuitivo e próximo da definição matemática
· Necessita de uma condição de parada para evitar chamadas infinitas
· Usa a pilha de chamadas da memória (empilha os estados até resolver)
🔁 Exemplo 1: Fatorial de 5 usando Recursão
📌 Código (forma recursiva)
função fatorial(n: inteiro): inteiro
início
  se n = 0 então
    retorne 1
  senão
    retorne n * fatorial(n – 1)
fim
🔄 Algoritmo Iterativo
· Como funciona:
· Usa uma estrutura de repetição (repita, para (for), enquanto(while), etc.)
· Cria uma variável auxiliar (aux) para armazenar o resultado do fatorial
· Exemplo simplificado:
· Para n = 5, o loop faz:
aux = 1 × 2 × 3 × 4 × 5 = 120
· Pontos importantes:
· Não usa chamadas recursivas, o que economiza memória
· Pode ser mais eficiente em alguns casos
· Menos intuitivo do ponto de vista matemático, mas simples de implementar
🔄 Exemplo 2: Fatorial de 5 usando Iteração
📌 Código (forma iterativa)
função fatorial(n: inteiro): inteiro
var n, aux: inteiro
início
  aux = 1
  para i de 1 até n faça
    aux = aux * n
  fim_para
  fatorial = aux
fim
⚖️ Comparação entre os dois:
· Recursivo:
· Mais elegante e direto para problemas naturalmente recursivos (como fatorial, árvores, ordenações)
· Requer mais cuidado com uso de memória e condição de parada
· Iterativo:
· Mais eficiente em termos de uso de memória
· Pode ser mais "verbooso", mas evita problemas com profundidade de pilha
	Característica
	Recursivo
	Iterativo
	Lógica
	Chama a si mesmo
	Usa laço de repetição e variável auxiliar
	Facilidade de entender
	Mais próximo da matemática
	Mais direto para quem programa
	Memória
	Usa pilha de chamadas
	Usa menos memória
	Riscos
	Pode estourar a pilha se sem parada
	Menor risco de erro de execução
	Exemplo típico
	Fatorial, Fibonacci, árvores
	Contagens, somatórios, fatorial
💡 Quando usar recursão:
· Quando o problema envolve subproblemas repetitivos e precisa guardar estados intermediários, como:
· Percorrer árvores binárias
· Algoritmos de ordenação (ex: quicksort, mergesort)
✅ As Três Leis da Recursão
📌 LEI 1: Deve haver um caso básico (caso de parada)
· Todo algoritmo recursivo precisa de um ponto em que a função pare de se chamar.
· Esse ponto é chamado de caso básico: um problema pequeno o suficiente para ser resolvido diretamente, sem mais chamadas.
🧠 Exemplo: Fatorial
· A função fatorial(n) para quando n = 0, pois 0! = 1 já é um valor conhecido.
📌 LEI 2: A função deve se aproximar do caso básico
· A cada chamada recursiva, os dados devem mudar de forma a chegar mais perto do caso básico.
· Isso evita chamadas infinitas e garante que o problema vá sendo "reduzido".
🧠 Exemplo: Fatorial
· A função chama fatorial(n - 1), ou seja, diminui n a cada vez:
· fatorial(5) → fatorial(4) → fatorial(3) … até fatorial(0)
📌 LEI 3: A função deve chamar a si mesma
· A recursão ocorre quando a função se chama dentro dela mesma.
· Isso permite que o problema maior seja resolvido a partir de vários problemas menores.
🧠 Exemplo: Fatorial
· A função chama a si mesma com um valor menor:
· fatorial(n) = n * fatorial(n - 1)
📝 Resumo das três leis em uma frase:
Um algoritmo recursivo precisa saber quando parar (Lei 1), precisa se mover em direção a esse fim (Lei 2) e precisa se chamar enquanto não chegou lá (Lei 3).
🔁 Tipos de Recursividade
Existem alguns tipos mais complexos de recursividade para a resolução de problemas mais elaborados cuja recursão simples não suporta.
🌀 1. Recursividade em Cauda (Tail Recursion)
· Acontece quando a chamada recursiva é o último comando executado na função.
· Vantagem: O valor final é carregado junto com as chamadas, economizando espaço na pilha (menos uso de memória).
Exemplo simplificado:
A função fatorial(n, valor_atual) calcula o fatorial de n acumulando o resultado em valor_atual.
função fatorial (n:inteiro, valor_atual: inteiro) : inteiro​
inicio
  se n = 0 então
    valor_atual
  senão
    fatorial = fatorial (n – 1, valor_atual * n) // A recursão em cauda acontece aqui
  fim se​
fim
Para se tornar mais tangível segue código em python de recursividade em cauda:
🟢 Exemplo: Cálculo de Fatorial
def fatorial_cauda(n, acumulador=1):
    if n == 0:return acumulador
    return fatorial_cauda(n - 1, acumulador * n) # A recursão em cauda acontece aqui 
# Exemplo de uso
print("Fatorial em cauda de 5:", fatorial_cauda(5)) 
🧠 Explicação:
· fatorial_cauda(n, acumulador): calcula o fatorial de n acumulando o resultado em acumulador.
· Linha 1: Define a função. O acumulador começa com 1.
· Linha 2: Caso base: se n == 0, o fatorial de 0 é 1, então retorna o valor acumulado.
· Linha 4: Chamada recursiva é o último comando → é uma recursão em cauda.
Cada chamada já calcula parte do resultado e o passa para frente.
· Calculo que acontece por trás: 
fatorial(5, 1)
→ fatorial(4, 5)
→ fatorial(3, 20)
→ fatorial(2, 60)
→ fatorial(1, 120)
→ fatorial(0, 120)
→ retorna 120
· Uma função é considerada recursiva em cauda se o resultado final da chamada recursiva, no caso 120, for também o resultado final da execução da função. 
· Dessa forma, a última chamada já possui o resultado da função.
· Diferencial da Recursão em cauda: A função já carrega o resultado em cada passo, sem depender de operações após a chamada recursiva.
🌀 2. Recursão Indireta
· Uma função chama outra função, que eventualmente chama a primeira novamente.
· A recursão ocorre de forma indireta, passando por várias funções até voltar à original.
Exemplo simplificado:
· par(x) chama impar(x-1)
· impar(x) chama par(x-1)
Função par(x): boleano​
x: inteiro
inicio
Se x = 0 então
  retorne (verdadeiro)
Senão
  Se x = 1 então
    retorne (falso)
  senão
    retorne(impar(x-1)) // A recursão indireta acontece aqui ao invocar a função ímpar 
  fim se
fim se
fim
Função impar(x): boleano​
x: inteiro
inicio
Se x = 0 então
  retorne (falso)
Senão
  Se x = 1 então
    retorne (verdadeiro)
  senão
    retorne(par(x-1)) // A recursão indireta acontece aqui ao invocar a função par
  fim se
fim se
fim
Para se tornar mais tangível segue código em python de recursividade indireta:
🟢 Exemplo: Verificar se um número é par ou ímpar
def eh_par(n):
    if n == 0:
        return True
    else:
        return eh_impar(n - 1) # A recursão indireta acontece aqui ao invocar a função ímpar
def eh_impar(n):
    if n == 0:
        return False
    else:
        return eh_par(n - 1) # A recursão indireta acontece aqui ao invocar a função par
print(eh_par(4))   # Saída: True
print(eh_impar(7)) # Saída: True
🧠 Explicação:
· eh_par chama eh_impar, e eh_impar chama eh_par → recursão indireta.
· Linha 2: Se n == 0, é par → retorna True.
· Linha 4: Caso contrário, chama eh_impar(n - 1).
· O mesmo vale para eh_impar, mas retornando False se n == 0.
· Observação sobre a Recursão indireta: Pode aumentar muito o uso de memória, pois duas pilhas de chamadas funcionam paralelamente.
🌀 3. Recursão Aninhada (Nested Recursion)
· É uma função recursiva que pode receber um argumento que inclui outra função recursiva. 
· A função chama a si mesma como argumento de outra chamada recursiva.
· Torna-se mais complexa e cresce rapidamente (exponencialmente). Portanto, não é aconselhado seu uso.
· Nome alternativo: Também pode ser chamada de recursão dupla.
Exemplo simplificado:
· A função de Ackermann, onde a chamada está aninhada:
Função ackermann(n: inteiro, m:inteiro)
inicio
se n = 0
  retorno m + 1
senão se n > 0 e m = 0 então
  ackermann(n - 1, m)
senão
  ackermann(n - 1, ackermann(n, m-1)) // A recursão aninhada acontece aqui 
fim se
fim
· Isso significa que para calcular ackermann(1, 2) por exemplo, o valor ackermann(1, 1) deve ser calculado antes como parte do parâmetro da próxima chamada.
Para se tornar mais tangível segue código em python de recursividade aninhada:
🟢 Exemplo: Função de Ackermann
def ackermann(m, n):
    if m == 0:
        return n + 1
    elif m > 0 and n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1)) # A recursão aninhada ocorre aqui
print(ackermann(2, 2))  # Saída: 7
# print(ackermann(4, 2))  # ⚠️ Muito pesado! Pode travar
🧠 Explicação:
· Linha 2: Caso base: se m == 0, retorna n + 1.
· Linha 4: Se m > 0 e n == 0, reduz m e reinicia n com 1.
· Linha 6: Chamada aninhada: ackermann(m - 1, ackermann(m, n - 1))
· Primeiro precisa resolver ackermann(m, n - 1)
· O resultado é passado como argumento para outra chamada de ackermann.
· Essa função cresce muito rápido, por isso deve ser usada com valores pequenos.
✅ Resumo:
	Tipo
	Característica principal
	Exemplo
	Recursão em Cauda
	Última instrução é a chamada recursiva
	fatorial_cauda(n)
	Recursão Indireta
	Uma função chama outra, que chama a primeira
	eh_par e eh_impar
	Recursão Aninhada
	Chamada recursiva ocorre como argumento de outra chamada
	ackermann(m, n)
✔️ Conclusão
· Recursão em cauda: eficiente em memória, último comando da função.
· Recursão indireta: envolve múltiplas funções se chamando de forma cruzada.
· Recursão aninhada: função dentro de função, crescimento rápido e mais difícil de controlar (não aconselhada).
Esses tipos permitem resolver problemas mais complexos que a recursão simples não resolve com eficiência.
✅ Quando não empregar recursividade
· Em alguns momentos, funções iterativas oferecem mais benefícios do que funções recursivas.
🔸 Recursividade vs Iteração
· Recursão: Mais simples de codificar e entender para alguns problemas.
· Iteração: Mais eficiente em tempo de execução e uso de memória.
· A escolha depende do problema: Às vezes, iterar é mais trabalhoso, mas vale mais a pena por questão de desempenho.
🔸 Problema com o uso de memória na recursão
· Cada chamada recursiva ocupa espaço na memória, armazenando:
· Parâmetros da função
· Endereço de retorno
· Isso consome mais memória e tempo de processamento do que a iteração.
🔸 O que é um procedimento reentrante
· Um procedimento reentrante permite várias chamadas ativas ao mesmo tempo.
· A recursão é um exemplo disso, pois uma função chama a si mesma antes de terminar.
🔸 Uso da pilha na recursão
· Cada chamada recursiva é empilhada na memória.
· Quando a função termina, ela é desempilhada.
· Isso é mostrado na Figura 8, que ilustra como a memória se comporta com chamadas sucessivas.
🔸 Exemplo: Cálculo da sequência de Fibonacci (Figura 9 e 10) – Versão recursiva
🧮 Código (em C):
#include 
#include 
//protótipo de função Fibonacci
int fibonacci(int); // Declara que a função fibonacci será definida posteriormente e que recebe retorna um inteiro
int main() {
  int n, i;
    printf("Digite a quantidade de termos da série ");
    scanf("%d", &n);
    printf("Sequência de Fibonacci e: \n");
    for(i=0; i 2, a função retorna a soma dos dois termos anteriores:
· fibonacci(num - 1) + fibonacci(num - 2)
· Exemplo: Se o usuário digita 5, o programa chamará:
· fibonacci(1), fibonacci(2), fibonacci(3), fibonacci(4), fibonacci(5)
· Resultado da sequência exibida será: 1 1 2 3 5
❗ Problema:
· Crescimento exponencial do número de chamadas:
· fibonacci(31) → 4.356.617 chamadas
· fibonacci(32) → 7.049.155 chamadas!
· Isso causa um grande uso de memória e lentidão. 
· Logo, é interessante evitar programas recursivos no estilo de Fibonacci que resultam em uma “explosão” exponencial de chamadas.
🔍 Figura 10: A Figura 10 descreve