代码之家 › 专栏 › 技术社区 › Raghav salotra

如何计算特定函数在递归中执行的次数

analysis recursion algorithm

Raghav salotra · 技术社区 · 6 年前

这个问题是关于爆破规范的:

cost = [[1, 10, 75, 92],
         [-1, 0, 35, 50],
         [-1, -1, 0, 80],
         [-1, -1, -1, 0]]

def min_cost(source, destination):
   if s==d or s == d-1:
       return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
return mc

当我干同样的事时,我看到Min_Cost(1,3)被执行了2次。我在一本书中读到,作者提到如果我们有10个电台,那么Min_u Cost(1,3)将运行144次。

我们怎么能算出这些数字,而不实际干运行。我知道使用递归方程我们可以计算出函数所花费的时间,但是怎么能说一个特定的函数会被执行这么多次呢?

3 回复 | 直到 6 年前

Gassa 6 年前

虽然我知道你不想让一次枯燥的跑步来数电话,但我还是想先做,看看发生了什么。所以,这里是:

def min_cost(s, d):
    global count
    count += 1
    if s==d or s == d-1:
        return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
    return mc

for n in range (2, 8):
    cost = [[0 for i in range (n)] for j in range (n)]
    count = 0
    min_cost(0, n-1)
    print (str (n) + ': ' + str (count))

输出为:

所以,我们看到d-s=k的调用数是3乘以(k-1)的幂。知道我们要证明什么有时会大大简化寻找证据的过程。

现在,为了证明自己。会的 proof by induction 。首先,请注意 min_cost(s, d) 只取决于 d-s ,而不是关于 s 和 d 。

基础是,因为 d-s=1 ,我们接到一个电话。为了 d-s>1 ,我们只打一个电话,然后从中拨打以下电话:

min_cost(s, s+1) and min_cost(s+1, d)
min_cost(s, s+2) and min_cost(s+2, d)
...
min_cost(s, d-1) and min_cost(d-1, d)

所以,为了 d-s=k ,通话次数 f(k) 是:

f(k) = 1 +
       f(1) + f(k-1) +
       f(2) + f(k-2) +
       ... +
       f(k-1) + f(1)
     = 2 * (f(1) + f(2) + ... + f(k-1))

如果,通过归纳假设,我们已经证明了f(v)=3 ^V 对于所有v<k,则f(k)为:
1+2*(3 ^一 + 3 ^二 +…+ 3 ^K-1 ),即 trivially 三 ^K ,完成我们的证明。

最后,请注意,虽然所提出的算法是指数型的,但基本问题可以在多项式时间内解决,最简单的方法是在o((d-s)^2)中记住我们已经做了所有工作的调用。

Tim B. 6 年前

当使用递归时,有几个选项可以计算该数量。最简单的方法是在递归方法中添加另一个变量,该变量在每次递归时都会增加,在返回该变量的最后一条语句中,它不会增加,而只是返回最后一个值,这将递归“返回”到上层请求。

伪代码示例:

function recursionfunction(x, y, recursioncount) {
    if(expressionIsFalse) {
        recursionfunction(x, y, recursioncount+1);
    } else {
        return recursioncount;
    }
}

print recursionfunction('','', 0);

另一种工作方式是通过引用分配变量、指针或全局变量(取决于编程语言)并递增该计数器。

这对你有帮助吗?

humble_D 6 年前

我认为一个全局变量驻留在函数之外(如果是Java中的一个成员,或者C++/C中的全局VAR),每次调用它时都会增加一个值。