[SICP 연습] 132 연습 3.63.

연습

원문

Exercise 3.63. Louis Reasoner asks why the sqrt-stream procedure was not written in the following more straightforward way, without the local variable guesses:

(define (sqrt-stream x) (cons-stream 1.0 (stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-stream x))))

Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa’s answer. Would the two versions still differ in efficiency if our implementation of delay used only (lambda () ) without using the optimization provided by memo-proc (section 3.5.1)?

분석하다.

책 233페이지의 sqrt-stream과 Louis의 차이는 gusses를 반환 결과로 사용한 것이 하나의 흐름이라는 데 있다.매번의 연산은 지난번의 결과를 호출하여 단지 한 번 더 계산할 뿐이다.memo-proc가 있기 때문에 복잡도는 theta(n)이다.
Louis도 되돌아오는 흐름이지만 책의 정의에 비해 지난번부터 호출된 것이 아니라 n=1부터 호출된 것이다.따라서 임의의 계산에 대해서는 n보가 필요하다.그래서 그것의 복잡도는 theta(n^2)이다.
sqrt-stream의memo-proc를 제거하면 이들의 효과는 같다. 사실guesses를 통해 흐름을 유지하여memo-proc의 효과를 달성하기 때문이다.Louis의 정의는 memo-proc에 의존하지 않았다.
방문해 주셔서 감사합니다. 도움이 되었으면 합니다.여러분의 관심이나 소장, 평론 또는 좋아요를 환영합니다.
본문을 수정하고 질문을 받기 위해 전재는 출처를 밝혀 주십시오.http://blog.csdn.net/nomasp