我们如何计算朴素斐波那契的调用次数?
How do we calculate number of calls in naive fibonaci?
所以下面不是优化的斐波那契函数:
sub fib {
my ( $n ) = @_;
return 1 if( $n == 1 || $n == 2 );
return fib( $n - 1 ) + fib( $n - 2 );
}
当我们试图找到 20 的斐波那契时,我实际上打印了 fib(3)
被调用的次数。
是2584。fib(2)
被称为4181。
据我所知,这个算法表现出指数行为。
我的问题是,如果没有 在代码中实际保留一个计数器并打印函数调用,我如何计算 fib(3)
会被调用 2584 次 ?指数部分是如何计算的?
我相信这是 Target - desired number + 1
处的斐波那契数,所以在询问 fib(3)
在 fib(20)
中被调用的次数是多少的情况下,它将是 fib(20 - 3 + 1)
(即fib(18) = 2584
)。
如果你画出代表斐波那契调用的树,你可以自己看到!
fib(i)
仅从 fib(i+1)
和 fib(i+2)
直接调用,并且每次调用一次。
因此calls(i)
(fib(i)
的调用次数)等于calls(i+1) + calls(i+2)
因此,如果我们从 m
开始并尝试计算 calls(n)
,我们将得到以下结果:
calls(m) = 1 (= fib(1))
calls(m-1) = 1 (= fib(2))
calls(m-2) = 2 (1+1) (= fib(3))
calls(m-3) = 3 (1+2) (= fib(4))
calls(m-4) = 5 (2+3) (= fib(5))
...
这就是我们要计算第 m-n+1
个数字的斐波那契数列
(要了解为什么它恰好是 m-n+1
,请考虑何时 n = m
,它应该是 fib(1)
)。
calls(n) = fib(m-n+1)
我们可以在这里使用优化的斐波那契函数来有效地(在线性时间内)计算 fib(m-n+1)
,这将是未优化版本中 fib(n)
的调用次数。
对于您的示例,如果您调用 fib(20)
,fib(3)
会被调用 2584
次。
fib(20-3+1) = fib(18) = 2584
.
注:calls(1) = calls(3)
(因为fib(2)
不调用fib(1)
),所以这是一个特例。
Dukeling 向您展示了 fib(3)
被调用次数的顺序:fib(20) (m)
被调用一次,fib(19) (m-1)
被调用一次,然后 fib(18)
被调用一次时间 fib(19)
或 fib(20)
被调用,总计 1+1.
当我们沿着序列向下移动以查找 fib(3)
被调用的次数时,您会注意到数字(和计算)与斐波那契数列本身相对应。我们从 20 下降到 3,所以 m - n + 1 步,每一步都对应下一个斐波那契数。等到调用了多少次fib(3)
(fib(n))时,序列已经到了第m-n+1
个斐波那契数,对应调用了多少次f(n)
在未优化的递归期间。
所以下面不是优化的斐波那契函数:
sub fib {
my ( $n ) = @_;
return 1 if( $n == 1 || $n == 2 );
return fib( $n - 1 ) + fib( $n - 2 );
}
当我们试图找到 20 的斐波那契时,我实际上打印了 fib(3)
被调用的次数。
是2584。fib(2)
被称为4181。
据我所知,这个算法表现出指数行为。
我的问题是,如果没有 在代码中实际保留一个计数器并打印函数调用,我如何计算 fib(3)
会被调用 2584 次 ?指数部分是如何计算的?
我相信这是 Target - desired number + 1
处的斐波那契数,所以在询问 fib(3)
在 fib(20)
中被调用的次数是多少的情况下,它将是 fib(20 - 3 + 1)
(即fib(18) = 2584
)。
如果你画出代表斐波那契调用的树,你可以自己看到!
fib(i)
仅从 fib(i+1)
和 fib(i+2)
直接调用,并且每次调用一次。
因此calls(i)
(fib(i)
的调用次数)等于calls(i+1) + calls(i+2)
因此,如果我们从 m
开始并尝试计算 calls(n)
,我们将得到以下结果:
calls(m) = 1 (= fib(1))
calls(m-1) = 1 (= fib(2))
calls(m-2) = 2 (1+1) (= fib(3))
calls(m-3) = 3 (1+2) (= fib(4))
calls(m-4) = 5 (2+3) (= fib(5))
...
这就是我们要计算第 m-n+1
个数字的斐波那契数列
(要了解为什么它恰好是 m-n+1
,请考虑何时 n = m
,它应该是 fib(1)
)。
calls(n) = fib(m-n+1)
我们可以在这里使用优化的斐波那契函数来有效地(在线性时间内)计算 fib(m-n+1)
,这将是未优化版本中 fib(n)
的调用次数。
对于您的示例,如果您调用 fib(20)
,fib(3)
会被调用 2584
次。
fib(20-3+1) = fib(18) = 2584
.
注:calls(1) = calls(3)
(因为fib(2)
不调用fib(1)
),所以这是一个特例。
Dukeling 向您展示了 fib(3)
被调用次数的顺序:fib(20) (m)
被调用一次,fib(19) (m-1)
被调用一次,然后 fib(18)
被调用一次时间 fib(19)
或 fib(20)
被调用,总计 1+1.
当我们沿着序列向下移动以查找 fib(3)
被调用的次数时,您会注意到数字(和计算)与斐波那契数列本身相对应。我们从 20 下降到 3,所以 m - n + 1 步,每一步都对应下一个斐波那契数。等到调用了多少次fib(3)
(fib(n))时,序列已经到了第m-n+1
个斐波那契数,对应调用了多少次f(n)
在未优化的递归期间。