递归函数的时间复杂度计算

Question

所以我有下面的代码，我不知道如何获得它的递归关系。我最终需要计算代码的时间复杂度。

int countChangeRec(int amount, array<int, 5>coins, int n)
{
    if(amount == 0)
        return 0;
    if((amount > 0 && n < 0) || (amount < 0))
        return INT_MAX;

    if(amount < coins[n-1])
        return countChangeRec(amount, coins, n-1);
    return min(countChangeRec(amount, coins, n-1), 
        amount / coins[n-1]+ countChangeRec(amount%coins[n-1], coins, n));
}

提前感谢您对如何进行这项工作的任何建议。

Answer 1

您的代码不能解决问题。如果你想计算硬币的最小数量，这里有一个例子打破了你的解决方案

coins = {1,9,10}
amount = 37

您的解决方案返回答案5，但正确答案是4

9*3 + 1*10