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.196

Passo 1 de 4keyboard_arrow_downkeyboard_arrow_up

Consideremos a implementação de uma pilha que mantém uma página da pilha na memória. Temos por condição que uma operação só é executada na pilha quando páginas suficientes da mesma estão presentes na memória. Se as páginas requeridas estão presentes, então não é necessário acesso ao disco.

Passo 2 de 4keyboard_arrow_downkeyboard_arrow_up

Para encontrar o tempo de execução no pior caso ao executar operações na pilha, tomamos a seguinte sequência de operações: PUSH, PUSH, POP, POP etc. Assumimos que a primeira operação de PUSH é feita no fim da página, isto é, no limite da página. A segunda operação de PUSH ocorre na página seguinte. Do mesmo modo, a segunda operação de POP precisa ler a página anterior mais uma vez.

Passo 3 de 4keyboard_arrow_downkeyboard_arrow_up

Desse modo, acessar palavras em uma página de disco necessita de tempo na CPU e um acesso ao disco. Logo, operações necessitarão de um total de acessos ao disco, já que operações serão executadas na pilha.

Passo 4 de 4keyboard_arrow_downkeyboard_arrow_up

Portanto, são necessários acessos ao disco na implementação citada, e o tempo de CPU para operações é .

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.