这个问题是与下面的代码有关:
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)被执行了两次。我在一本书中读到过作者提到,如果我们有10个站点,则min_cost(1, 3)将运行144次。
我们如何在不实际运行的情况下找出这些数字?我知道使用递归方程我们可以找出函数所需的时间,但是我们如何说特定的函数将执行这么多次?
当我dry run相同代码时,我发现min_cost(1,3)被执行了两次。我曾在一本书中阅读到,如果有10个站点,则min_cost(1,3)将运行144次。那么,我们如何在实际干运行之前计算这些数字?虽然我们可以使用递归公式来计算函数的运行时间,但我们如何确定特定函数将被执行的次数呢?