擅长:python、mysql、java
<p>在内存使用的峰值,它有N个栈帧,每个栈帧都有一个等待相乘的因子。那需要O(N)内存。你知道吗</p>
<hr/>
<p>这个数字可以用O(1)存储器来计算。你知道吗</p>
<p>如果Python消除了尾部递归,那么下面将使用O(1)内存:</p>
<pre><code>def _nthFib(acc, n):
if n == 1:
return acc
return _nthFin(acc*n, n-1)
def nthFib(n):
if n == 0:
return 0
return _nthFin(1, n)
</code></pre>
<p>如果Python的<code>range</code>是一个真正的迭代器,那么下面使用O(1)内存:</p>
<pre><code>def nthFib(n):
if n == 0:
return 0
acc = 1
for x in range(2, n):
acc *= x;
return acc
</code></pre>