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 には、これについて非常に優れた説明があります。