Segue a minha resposta deste exercício e gostaria de saber se está coerente.
Recebe um contador A e um índice do bit mais significativo e devolve o contador incrementado e o índice atualizado
Increment (A, l)
- i <- 0
- enquanto i < l e A[i] = 1 faça
- A[i] <- 0
- i <- i + 1
- se i < l e i < Comprimento[A] então
- A[i] <- 1
- l <- max {l, i}
Recebe um contador A e um índice do bit mais significativo e devolve A zerado.
Reset (A, l)
- i <- 0
- enquanto i < l faça
- A[i] <- 0
- i <- i + 1
- l <- 0
Análise amortizada. Em n operações temos que
A[0] é alterado n / 2^0 vezes
A[1] é alterado n / 2^1 vezes
.
.
.
A[chao(lg n)] é alterado n / 2^chao(lg n) vezes
= soma chao (n / 2 ^i) de i = 0 até chao (lg n)
< 2n
Agora vamos contar o número de alterações feita pela função Reset. Temos que
Para limpar de 0 a 0 é preciso que antes seja executada 2^0 chamadas do Increment
Para limpar de 0 a 1 é preciso que antes seja executada 2^1 chamadas do Increment
Para limpar de 0 a 2 é preciso que antes seja executada 2^2 chamadas do Increment
.
.
Para limpar de 0 a chao (lg i) é preciso que antes seja executada 2^(chao (lg i)) chamadas do Increment
= soma chao (n / 2 ^i) de i = 0 até chao (lg n)
< 2n
Somando as duas
= 2n + 2n = 4n = O
É assim mesmo que resolve?