Esse algoritmo apresentado é muito semelhanteleia observação no final da resposta a uma implementação do algoritmo para calcular o número n
da sequência de Fibonacci, que por sua vez tem complexidade temporal linear (o(n)
). Então, dá pra dizer que o comportamento esperado de T(n)
seja uma função linear, no formato T(n) = a*n + b
, para casos gerais. Porém, existem casos especiais: qualquer número com n <= 1
tem T(n) = 2
. Como sei disso? Fazendo o teste de mesa. Veja como foi para n = 1
:
- verifica valor da posição -1 >= 2 (
n >= 2
)
- retorne valor da posição -1 (
return n
)
Estou considerando que o goto
seja parte da operação primitiva de comparação, algo como jumpelse n >= 2, LABEL_ELSE
Agora, como seria para um outro caso? Para um caso genérico de n
? Testemos com n = 4
:
- verifica valor da posição -1 >= 2 (
n >= 2
)
- atribui 1 à posição 0 (
ant = 1
)
- atribui 1 à posição 1 (
preant = 1
)
- atribui valor da posição -1 à posição 3 (
i = n
)
- verifica se valor da posição 3 >= 3 (
i >= 3
)
- soma valor da posição 0 e valor da posição 1 (
ant + preant
)
- atribui resultado à posição 2 (
atual = ant + preant
, sendo que a soma foi considerada acima)
- atribui valor da posição 1 à posição 0 (
preant = ant
)
- atribui valor da posição 2 à posição 1 (
ant = preant
)
- decrementa a posição 3 (
i--
)
- verifica valor da posição 3 >= 3 (
i >= 3
)
- soma valor da posição 0 e valor da posição 1 (
ant + preant
)
- atribui resultado à posição 2 (
atual = ant + preant
, sendo que a soma foi considerada acima)
- atribui valor da posição 1 à posição 0 (
preant = ant
)
- atribui valor da posição 2 à posição 1 (
ant = preant
)
- decrementa a posição 3 (
i--
)
- verifica valor da posição 3 >= 3 (
i >= 3
)
- retorna valor da posição 2 (
return atual
)
Então, deram 18 operações para n = 4
. E para n = 5
?
- verifica valor da posição -1 >= 2 (
n >= 2
)
- atribui 1 à posição 0 (
ant = 1
)
- atribui 1 à posição 1 (
preant = 1
)
- atribui valor da posição -1 à posição 3 (
i = n
)
- verifica se valor da posição 3 >= 0 (
i >= 0
)
- soma valor da posição 0 e valor da posição 1 (
ant + preant
)
- atribui resultado à posição 2 (
atual = ant + preant
, sendo que a soma foi considerada acima)
- atribui valor da posição 1 à posição 0 (
preant = ant
)
- atribui valor da posição 2 à posição 1 (
ant = preant
)
- decrementa a posição 3 (
i--
)
- verifica valor da posição 3 >= 0 (
i >= 0
)
- soma valor da posição 0 e valor da posição 1 (
ant + preant
)
- atribui resultado à posição 2 (
atual = ant + preant
, sendo que a soma foi considerada acima)
- atribui valor da posição 1 à posição 0 (
preant = ant
)
- atribui valor da posição 2 à posição 1 (
ant = preant
)
- decrementa a posição 3 (
i--
)
- verifica valor da posição 3 >= 0 (
i >= 0
)
- soma valor da posição 0 e valor da posição 1 (
ant + preant
)
- atribui resultado à posição 2 (
atual = ant + preant
, sendo que a soma foi considerada acima)
- atribui valor da posição 1 à posição 0 (
preant = ant
)
- atribui valor da posição 2 à posição 1 (
ant = preant
)
- decrementa a posição 3 (
i--
)
- verifica valor da posição 3 >= 0 (
i >= 0
)
- retorna valor da posição 2 (
return atual
)
Deu 24 operações. Daqui, conseguimos tirar o valor de a
em T(n) = a*n + b
e, então, descobriremos b
:
T(5) = a*5 + b
T(4) = a*4 + b
T(5) = 24
T(4) = 18
T(5) - T(4) = a*5 + b - (a*4 + b) = a
T(5) - T(4) = 24 - 18 = 6
a = 6
18 = a*4 + b = 6*4 + b = 24 + b
b = -6
Portanto, temos que, para n >= 2
, T(n) = 6*n - 6
. Portanto:
Esse algoritmo, apesar de ser muito semelhante a uma implementação clássica ao algoritmo que calcula os números da sequência de Fibonacci, contém um erro que o desqualifica como tal. Veja, por exemplo, o comoportamento para n = 2
:
- verifica valor da posição -1 >= 2 (
n >= 2
)
- atribui 1 à posição 0 (
ant = 1
)
- atribui 1 à posição 1 (
preant = 1
)
- atribui valor da posição -1 à posição 3 (
i = n
)
- verifica se valor da posição 3 >= 3 (
i >= 3
)
- retorna valor da posição 2 (
return atual
)
Em nenhum momento a posição 2 (que representa a variável atual
) foi preenchida. Isso indica que, nesse momento, o retorno da função é indefinido. Isso é proibido em algumas linguagens de programação, mas os compiladores de C que conheço permitem isso. Em muitos casos, o retorno será um lixo de memória, um valor qualquer, que as vezes pode até coincidir com o valor adequado. Em outras vezes, alguns interpretadores que vi por aí inicializam variáveis com 0. Ademais, veja o resultado da saída para alguns números:
fib(0) => 0
fib(1) => 1
fib(2) => undefined
fib(3) => 2
fib(4) => 3
fib(5) => 5
Existem algumas soluções para corrigir o algoritmo:
- tornar 2 um caso especial e forçar retornar 1
- fazer
preant = 0, ant = 1
e o laço até i >= 2
A primeira solução adicionaria 1 passo a mais nos casos especiais (e nenhum no caso geral, se bem escrito o algoritmo); também alteraria a composição da função, sendo constante no intervalo (-infty, 2]
e linear em [3, +infty)
(a original é constante no intervalo (-infty, 1]
e linear em [2, +infty)
).
A segunda solução não altera o número de passos nos casos especiais, nem tampouco os intervalos que definem o comportamento da função, mas alteraria a parte linear; sairia de 6*n - 6
para 6*n
, já que pelo menos um laço (que por sua vez tem 6 operações) será sempre executado.
T(n)
?