24

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

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.345

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

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.