Logo Passei Direto
Buscar

Matemática

UNICESUMAR
Pergunta 9 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
jose maria olaya olaya

mês passado

Respostas

User badge image

Ed Verified user icon

mês passado

Para determinar a complexidade temporal da abordagem de divisão e conquista aplicada ao problema da mochila binária, precisamos considerar como a técnica de divisão e conquista funciona nesse contexto. No problema da mochila binária, a abordagem de divisão e conquista geralmente envolve dividir o conjunto de itens em duas metades, resolver o problema para cada metade e, em seguida, combinar os resultados. A complexidade do problema pode ser expressa em termos do número de itens (n) e da capacidade da mochila (C). Analisando as alternativas: a) O(n²) - Essa complexidade não é típica para o problema da mochila binária. b) O(n C), onde C é a capacidade da mochila - Essa é uma complexidade comum para a abordagem dinâmica do problema da mochila, mas não necessariamente para a abordagem de divisão e conquista. c) O(2ⁿ/² log 2ⁿ/²) - Essa opção parece complexa, mas não é uma representação típica da complexidade do problema da mochila. d) O(C log n) - Essa opção não se alinha com a abordagem de divisão e conquista. e) O(n log n) - Essa complexidade é mais associada a algoritmos de ordenação, não ao problema da mochila. A opção que melhor se alinha com a complexidade temporal da 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

Ainda com dúvidas?

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

Mais conteúdos dessa disciplina