Flashcards
Sem título
Flashcards do conjunto (11)
- 1O que é o paradigma Divisão e Conquista? Quais são os 3 passos?DIVIDIR: quebrar em subproblemas menores. CONQUISTAR: resolver recursivamente. COMBINAR: unir as soluções. Ex.: MergeSort divide o array ao meio, ordena cada metade e intercala
- 2Como o MergeSort aplica Divisão e Conquista? Qual sua recorrência e complexidade?DIVIDIR: encontra o meio. CONQUISTAR: chama MergeSort em cada metade. COMBINAR: intercala em O(n). Recorrência: T(n) = 2T(n/2) + Θ(n) → Θ(n log n)
- 3que é o Problema do Subarranjo de Soma Máxima? Como D&C resolve?Encontrar subarranjo contíguo de soma máxima em um array com negativos. D&C divide ao meio e analisa 3 casos: máximo só à esquerda, só à direita, ou cruzando o ponto médio. Complexidade: Θ(n log n).
- 4O que é uma Relação de Recorrência? Dê um exemplo.Equação que define T(n) em termos de T com entradas menores, com um caso base. MergeSort: T(n) = 2T(n/2) + Θ(n), T(1) = Θ(1). Representa: subproblemas + custo de dividir/combinar.
- 5O que significa cada termo em T(n) = aT(n/b) + f(n)?a ≥ 1 = número de subproblemas. b > 1 = fator de redução do tamanho. f(n) = custo de dividir + combinar. n/b = tamanho de cada subproblema. MergeSort: a=2, b=2, f(n)=Θ(n).
- 6Quais são os passos do Método de Substituição?Passo 1: Adivinhar (chute) o limite assintótico. Passo 2: Hipótese de indução: T(k) ≤ c·k·log(k) para k < n. Passo 3: Substituir na recorrência e verificar que a desigualdade se mantém.
- 7Qual a principal dificuldade do Método de Substituição e como superá-la?Fazer um chute inicial correto. Estratégias: usar a Árvore de Recorrência para intuir o limite; se a hipótese não fechar, subtrair termos de ordem inferior (ex.: T(n) ≤ c·n – d em vez de T(n) ≤ c·n).
- 8O que é uma Árvore de Recorrência e como calcular o custo total?Diagrama que expande a recorrência nível a nível. Cada nó = custo do subproblema naquele nível. Custo total = soma de todos os níveis. Altura da árvore = log_b(n). Número de folhas = n^(log_b a).
- 9Calcule T(n) = 2T(n/2) + cn pela Árvore de Recorrência.Nível 0: cn. Nível 1: 2·(cn/2) = cn. Nível k: cn. Cada nível custa cn! Há log₂(n) + 1 níveis. Total = cn·(log n + 1) = Θ(n log n). Confirmado pelo Método Mestre (Caso 2).
- 10Quais são os 3 casos do Método Mestre para T(n) = aT(n/b) + f(n)?Seja p = n^(log_b a). Caso 1: f(n) = O(p / n^ε) → T = Θ(p). Caso 2: f(n) = Θ(p) → T = Θ(p · log n). Caso 3: f(n) = Ω(p · n^ε) + regularidade → T = Θ(f(n)).
- 11Quando o Método Mestre NÃO pode ser aplicado?Quando f(n) não é polinomialmente maior ou menor que n^(log_b a). Ex.: f(n) = n/log(n) não se encaixa em nenhum caso. Também inválido se a < 1, b ≤ 1, ou a condição de regularidade do Caso 3 falhar. Nesses casos, use Substituição ou Árvore.
Informações
- Descrição
- FlashCards sobre Sem título, criado por Vinícius De Souza em 07-05-2026.
- Criado por
- Vinícius De Souza · mai 2026
- Atualizado
- 7 mai 2026
- Visualizações
- 0
- Avaliação