Analise Amortizada 2012 1

Introdu¸c˜ ao M´ etodo Agregado

M´ etodo Cont´ abil An´ alise Amortizada
Prof. Dr. Leandro Balby Marinho

An´ alise e T´ ecnicas de Algoritmos

Prof. Dr. Leandro Balby Marinho

1 / 36

UFCG CEEI

Introdu¸c˜ ao M´ etodo Agregado

M´ etodo Cont´ abil Roteiro

1. Introdu¸c˜ao

2. M´etodo Agregado

3. M´etodo Cont´abil

Prof. Dr. Leandro Balby Marinho

2 / 36

UFCG CEEI

Introdu¸c˜ ao M´ etodo Agregado

M´ etodo Cont´ abil An´alise Amortizada

Entender o comportamento assint´ otico em sequˆencias de opera¸c˜oes. Prof. Dr. Leandro Balby Marinho

2 / 36

UFCG CEEI

Introdu¸c˜ ao M´ etodo Agregado

M´ etodo Cont´ abil An´alise Amortizada

Entender o comportamento assint´ otico em sequˆencias de opera¸c˜oes. Normalmente, opera¸c˜ oes em estruturas de dados.

Prof. Dr. Leandro Balby Marinho

2 / 36

UFCG CEEI

Introdu¸c˜ ao M´ etodo Agregado

M´ etodo Cont´ abil An´alise Amortizada

Entender o comportamento assint´ otico em sequˆencias de opera¸c˜oes. Normalmente, opera¸c˜ oes em estruturas de dados.
Em alguns casos, o tempo de execu¸c˜ao de uma opera¸c˜ao varia em chamadas subsequentes.

Prof. Dr. Leandro Balby Marinho

2 / 36

UFCG CEEI

Introdu¸c˜ ao M´ etodo Agregado

M´ etodo Cont´ abil An´alise Amortizada

Entender o comportamento assint´ otico em sequˆencias de opera¸c˜oes. Normalmente, opera¸c˜ oes em estruturas de dados.
Em alguns casos, o tempo de execu¸c˜ao de uma opera¸c˜ao varia em chamadas subsequentes.
A an´alise amortizada leva em conta a m´edia do desempenho de uma opera¸c˜ao no pior caso.

Prof. Dr. Leandro Balby Marinho

2 / 36

UFCG CEEI

Introdu¸c˜ ao M´ etodo Agregado

M´ etodo Cont´ abil An´alise Amortizada

Entender o comportamento assint´ otico em sequˆencias de opera¸c˜oes. Normalmente, opera¸c˜ oes em estruturas de dados.
Em alguns casos, o tempo de execu¸c˜ao de uma opera¸c˜ao varia em chamadas subsequentes.
A an´alise amortizada leva em conta a m´edia do desempenho de uma opera¸c˜ao no pior caso.
Como essa opera¸c˜ao pode