【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


目录
相关文章
|
算法 安全 Go
Go语言哈希函数不可不知的N个实战技巧
Go语言哈希函数不可不知的N个实战技巧
454 0
|
存储 算法
线性表的链式表示及实现
线性表的链式表示及实现
137 0
线性表的链式表示及实现
|
6天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
17天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1320 7
|
5天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
296 129
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
4天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
16天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1392 87
|
4天前
|
JavaScript Java 大数据
基于JavaWeb的销售管理系统设计系统
本系统基于Java、MySQL、Spring Boot与Vue.js技术,构建高效、可扩展的销售管理平台,实现客户、订单、数据可视化等全流程自动化管理,提升企业运营效率与决策能力。