时间戳

首页 > 解决方案 > 这个硬币找零算法的时间复杂度是多少？

algorithm - 这个硬币找零算法的时间复杂度是多少？

问题描述

我解决了 leetcode https://leetcode.com/problems/coin-change-2/上的硬币兑换问题。

这是我写的代码：

    def change(self, amount: int, coins: List[int]) -> int:
        def helper(amount, coins, ind):
            if amount == 0:
                return 1
            if amount < 0:
                return 0
            if (amount, ind) in dp:
                return dp[(amount, ind)]

            res = 0
            for i in range(ind, len(coins)):
                res  += helper(amount - coins[i], coins, i)

            dp[(amount, ind)] = res
            return res

        coins.sort()
        dp = {}
        return helper(amount, coins, 0)

而且我注意到我在使用记忆分析算法的时间复杂性方面遇到了很多困难。例如，在这种情况下，我认为我们有amount * number of coins子问题——>因此，算法O(amount * number of coins * number of coins)在我的因子中运行的第二个硬币数量来自这样一个事实，即对于每个子问题，我们必须通过循环for i in range(ind, len(coins)):来将结果相加.

然而，似乎这个解决方案实际上O(amount * number of coins)来自我阅读的内容（自下而上的方法是O(amount * number of coins)）。什么是正确答案？

我似乎在递归函数内的循环中遇到了很多困难，有时我们似乎将它们计算在时间复杂度中，而其他时候它们已经在子问题中“定价”，就像我怀疑这里的情况一样。

标签： algorithmrecursiontime-complexitymemoizationcoin-change

解决方案

正如 Enrico Borba 所说：

你的分析对我来说似乎是正确的。您的表格中有O(amount * number of coins)单元格，并且要计算表格中的任何单元格，您需要运行一个循环（硬币数量）次。您编写的代码具有这种复杂性。很可能存在具有 O（数量 * 硬币数量）复杂度的不同算法。

——恩里科·博尔巴

推荐阅读