30

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 7keyboard_arrow_downkeyboard_arrow_up

Podemos resolver os subproblemas da questão apresentada de duas maneiras diferentes. Em cada ponto possível para divisão da cadeia de matrizes, usamos enumeração para encontrar todas as maneiras de parentizar a metade esquerda e a metade direita da cadeia, então procuramos todas as combinações possíveis para as duas metades. O produto do número de maneiras para se fazer a metade esquerda e do número de maneiras para se fazer a metade direita é igual ao trabalho total para encontrarmos cada combinação dos dois subproblemas.

Passo 2 de 7keyboard_arrow_downkeyboard_arrow_up

Usando RECURSIVE-MATRIX-CHAIN, em cada ponto possível para dividirmos a cadeia de matrizes encontramos a melhor maneira de parentizar a metade esquerda e a metade direita da cadeia e combinamos somente esses resultados. Assim, o trabalho para combinarmos os resultados dos subproblemas das metades esquerda e direita é .

Passo 3 de 7keyboard_arrow_downkeyboard_arrow_up

Sabemos que o tempo de execução para enumeração é . Mostraremos então que o tempo de execução de RECURSIVE-MATRIX-CHAIN é , e assim é assintoticamente mais eficiente.

Passo 4 de 7keyboard_arrow_downkeyboard_arrow_up

Podemos definir a seguinte recorrência para RECURSIVE-MATRIX-CHAIN:

Passo 5 de 7keyboard_arrow_downkeyboard_arrow_up

Reescrevendo a recorrência acima, temos então:

Provamos então através do método da substituição que , mostrando que para todo .

Passo 6 de 7keyboard_arrow_downkeyboard_arrow_up

Usando indução, temos:

Passo 7 de 7keyboard_arrow_downkeyboard_arrow_up

Portanto, o modo mais eficiente é executar RECURSIVE-MATRIX-CHAIN.

Navegar por capítulo

O passo a passo dos exercícios mais difíceis

12xR$ 29,90 /mêsCancele quando quiser, sem multa

E mais

  • check Videoaulas objetivas
  • check Resumos por tópicos
  • check Salve para ver depois
  • check Disciplinas ilimitadas
  • check Filtros exclusivos de busca