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

Question

这个问题参考了打击代码:

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_cost(1,3)会运行144次.

如何在不实际干运的情况下弄清楚这些数字.我知道使用递归方程我们可以计算出函数所花费的时间但是怎么能说这个特定的函数会被执行很多次呢？

Answer 1

虽然我知道你不想让干跑只计算电话,但我还是先做,只是为了看看发生了什么.所以,这里是:

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))

输出是:

2: 1
3: 3
4: 9
5: 27
6: 81
7: 243

因此,我们看到ds = k的调用次数是(k-1)的幂的3.知道我们必须证明什么有时会大大简化查找证据.

现在,到证明本身.它将通过归纳证明.首先,请注意电话的数量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}),这是一个简单的 3 ^k,完成我们的证明.

最后,请注意,虽然所提出的算法是指数的,但是基本问题可以在多项式时间内解决,最简单的是在O((ds)^ 2)中通过记忆我们已经完成所有工作的调用.