Logo Passei Direto
Buscar
Qual é a complexidade temporal da abordagem de divisão e conquista aplicada ao problema da mochila binária com divisão em duas metades? a. O(n²) b. O(n C), onde C é a capacidade da mochila c. O(2ⁿ/² log 2ⁿ/²) d. O(C log n) e. O(n log n)
User badge image
Rubens Campos

há 3 meses

Respostas

User badge image

Ed Verified user icon

há 3 meses

Para determinar a complexidade temporal da abordagem de divisão e conquista aplicada ao problema da mochila binária, precisamos considerar como a abordagem funciona. No problema da mochila binária, a ideia é dividir o conjunto de itens em duas metades e resolver o problema para cada metade, combinando os resultados. A complexidade do problema pode ser analisada em termos de como as soluções parciais são combinadas e quantas chamadas recursivas são feitas. Analisando as alternativas: a) O(n²) - Essa complexidade não se aplica ao problema da mochila binária com divisão e conquista. b) O(n C), onde C é a capacidade da mochila - Essa é uma complexidade que pode surgir em abordagens dinâmicas, mas não é a correta para divisão e conquista. c) O(2ⁿ/² log 2ⁿ/²) - Essa opção parece complexa, mas não é uma representação comum para a complexidade do problema da mochila. d) O(C log n) - Essa complexidade não se aplica diretamente ao problema da mochila binária. e) O(n log n) - Essa é uma complexidade que pode surgir em algoritmos de ordenação, mas não é a correta para o problema da mochila. A complexidade correta para a abordagem de divisão e conquista aplicada ao problema da mochila binária é: b) O(n C), onde C é a capacidade da mochila.

Essa resposta te ajudou?

0
Dislike0
left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

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

Mais conteúdos dessa disciplina