aula-AnaliseAlgoritmos
202 pág.

aula-AnaliseAlgoritmos


DisciplinaAlgoritmos14.810 materiais172.771 seguidores
Pré-visualização12 páginas
limite para o custo real total.
UFMG/ICEx/DCC 199
Método potencial
\u2022 Associa-se uma energia potencial a cada estrutura de dados.
\u2022 Energia potencial é o \u201cpotencial para fazer um estrago\u201d.
\u2022 Custo amortizado = Custo atual +
Novo potencial \u2212
Potencial anterior
\u2013 Deve-se pagar para incrementar o potencial da estrutura de dados.
\u2022 Se a operação tem um custo cumulativo alto mas reduz bastante o potencial,
então o custo amortizado é baixo.
\u2022 Como encontrar o potencial?
Ü Determine o que torna uma estrutura de dados ruim.
UFMG/ICEx/DCC 200
Regras básicas para funções potenciais
\u2022 Devem ser sempre não negativas.
\u2022 Devem começar de zero.
\u2022 Implica uma seqüência de n operações que custam no máximo n× \u201ccusto
amortizado\u201d.
UFMG/ICEx/DCC 201
Contador binário
\u2022 Estrutura de dados é \u201cruim\u201d se tem vários 1\u2019s.
\u2022 Seja \u3a6(Contador)= # 1\u2019s no contador.
\u2022 Potencial aumenta quando há um incremento:
= # (0\u2192 1) \u2212 # (1\u2192 0)
= 1 \u2212 # (1\u2192 0)
\u2022 Custo amortizado do incremento:
= Custo real (atual) + Aumento do potencial
= (1 + # (1\u2192 0) + (1 \u2212 # (1\u2192 0)))
= 2
\u2022 Custo amortizado é 2 e o custo de n incrementos é no máximo 2n.
UFMG/ICEx/DCC 202