本小节主要介绍了阶的概念,与算法中计算时间和空间复杂度类似。给了一个过程:
<!---->(define (cube x)(* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
这个过程用于求弧度的正弦值
a)在求值(sine 12.15)时,p过程将被使用多少次?
答:
(sine 12.15)->(p (sine 4.05))
->(p (p (sine 1.35)))
->(p (p (p (sine 0.45))))
->(p (p (p (p (sine 0.15)))))
->(p (p (p (p (p (sine 0.05))))))
显而易见,p被调用了5次
b)由过程sine所产生的计算过程使用的空间和步数增长的阶是多少?
从上面的分析可以看出,空间和步数的增长都跟p的调用次数成正比,也就是与递归次数是线性关系。
当|a|<0.1时,递归次数为0
当|a|>0.1时,递归的最大次数满足条件:|a|/3**num<0.1,这里的3**num采用ruby记法表示3的num次方,此时递归次数num<log3(10a)
因此,对于空间和步数的阶应该为:R(n)=(theta)lg(n)
分享到:
相关推荐
SICP习题解答,主要第一章的内容习题答案
SICP 习题答案 计算机程序的构造和解释 1-3章 习题答案
NULL 博文链接:https://pengpeng.iteye.com/blog/1344689
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 !!!download>>>https://github.com/wizardforcel/sicp-py-zh
SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版
SICP-Python版本
SICP 使用的scheme解释器 以前叫DrScheme
sicp 2.2.4节图形语言的racket程序包,配置路径,C:\Users\Administrator\AppData\Roaming\Racket
Python SICP epub版本,很适合学习抽象的思想,用Python版本比lisp更实用
SICP 解题集
SICP CHINESE ENGLISH THE SECOND EDITION SICP CHINESE ENGLISH THE SECOND EDITION
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 download : https://github.com/wizardforcel/sicp-py-zh
资源来自pypi官网。 资源全名:sicp-0.0.1b102.dev4.tar.gz
sicp 2ed高清pdf,以及相对应的mit课程资料及习题答案打包,中文版的视频在这里http://i.youku.com/i/UNTcxODk3ODQw/videos?spm=a2hzp.8244740.0.0
sicp-in-python(中文版+英文版)PDF 背景. SICP 全称Structure and Interpretation of Computer Programs,翻译过来叫《计算机程序的构造和解释》使用python
资源名称:sicp 和 操作系统:精髓与设计原理第七版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
经典书籍《计算机程序的构造与解释》,UCB热门课程CS61a的官方教材
#SICP SICP解决方案
超声高速铣削和高速铣削高体分SiCp/Al MMCs的粗糙度研究,向道辉,岳广喜,结合正交分析和单因素分析对高体分SiCp/MMCs在超声高速和高速铣削两种实验条件下的粗糙度进行分析,研究铣削速度、进给量和切削深度