【SICP练习】132 练习3.63-阿里云开发者社区

开发者社区> nomasp> 正文

【SICP练习】132 练习3.63

简介:
+关注继续查看

练习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


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
使用NAT网关轻松为单台云服务器设置多个公网IP
在应用中,有时会遇到用户询问如何使单台云服务器具备多个公网IP的问题。 具体如何操作呢,有了NAT网关这个也不是难题。
26799 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
2512 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
12078 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13897 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
11820 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
4670 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4512 0
+关注
542
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载