sin x ≈ x
, se x
é suficientemente pequeno, e da identidade trigonométricasin x = 3 sin x/3 - 4 sin3 x/3
para redzir o tamanho do argumento da função seno. (Para os propósitos deste exercício, um ângulo é considerado "suficientemente pequeno" se seu módulo não é maior que 0.1 radianos). Essas ideias são incorporadas nos seguintes procedures:
a. Quantas vezes o procedure p é aplicado quando
(sine 12.15)
é avaliado?b. Qual é a ordem de crescimento em espaço e número de passos (como uma função de a) usada pelo processo gerado pelo procedure
sine
quando a expressão (sine a)
é avaliada?Solução:
a. O procedure p é aplicado 5 vezes. Vamos avaliar a expressão 12.15 manualmente:
De agora em diante, vamos pular as avaliações dos
if
s.Agora, a expansão acabou. Vai começar a redução. Desde já, podemos ver que o procedure
p
é chamado exatamente 5 vezes. Os passos a seguir são mostrados apenas para que possamos ver todo o cálculo.b. A ordem de crescimento, em fumção de a, do processo gerado pelo procedure
sine
quando a expressão (sine a)
é avaliada, é log a
, tanto em espaço quanto em número de passos.Primeiramente, vamos chamar de k(a) o número de vezes que o procedure
p
é chamado, em função de a.Observando a estrutura do código, podemos chegar à seguinte fórmula.
k(a) = 0
, se |a| ≤ 0.1
k(a) = 1 + k(a/3)
, caso contrário.Vamos expandir k(a/3):
k(a/3) = 1
, se |a|/3 ≤ 0.1
, ou seja, se |a| ≤ 0.3
k(a/3) = 1+ k(a/32)
, caso contrárioVoltando para k(a), podemos dizer:
k(a) = 0
, se |a| ≤ 0.1
k(a) = 1
, se 1 < |a| ≤ 0.3
k(a/3) = 1+ k(a/32)
, caso contrárioOra, tal expansão nos leva a pensar em um padrão. A fórmula fechada para k(a) é
k(a) = 0
, se |a| ≤ 0.1
k(a) = teto(log(a/0.1, 3))
, caso contrário.Na fórmula anterior,
log(x, y)
significa o logaritmo de x na base y, e a função teto(x)
é definida como o menor inteiro maior ou igual a x.Assim, teto(0) = 0, mas teto(0.000001) = 1. De fato, para a=12.15 temos log(121.5, 3) = 4.369070246428542 e, portanto, k(12.15) = 5.
Para responder (finalmente) ao exercício, vamos considerar que as funções
cube
e p
executam um número constante de passos. Isso só é verdade se os argumentos dessas funções não forem muito grandes, mas para o propósito desse exercício podemos assumir tal fato. Daí, fica fácil observar que:k(a)
é da ordem delog a
- O espaço utilizado é proporcional a
k(a)
, portantosine
também é da ordem delog a
- O mesmo vale para o número de passos, uma vez que consideramos
(cube a)
e(p a)
constantes em a
Nenhum comentário:
Postar um comentário