Расчет времени Сложность функции рекурсии

Итак, у меня есть следующий код, и я не могу понять, как получить отношение повторения для него. Наконец, мне нужно рассчитать временную сложность кода.Расчет времени Сложность функции рекурсии

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)); 
}

Заранее благодарим за любые советы о том, как это сделать.

источник

2015-02-21 shanilpuri

Кроме того, любые оптимизации будут оценены , Необходимо решить с помощью рекурсии. Я знаю решение DP, но любые оценки в вышеприведенном методе будут оценены. – shanilpuri

Это может быть очевидно, но, пожалуйста, добавьте, как вы вызываете функцию в первый раз, чтобы начать работу. – yzt

Кроме того, я могу ошибаться, но я думаю, что ваш код имеет ошибку, когда 'n' является (или становится) нулем, а' amount' отличен от нуля, потому что вы получаете доступ к «монетам [-1]». – yzt

Ваш код не разрешает проблему. Если вы хотите, чтобы вычислить минимальное количество монет, вот пример, который разрушает ваше решение

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

Ваше решение вернуть ответ 5, но правильный ответ 4

9*3 + 1*10

источник

2015-03-18 12:11:38

Расчет времени Сложность функции рекурсии

ответ

Смежные вопросы