Flashcards
Untitled
Cards in this deck (10)
- 1Quais são as três etapas fundamentais do paradigma de Divisão e Conquista?1.Dividir (o problema em subproblemas).
2. Conquistar (resolver os subproblemas recursivamente).
3. Combinar (unir as respostas dos subproblemas). - 2No algoritmo MergeSort, o que é um subarranjo?É uma fatia menor do array original, gerada sucessivamente durante a etapa de "Divisão" para que possa ser ordenada independentemente antes da combinação final.
- 3O que é uma Relação de Recorrência na análise de algoritmos?É uma equação matemática que descreve o tempo de execução de um algoritmo recursivo em função do tempo de execução de entradas menores.
- 4a equação do MergeSort T(n) = 2T(n/2) + Θ(n), o que significa a parte Θ(n)?Representa o custo (tempo gasto) para realizar a divisão do array e, principalmente, a combinação (merge) dos subarranjos naquele nível de recursão.
- 5Quais são os dois passos para resolver uma recorrência pelo Método de Substituição?1. Adivinhar a forma da resposta (o limite assintótico).
2. Usar indução matemática para provar que o palpite está correto e encontrar as constantes. - 6Qual é a principal limitação ou dificuldade matemática do Método de Substituição?Não existe uma forma sistemática para gerar o palpite inicial correto. Depende da intuição e experiência de quem está analisando o algoritmo.
- 7Qual é o objetivo de desenhar uma Árvore de Recorrência?Visualizar e somar os custos da recursão nível por nível para encontrar um palpite preciso ou a solução direta da complexidade assintótica.
- 8O que representam os nós folhas (a base) em uma Árvore de Recorrência e qual costuma ser o custo deles?Representam os casos base da recursividade (onde o problema não é mais dividido). O custo de resolução de um nó folha é, em geral, constante, ou seja, Θ(1).
- 9Qual é a forma geral da recorrência que pode ser resolvida aplicando o Método Mestre?T(n) = aT(n/b) + f(n), onde a >= 1$, b > 1, e f(n) é uma função assintoticamente positiva.
- 10No Método Mestre, se o custo das divisões (folhas) for polinomialmente maior que o custo de combinação $f(n)$ (Caso 1), qual é a complexidade final do algoritmo?A complexidade será dominada pelas folhas, resultando em T(n) = Θ(n^log_b a).
Information
- Description
- Flashcards on Untitled, created by Bernardo Soares on 03/05/2026.
- Created by
- Bernardo Soares
- Views
- 0
- Rating