这个换币组合算法的时间复杂度是多少？

Question

你好，我刚刚解决了这个 leetcode 问题：https://leetcode.com/problems/coin-change-2/

objective 是为了找到 coins 的不同可能组合的数量，我们可以使用它来生成 amount 假设我们有来自每个面额的无限数量的硬币。

我知道这个问题有一个在 O(amount*len(coins)) 中运行的 DP 解决方案，我可以在下面的解决方案中添加记忆来实现它。

然而，我正在努力寻找以下天真的方法的时间复杂度：

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。

谁能给出时间复杂度的准确形式？指数项到底是什么？或者我如何计算图形中的边和顶点？

Answer 1

假设一种情况，其中数量 n 非常大，而每个硬币的价值与 n 相比非常小，并且让硬币数组的大小为 c。事实上，在最坏的情况下，我们可以假设每个硬币的价值约为 1。在代表您的解决方案构建的调用堆栈的树中，每个节点将分支 c 次。树的每一层都从 n 中减去一枚硬币的价值（在最坏的情况下约为 1），因此树的深度（或高度）将为 n。所以我们正在查看高度为 n 的 c-branch 树。顶点数，V = c^0 + c^1 + c^2 + c^3 + ... + c^(n-1) + c^n。您可以看到这个系列减少到 here。边数 E 的计算是类似的。这个算法有O(c^n)的时间复杂度。

Answer 2

这里有几点需要注意

动态编程是一个概念或想法。它本身并不是一种算法。这是一种用于提高某些算法的运行时间的技术，其中子问题有可能重叠并使用预先计算的结果。 none 的子问题有可能重叠，这是人们谈论的最坏情况的复杂性。
所以让我们继续假设没有子问题重叠，我们采用自上而下的方法，你有 c₁, c₂, ... c_n 作为你的硬币面额

我认为下面的方法可行，

因此自上而下的方法看起来像这样

一些路径将终止为以 0 结尾的叶子。（该方法产生了初始数量的完美分割 k ）。有些没有。

为了复杂起见，我们假设他们都这样做了。

因此，在任何给定级别，您都有 n^level_num 个节点。而且你必须遍历树的每个节点。

最长的路径是您从初始金额 k 中不断删除最小面额的地方。 i.ik/c₁

因此，您的情况下的真实时间复杂度为 O(1+n¹+n²+ ....n^k/c₁)

大多数此类问题都将 1 作为硬币的有效面额（或其他一些小数字）以简化此表达式并使 GP 更易于计算

这个换币组合算法的时间复杂度是多少？

What is the time complexity of this coin changing combination algorithm?

python-3.x

algorithm

recursion

coin-change