Какова временная сложность этого алгоритма комбинации изменения монет? - PullRequest
Новая
       53

Какова временная сложность этого алгоритма комбинации изменения монет?

0 голосов
/ 29 мая 2019

Здравствуйте. Я только что решил этот вопрос с кодом leetcode: https://leetcode.com/problems/coin-change-2/

Цель состоит в том, чтобы найти количество различных возможных комбинаций coins, которые мы можем использовать для генерации amount, предполагая, что у нас бесконечное числоколичество монет от каждого номинала.

Я знаю, что у этой проблемы есть решение DP, которое работает в O(amount*len(coins)), и я могу добавить памятку к решению ниже для достижения этого.

Однако я изо всех силчтобы найти временную сложность наивного подхода ниже: 

def change(amount, coins):
    def helper(amount, coins, id):
        if amount == 0:
            return 1
        res = 0
        for i in range(id, len(coins)):
            if coins[i] <= amount:
                res += helper(amount - coins[i], coins, i)
        return res

    res = helper(amount, coins, 0)
    return res

Итак, что я на самом деле делаю, так это DFS, где я стараюсь максимально использовать первую монету, прежде чем вернуться назад и перейти к следующей монете.Поэтому, как только я начинаю использовать следующую монету, я не могу снова использовать первую -> это позволяет мне не учитывать перестановки в моем результате.

Я знаю, что временная сложность этого решения O(exponential)и я также знаю, что это O(V + E), потому что это DFS.

Может кто-нибудь дать точную форму сложности времени?Что такое экспоненциальный член точно?Или как подсчитать ребра и вершины в моем графике?

Ответы [ 2 ]

1 голос
/ 29 мая 2019

Предположим, что количество n очень велико, а стоимость каждой монеты очень мала по сравнению с n, и пусть размер массива монет c. На самом деле, в худшем случае мы можем принять значение каждой монеты равным 1. В дереве, представляющем стек вызовов, который создает ваше решение, каждый узел будет разветвляться c раз. Каждый уровень дерева вычитает значение монеты (в худшем случае около 1) из n, поэтому глубина (или высота) дерева будет n. Итак, мы смотрим на дерево c-ветви с высотой n. Количество вершин, V = c ^ 0 + c ^ 1 + c ^ 2 + c ^ 3 + ... + c ^ (n-1) + c ^ n. Вы можете увидеть, что эта серия уменьшает до здесь . Расчет числа ребер E аналогичен. Этот алгоритм имеет O (c ^ n) сложность времени.

0 голосов
/ 29 мая 2019

Здесь следует отметить несколько вещей

  1. Динамическое программирование - это концепция или идея.Это не алгоритм сам по себе.Это методика, используемая для увеличения времени работы некоторых алгоритмов, где существует вероятность перекрытия подзадач и использования предварительно вычисленных результатов.Существует вероятность того, что ни одна из подзадач не пересекается, и это наихудшая сложность, о которой говорят люди.
  2. Итак, давайте продолжим с предположением, что ни одна из подзадач не пересекается, и мы используем подход сверху вниз, и у вас есть c 1 , c 2 , ... c n в качестве монет достоинства

I думаю сработало бы нижеприведенное,

Поэтому подход сверху вниз будет выглядеть так:

enter image description here

Некоторые пути заканчиваются как листья, которые заканчиваются на 0. (этот метод дал идеальное сокращение начального значения k ).Некоторые этого не сделали.

Ради сложности, давайте предположим, что все они сделали.

Так что на любом данном уровне у вас есть n level_num узлы.И вы должны пройти через каждый узел дерева.

Самый длинный путь - это то место, где вы продолжали удалять наименьшее номинал из начальной суммы k .ii k / c 1

Следовательно, сложность истинного времени в вашем случае будет O (1 + n 1 + n 2 + .... n k / c 1 )

Большинство таких проблем имеют 1 в качестве действительного наименованиямонета (или другое небольшое число), чтобы упростить это выражение и облегчить вычисление ГП

...