59
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 14keyboard_arrow_downkeyboard_arrow_up

Consideremos o algoritmo SELECT. Neste algoritmo, elementos de um arranjo são divididos em grupos, com cada grupo tendo 5 elementos. Dos grupos, no máximo um grupo tem elementos.

Passo 2 de 14keyboard_arrow_downkeyboard_arrow_up

Ordenamos os elementos nos grupos e encontramos a mediana de cada grupo. Então determinamos que a mediana entre todas as medianas é . Pelo menos metade dos grupos têm 3 elementos que são maiores do que , exceto o grupo que não possui 5 elementos e o grupo que contém .

Passo 3 de 14keyboard_arrow_downkeyboard_arrow_up

Assim calculamos a quantidade de elementos maiores e menores que :

Portanto existem pelo menos elementos maiores que e o mesmo número de elementos menores que .

Passo 4 de 14keyboard_arrow_downkeyboard_arrow_up

Com grupos de 7 elementos, o número de elementos que é maior ou menor que a mediana é calculado da seguinte maneira:

Passo 5 de 14keyboard_arrow_downkeyboard_arrow_up

No pior caso, o algoritmo SELECT chama recursivamente no máximo elementos. Assim, a recorrência é dada por:

Passo 6 de 14keyboard_arrow_downkeyboard_arrow_up

Consideremos onde é qualquer constante e a limitemos com o termo não-recursivo . Assim, temos:

Passo 7 de 14keyboard_arrow_downkeyboard_arrow_up

Adicionamos e subtraímos no resultado acima:

Passo 8 de 14keyboard_arrow_downkeyboard_arrow_up

Para que o último passo acima seja verdadeiro, temos que . Logo:

Passo 9 de 14keyboard_arrow_downkeyboard_arrow_up

Consideremos . Isso nos daria . Desse modo, selecionando satisfaz o resultado acima. Portanto, o algoritmo SELECT funcionará em tempo linear quando os elementos de entrada são divididos em grupos de 7.

Passo 10 de 14keyboard_arrow_downkeyboard_arrow_up

Quando os elementos são divididos em grupos de 3, o número de elementos que são menores ou maiores que a mediana é calculado da seguinte maneira:

Passo 11 de 14keyboard_arrow_downkeyboard_arrow_up

No pior caso, o algoritmo SELECT chama recursivamente no máximo elementos. Assim, a recorrência é dada por:

Passo 12 de 14keyboard_arrow_downkeyboard_arrow_up

Consideremos onde é qualquer constante e a limitemos com o termo não-recursivo . Assim, temos:

Passo 13 de 14keyboard_arrow_downkeyboard_arrow_up

Como , não é possível que tenhamos . Assim, o algoritmo SELECT não funcionará em tempo linear quando os elementos de entrada são divididos em grupos de 3.

Passo 14 de 14keyboard_arrow_downkeyboard_arrow_up

Portanto, o algoritmo SELECT funcionará em tempo linear quando os elementos de entrada são divididos em grupos de 7. Por outro lado, não funcionará em tempo linear quando os elementos de entrada são divididos em grupos de 3.

Navegar por capítulo