62
Algoritmos - Teoria e Prática - 3ª Ed. 2012

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

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 3keyboard_arrow_downkeyboard_arrow_up

Nesse exercício temos um conjunto Q de pontos no plano, para definimos de modo que consista nos pontos em E, eliminados todos os pontos em camadas convexas . O exercício é dividido em dois itens, no primeiro vamos demonstrar que o algoritmo demora o tempo para encontrar as camadas convexas de um conjunto de pontos n.

Passo 2 de 3keyboard_arrow_downkeyboard_arrow_up

Para isso temos que, se existem k camadas convexas e as camadas contem x pontos, o tempo total de processo é definido por,

.

Passo 3 de 3keyboard_arrow_downkeyboard_arrow_up

Portanto, através da equação acima podemos provar o tempo para um número especifico k de camadas convexas. Porém para isso, precisamos ter .

Navegar por capítulo