Анализ сложности времени первого поиска глубины с возвратом - PullRequest
Новая
       29

Анализ сложности времени первого поиска глубины с возвратом

0 голосов
/ 22 апреля 2019

Я написал следующий алгоритм для задачи замены монет, в котором я хочу найти все возможные комбинации чисел, которые составляют некоторую сумму.

Числа, которые можно использовать, являются простыми числами <= сумма, включая саму сумму, независимо от того, является ли сумма простым числом. Помимо указания суммы, экземпляр проблемы также может ограничивать количество монет, которые можно использовать (или диапазон количества монет, которые можно использовать). </p>

Привет,

Я написал следующую рекурсивную функцию для решения задачи. Сейчас я пытаюсь проанализировать сложность времени. Настройка рекуррентного отношения, похоже, не работает для этой проблемы. Тем не менее, я думаю, что сложность времени должна быть примерно 2 ^ n. Однако я не уверен, как это явно показать. Если бы кто-нибудь мог помочь или указать мне правильный путь, было бы здорово! 

def get_change(coins, amount, max_index, coins_left, upper_bound):

    # base case -> a solution has been found when amount is 0 and valid number of coins has been used
    if amount == 0 and (coins_left in range(0, upper_bound+1)):
        return 1

    count = 0

    i = 0

    # for each of the coins in the list from index 0 to max_index, call the function again with adjusted parameters
    # and add the return value to the current count of solutions
    while i <= max_index and coins[i] <= amount and coins_left > 0:
        count += get_change(coins, amount -
                            coins[i], i, coins_left-1, upper_bound)
        i += 1

    return count
...