文档章节

【SICP练习】90 练习2.63

NoMasp
 NoMasp
发布于 2015/09/08 21:51
字数 481
阅读 3
收藏 0

练习2.63

这两段代码的区别在于第二段用了迭代,相信可以大大减少计算时间。那么还是先来测试第一小题。需要的代码大家先敲进去。然后来定义图2-16中的三棵树了。

(define tree-1 (make-tree 7 (make-tree 3 (make-tree 1 '() '()) (make-tree 5 '() '())) (make-tree 9 (make-tree '()) (make-tree 11 '() '()))))
(define tree-2 (make-tree 3 (make-tree 1 '() '()) (make-tree 7 (make-tree 5 '() '()) (make-tree 9 '() (make-tree 11 '() '())))))
(define tree-3 (make-tree 5 (make-tree 3 (make-tree 1 '() '()) '()) (make-tree 9 (make-tree 7 '() '()) (make-tree 11 '() '()))))

这些相信大家都会定义的,make-tree的三个参数依次是结点,左右树枝。
对这三棵树,2段代码做6次测试,得到的结果毫无疑问的一致:
(1 3 5 7 9 11)

那么a小题就算完成了,至于b小题涉及到了这两个函数的执行效率,因此我们不得不对它们进行分解展开。

这里写图片描述

这里写图片描述

我们就用第一棵树,分别用两个函数来演示展开过程。
展开的过程真是太漫长了,但收获也是有的,我们发现其到最后一共有6次append,同时也有6次cons,而tree-1的节点一共有6个(当然了,tree-2和tree-3也是6个结点)。因此结论是使用append和cons的次数和结点的个数是正相关的。而append的复杂度比cons高,前者为n后者为1,因此这个函数的复杂度为n方。

tree->list-2的展开过程类似,其复杂度为n。因此虽然两者最终结果一样,但第二个函数更快速。



感谢访问,希望对您有所帮助。 欢迎关注或收藏、评论或点赞。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp


版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/44079409

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
CentOS6.5升级autoconf版本,解决”Autoconf version 2.64 or higher is required“错误

版权声明:本文为博主原创文章,如需转载,必须注明原文链接及作者。 安装软件时提示说需要Autoconf 2.64或更高的版本: [python] view plain copy [root@wslu-cs wslu]# autoconf configure...

jbaowei2000
2017/02/13
0
0
一个案例看机器学习建模基本过程

machine learning for credit scoring Banks play a crucial role in market economies. They decide who can get finance and on what terms and can make or break investment decisions. ......

czl389
2017/08/28
0
0
SQLServer2012子查询练习

表结构与数据:https://github.com/XuePeng87/TSQLV4 练习1 练习内容:编写一个查询,返回Orders表中可以查到的活动最后一天的所有订单 涉及的表:Sales.Orders 输出的列:orderid, orderdat...

杰克鹏仔
2016/11/10
40
0
SQLServer2012子查询练习

表结构与数据:https://github.com/XuePeng87/TSQLV4 练习1 练习内容:编写一个查询,返回Orders表中可以查到的活动最后一天的所有订单 涉及的表:Sales.Orders 输出的列:orderid, orderdat...

巧乐兹
2016/11/05
123
0
Dnsmasq 2.64 发布,DNS服务工具

DNS轻量级缓存服务dnsmasq发布2.64版本。2012-12-04 上一个版本是2012-08-17的2.63。经过1个RC.可以用它做DNS代理缓存及hosts主机名的集中管理使用(也可以做DHCP),非常好用。 此版本增加了-...

fei
2012/12/05
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

IT小白们进击前端工程师的学习路线:编辑器,基础进阶学习要点,框架

一、HTML、CSS基础、JavaScript语法基础。学完基础后,可以仿照电商网站(例如京东、小米)做首页的布局。 二、JavaScript语法进阶。包括:作用域和闭包、this和对象原型等。相信我,JS语法,...

梦想编程
24分钟前
97
0
ZhaoWei-2020-01-19

Dubbo Dubbo是一个分布式服务治理框架,提供高性能和透明化的RPC远程服务调用方案及 SOA架构治理方案。 远程通信 提供对多种基于长连接的NIO框架抽象封装,包括多种线程模型,序列化,以及 ...

SuSheePark
27分钟前
30
0
Python文件的常见标头格式是什么?

在有关Python编码准则的文档中,我遇到了以下Python源文件的头格式: #!/usr/bin/env python"""Foobar.py: Description of what foobar does."""__author__ = "Barack Obama"__cop......

javail
31分钟前
40
0
Linux 安装 jq

先下载jq安装包 https://stedolan.github.io/jq/download/将下载的安装包文件jq-linux64 拷贝到服务器下 wget -O jq https://github.com/stedolan/jq/releases/download/jq-1.6/jq-li......

乐易林谷
35分钟前
82
0
Elasticsearch深入:Refresh和Flush区别@

整体流程: 数据首先写入Buffer缓冲和Translog日志文件中。 当你写一条数据doc的时候,一方面写入到mem buffer缓冲中,一方面同时写入到translog日志文件中。 buffer满了或者每隔1秒(默认1秒...

HLee
39分钟前
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部