scala - 计算变化的时间复杂度

Question

我有一个类似的问题要链接：使用递归的scala中的硬币兑换算法

该代码是递归的，如下所示：

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 对此有很好的解释。