计时变化

Question

的复杂性我有一个类似的问题链接：coin change algorithm in scala using recursion

的代码是递归的样子：

def countChange(money: Int, coins: List[Int]): Int = { 
    def count(capacity: Int, changes: List[Int]): Int = { 
      if(capacity == 0) 1 
      else if(capacity < 0) 0 
      else if(changes.isEmpty && capacity >=1)0 
      else count(capacity, changes.tail) + count(capacity - changes.head, changes) 
    } 
count(money, coins) 
} 

我的问题是如何分析该算法的时间复杂度？谢谢！

Answer 1

这是随输入指数增长的树递归形式。 SICP has very nice explanation about this。