Logo Passei Direto
Buscar
eia o texto a seguir: Um algoritmo de pesquisa binária executa a estratégia de divisão e conquista. Esse algoritmo pode ser descrito assim: pesquise um array ordenado dividindo repetidamente o intervalo de pesquisa pela metade; comece com um intervalo cobrindo todo o array. Se o valor da chave de pesquisa for menor que o item no meio do intervalo, reduza o intervalo para a metade inferior. Caso contrário, reduza-o para a metade superior. Verifique repetidamente até que o valor seja encontrado ou o intervalo esteja vazio. Considerando as informações apresentadas, avalie as afirmações abaixo: I. Existem dois fundamentos da estratégia de divisão e conquista: um deles é a condição de parada e o outro é a fórmula relacional. II. Algoritmos como busca binária e busca sequencial são conhecidos como divisão e conquista, tendo como complexidade O(log n). III. Esse algoritmo consiste em duas etapas: dividir uma entrada (etapa 1, divisão) com o objetivo de encontrar uma solução para cada subproblema (etapa 2, conquista). É correto o que se afirma em:
User badge image
Bru Montano

ontem

Respostas

User badge image

Ed Verified user icon

ontem

Vamos analisar cada uma das afirmações: I. Existem dois fundamentos da estratégia de divisão e conquista: um deles é a condição de parada e o outro é a fórmula relacional. Essa afirmação é verdadeira, pois a condição de parada é essencial para evitar loops infinitos, e a fórmula relacional é usada para descrever a relação entre o tamanho do problema e o tamanho dos subproblemas. II. Algoritmos como busca binária e busca sequencial são conhecidos como divisão e conquista, tendo como complexidade O(log n). Essa afirmação é falsa. A busca binária é um algoritmo de divisão e conquista com complexidade O(log n), mas a busca sequencial não se enquadra nessa categoria, pois ela verifica cada elemento um por um, resultando em complexidade O(n). III. Esse algoritmo consiste em duas etapas: dividir uma entrada (etapa 1, divisão) com o objetivo de encontrar uma solução para cada subproblema (etapa 2, conquista). Essa afirmação é verdadeira, pois descreve corretamente as etapas do algoritmo de divisão e conquista. Com base na análise, as afirmações verdadeiras são I e III. Portanto, a alternativa correta que contém todos os itens verdadeiros é: I e III.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Mais conteúdos dessa disciplina