空间与时间的方案代码分析
我正在学习 MIT 在线讲座，学习经典的 6.001 课程：计算机程序的结构和解释。
我试图了解根据内存使用与执行时间来分析代码复杂性。在前几堂课中，他们在斐波那契数列方案中提出了一个解决方案。
他们在视频中提出的解决方案具有内存空间随x（线性递归性能）增长的特点，这给斐波那契数列带来了一个大问题。当您尝试找到更大的斐波那契数时，递归所需的空间就会变得巨大。
他们建议尝试找到一种获得线性迭代性能的方法，其中所需的内存空间在整个计算过程中保持不变并且不依赖于 x。
我的解决方案如下。我的具体问题是，下面我的方案代码的性能分析（在内存使用与执行时间方面）是怎样的？
(define (fib x)
(define (fib-helper target total current-index i-2 i-1)
(if (> current-index target)
(if (= target 1)
0
total)
(fib-helper target
(+ i-2 i-1)
(+ current-index 1)
i-1
(+ i-2 i-1))))
(fib-helper x 1 3 0 1))
I'm working my way through the online MIT lectures for the classic 6.001 course: The Structure and Interpretation of Computer Programs.
I'm trying to gain an understanding of analyzing code complexity in terms of memory usage vs. execution time. In the first few lectures, they present a solution in Scheme for the Fibonacci Series.
The solution they present in the videos is one that has the characteristic of growing in memory space with x (Linear Recursion performance), which presents a big problem with the Fibonacci Series. As you try to find a larger Fibonacci number, the space required for the recursion becomes huge.
They suggest trying to find a way to get Linear Iteration performance, where the memory space needed remains constant throughout the computation and doesn't depend on x.
My solution is below. My specific question is, what is the performance analysis of my Scheme code below, in terms of memory usage vs. execution time?
(define (fib x)
(define (fib-helper target total current-index i-2 i-1)
(if (> current-index target)
(if (= target 1)
0
total)
(fib-helper target
(+ i-2 i-1)
(+ current-index 1)
i-1
(+ i-2 i-1))))
(fib-helper x 1 3 0 1))
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
好吧，考虑到
(fib n)导致n-1调用fib-helper，您的解决方案以线性时间运行。 fib-helper 每次迭代仅调用自身一次，并且每次迭代都是尾调用，因此您的程序在恒定空间中运行。这意味着，在占用相同内存量的情况下，对
(fib 1000)的调用只需花费(fib 100)的大约十倍的 CPU 时间。Well, considering that
(fib n)causesn-1calls tofib-helper, your solution runs in linear time.fib-helperonly calls itself once for each iteration, and each iteration is a tail call, so your program runs in constant space.This means that a call to
(fib 1000)should only take about ten times the CPU time of(fib 100)while taking up the same amount of memory.看到您对 fib-helper 的调用是一个正确的尾部调用，这将在恒定的空间中运行。
不过我无法帮助你缩短执行时间:)
Seeing your call to
fib-helperis a proper tail call, this will run in constant space.I cant help you with execution time though :)