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 que cobramos $2 por cada operação de PUSH e POP e $0 por cada operação de COPY. Quando chamamos PUSH, usamos $1 para pagar pela operação e armazenamos o $1 restante no item que sofreu o PUSH. Do mesmo modo, quando chamamos POP usamos $1 para pagar pela operação e armazenamos o $1 restante na própria pilha.

Passo 2 de 4keyboard_arrow_downkeyboard_arrow_up

Como o tamanho da pilha nunca excede , o custo real de uma operação COPY é no máximo $, que é pago pelo $ encontrado nos itens que sofreram PUSH e na própria pilha. Isto é, como ocorrem operações de PUSH e POP entre duas operações de COPY, existe $ de crédito armazenado, seja em itens individuais (pela operação de PUSH) ou na própria pilha (pela operação de POP), até que uma operação de COPY seja chamada.

Passo 3 de 4keyboard_arrow_downkeyboard_arrow_up

Como o custo amortizado de cada operação é e a quantidade de crédito nunca é negativa, o custo total de operações é .

Passo 4 de 4keyboard_arrow_downkeyboard_arrow_up

Portanto, o custo de operações na pilha é .

Navegar por capítulo