SICP - Exercício 1.14 - Contando o troco... Um pouco de análise de algoritmos

Desenhe a árvore ilustrando o processo gerado pelo count-change da seção 1.2.2 quando está contando o troco para 11 centavos. Quais são as ordens de crescimento de espalo e número de passos usados por esse processo à medida que a quantia a ser trocada aumenta?

Solução: Primeiramente, vamos ao desenho da árvore:

As reticências são para representar um processo que se repete.

Complexidade Espacial
A complexidade espacial do processo gerado por count-change é linear, mais precisamente, Θ(n), com a quantidade a ser trocada. Vejamos: segundo o livro, o espaço é proporcional à altura da árvore que descreve o processo. Sabemos que (count-change n) chama (cc n 5). A altura da árvore se dará pelo caminho (cc n 5) -> (cc n 4) -> (cc n 3) -> (cc n 2) -> (cc n 1) -> (cc (- n 1) 1) -> (cc (- n 2) 1) -> ... (cc 1 1) -> (cc 0 1). A altura é, portanto, da forma n + constante. Assim, temos um processo Θ(n) em espaço.

Complexidade do número de operações
A complexidade do número de operações da ordem de n⁵. Para que possamos chegar a esse resultado, notemos que, como (count-change n) executa somente a expressão (cc n 5), devemos estudar a complexidade desta última expressão. Seja S(n, p) o número de passos realizados por (cc n p), para n≥0 e 0≤p≤5. Definindo como C(n) o número de passos em que estamos interessados, temos:

C(n) = S(n, 5) + constante

Porém, é possível achar uma expressão para S(n, 5).
S(n, 5) = S(n, 4) + S(n-50, 5)

Analogamente,
S(n, 4) = S(n, 3) + S(n-25, 4)
S(n, 3) = S(n, 2) + S(n-10, 3)
S(n, 2) = S(n, 1) + S(n-5, 2)
S(n, 1) = S(n, 0) + S(n-1, 1)

Agora, basta resolver as "recursões", de baixo pra cima...

Primeiro, notamos que o número de passos em p=0 é uma constante.
S(n, 1) = k + S(n-1, 1)
Usando a mesma fórmula para expandir S(n-1, 1), temos
S(n-1, 1) = k + S(n-2, 1) e, portanto,
S(n, 1) = k + (k + S(n-2, 1)) = 2k + S(n-2, 1)
A fórmula geral pode ser vista facilmente:
S(n, 1) = q*k + S(n-q, 1)
Sabemos que a o número de passos quando n é 0 também é constante (vamos chamar de p). Podemos substituir q por n e obter
S(n, 1) = n*k + S(n-n, 1)
S(n, 1) = k*n + p
Portanto, S(n, 1) é Θ(n).

Agora, vamos trabalhar com
S(n, 2) = S(n, 1) + S(n-5, 2)
S(n, 2) = S(n, 1) + S(n-5, 1) + S(n-2*5, 2)
S(n, 2) = S(n, 1) + S(n-5, 1) + S(n-2*5, 1) + S(n-3*5, 2)
A fórmula geral é, portanto:
S(n, 2) = S(n, 1) + S(n-5, 1) + S(n-2*5, 1) + ... + S(n-k*5, 1) + S(n-(k+1)*5, 2)

De maneira geral, sabemos calcular cada um dos termos, com exceção do último. Mas há uma condição especial em que sabemos calcular até mesmo o último termo. Podemos expandir a expressão até o primeiro valor de k tal que n-(k+1)*5 seja menor que zero. Daí, saberemos que, para tal k, S(n - (k+1)*5, 2) será uma constante.

Vamos determinar tal k:

n-5(k+1) < 0
n-5 < 5k
k > n/5-1

Assim, sabemos que o nosso valor de interesse para k é o teto (arredondamento para cima) de n/5. Nessas condições, o somatório para S(n, 2
S(n, 2) = O(n) + O(n-5) + O(n-10) + ... + O(n-5*n/5) + constante
Estamos somando um número dependente de n de termos que também são dependentes de n. Raciocinando informalmente, temos

S(n, 2) = n/5*O(n)
S(n, 2) = O(n²)

Analogamente, podemos calcular as complexidades de S(n, 3), S(n, 4) e, finalmente, C(n) = S(n, 5)

S(n, 3) = n/10*O(n²)
S(n, 3) = O(n³)

S(n, 4) = n/25*O(n³)
S(n, 4) = O(n⁴)

C(n) = S(n, 5) = n/50*O(n⁴)
C(n) = O(n⁵)

Concluindo
O método de calcular troco apresentado é uma simples tradução de um algoritmo recursivo para a linguagem Scheme. Assim sendo, por não tomar os devidos cuidados, repete bastante certos cálculos. Mas nem tudo está perdido, há técnicas para eliminar essas repetições

O raciocínio informal que eu usei pra obter a complexidade n⁵ a primeira vista parece razoavelmente complicado. Lembre-se, porém, que ele é usado pra analisar vários algoritmos diferentes (principalmente do estilo divisão e conquista). Assim sendo, não se preocupe, porque você vai acabar absorvendo a técnica.