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

Question

Я написал рекурсивную функцию, которая берет массив положительных целых чисел (> 0) (denominations) и целочисленное значение (amount) и возвращает количество способов, с помощью которых можно получить значение, используя только целые числа в массиве. Так, например, массив целых чисел можно рассматривать как изменение и целочисленное значение как сумму денег, которую вы должны заплатить. И функция возвращает количество способов оплаты кассира. Например:

amount = 4 и denominations = [1,2,3,4]

Это должно вернуть 5

Я проверил свою функцию и она отлично работает. При вызове функции, аргументы acc и index передаются как 0. Вот функция:

public int count_number_of_ways(int amount, int acc, int index, int[] denominations) { 

     if (acc > amount) return 0; 

     if (amount == acc) return 1; 


     int len = denominations.length; 
     int count = 0; 

     while (acc < amount) { 


      for (int i = index + 1; i < len; i++) { 


       count += count_number_of_ways(amount, acc + denominations[i], i, denominations); 


      } 

      acc += denominations[index]; 

      if (acc > amount) return count + 0; 

      if (acc == amount) return count + 1; 

     } 

     return count + 0; 


} 

Я пытался вычислить временную сложность этой функции, но врезался в кирпичную стену. Рекурсивный вызов находится внутри цикла for, который находится внутри цикла while, и это создавало для меня что-то непонятное. Может ли кто-нибудь помочь мне определить временную сложность для этой функции?

Answer 1

Вообще говоря, в худшем случае, вы будете тратить время, пропорциональное (amount/denominations[0]) * (amount/denominations[1]) * ... * (amount/denominations[n]), где п - количество наименований.

Это потому, что вы просматриваете все подсчеты для каждого из ваших наименований. И максимальное количество для определенного номинального номера i - amount/denominations[i].

В реальном случае вы останавливаете процесс раньше, но я не думаю, что он меняет O ((amount/geometric_average_denomination)^n).

Тем не менее, можно избежать экспоненциального времени. Для этого вы можете использовать подход с динамическим программированием. Вот моя версия вашего алгоритма требует O (количество * п):

public static int count_number_of_ways(int amount, int index, Integer[][] cache, int[] denominations) { 
    if (cache == null) 
     cache = new Integer[denominations.length][amount + 1]; 
    if (amount == 0) { 
     int ret = 1; 
     cache[index][amount] = ret; 
     return ret; 
    } 
    if (cache[index][amount] != null) { 
     return cache[index][amount]; 
    } 
    int ret = 0; 
    if (index + 1 < denominations.length) 
     ret += count_number_of_ways(amount, index + 1, cache, denominations); 
    if (amount >= denominations[index]) 
     ret += count_number_of_ways(amount - denominations[index], index, cache, denominations); 
    cache[index][amount] = ret; 
    return ret; 
} 

Идея заключается в том, чтобы заполнить матрицу размера [п] [сумма], где каждый элемент (I, J) является число решений для amount = j, используя подмножество наименований с индексами> = i. Вы заполняете каждый элемент этой матрицы cache только один раз и повторно используете его позже, если он уже определен.

Используйте это нравится:

int ret = count_number_of_ways(amount, 0, null, denominations)