60
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 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 é .

Navegar por capítulo