30

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

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

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.