Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
Uma fila é implementada com duas pilhas S1 e S2, enfileirando em S1 e desenfileirando a...
Uma fila é implementada com duas pilhas S1 e S2, enfileirando em S1 e desenfileirando a partir de S2 com transferência de S1 para S2 quando S2 está vazia. Para uma sequência com M enfileiramentos e M desenfileiramentos intercalados, assinale o custo amortizado por operação.
A
Θ (log M) por operação, pois cada transferência entre pilhas executa busca binária em S2.
B
Θ (1) por operação, pois cada elemento movimenta-se no máximo duas vezes entre as pilhas.
C
Θ (√M) por operação, pois a movimentação total distribui-se em blocos de tamanho médio raiz de M.
D
Θ (M) por operação, pois cada desenfileiramento percorre todos os elementos remanescentes.