Какова временная сложность этого комбинированного алгоритма обмена монет?
Здравствуйте, я только что решил этот вопрос с литкодом: 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
Предположим, что сумма 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).
Несколько вещей, которые следует отметить здесь
- Динамическое программирование — это концепция или идея. Это не алгоритм сам по себе. Это метод, используемый для увеличения времени выполнения некоторых алгоритмов, где существует вероятность перекрытия подзадач и использования предварительно вычисленных результатов. Существует вероятность того, что ни одна из подпроблем не перекрывается, и это наихудшая сложность, о которой говорят люди.
- Итак, давайте продолжим с предположением, что никакие подзадачи не перекрываются, и мы используем подход сверху вниз, и у вас есть с1, с2, ... сn в качестве номинала монет.
I думать ниже будет работать,
Поэтому подход сверху вниз будет выглядеть так
Некоторые пути заканчиваются как листья, заканчивающиеся на 0. (этот метод дал идеальное сокращение начальной суммы к ). Некоторые этого не сделали.
Для сложности предположим, что это сделали все.
Таким образом, на любом заданном уровне у вас есть узлы пlevel_num. И вам нужно пройти через каждый узел дерева.
Самый длинный путь будет там, где вы продолжали удалять наименьшую деноминацию из начальной суммы к. i.i к/с1
Поэтому истинная временная сложность в вашем случае будет О(1+n1+n2+....nk/c1).
В большинстве таких задач допустимым номиналом монеты является 1 (или какое-то другое небольшое число), чтобы упростить это выражение и облегчить вычисление GP.