python - 这段代码关于递归算法的时间复杂度是多少

Question

我已经进行了货币兑换问题，例如，用尽可能少的硬币兑换一定数量的货币。可用的面额有：1,3 和 4。即使是 100 等少量面额也需要很长时间。复杂度是 2^n 吗？

def moneychange_rec(money,coins):
   if money == 0:
       return table[money]
   else:
       for coin in coins:
           if money>=coin:
               table[money] = min(table[money],1 + moneychange_rec(money-coin,coins))
   return table[money]
money = 11
table = [0]+[money+1]*money
print(table)
coins = [1,3,4]

moneychange_rec(money,coins)

标签： pythonrecursiondynamic-programming

Answer 1

输入大小n与表示值需要多少位有关money。但是，递归深度与值本身有关。因此，您的递归深度可能是指数的，因此算法是O(2**n).

换个角度看：将金额从 100 倍增至 200 倍，您的算法所花费的时间大约会增加一倍（或者至少，递归深度大约会增加一倍）。但一般来说，将一个值加倍会使表示该数字所需的位数最多增加 1。