python - 贪心递归算法的时间复杂度

coins = [1, 5, 10, 21, 25] coinsArraySize = len(coins) change = 63 pickedCoins = [] def findMin(change, i, pickedCoins): if (i>=0): if (change >= coins[i]): pickedCoins.append(coins[i]) findMin(change - coins[i], i, pickedCoins) else: findMin(change, i-1, pickedCoins) findMin(change, coinsArraySize-1, pickedCoins)

是什么n？运行时间取决于数量和特定的硬币。例如，假设您有一百万个硬币，从 1 到 1,000,000，并尝试为 1 找零。代码将在最终找到它可以使用的最大硬币 (1) 之前进行一百万个递归级别。如果你只有一枚硬币 ( 1 ) 并尝试找零 1,000,000，那么最后同样的事情 - 然后你会立即找到硬币，但要深入一百万层，一百万次挑选该硬币。

这是一个非递归版本，对这两个方面都进行了改进：使用二分搜索找到下一个可用的硬币，一旦找到合适的硬币，就尽可能多地使用它。

def makechange(amount, coins):
    from bisect import bisect_right
    # assumes `coins` is sorted. and that coins[0] > 0
    right_bound = len(coins)
    result = []
    while amount > 0:
        # Find largest coin <= amount.
        i = bisect_right(coins, amount, 0, right_bound)
        if not i:
            raise ValueError("don't have a coin <=", amount)
        coin = coins[i-1]
        # How many of those can we use?
        n, amount = divmod(amount, coin)
        assert n >= 1
        result.extend([coin] * n)
        right_bound = i - 1
    return result

如果要求找一百万只硬币是 1仍然需要O(amount)时间，但因为它必须建立一个包含一百万份 1 的结果列表。如果有一百万硬币并且你要求找零，但是，是O(log2(len(coins)))时候了。第一个可以通过将输出格式更改为 dict 来削减，将硬币映射到该硬币的使用次数。然后第一个案例将被削减到O(1)时间。

事实上，它所花费的时间与结果列表的长度成正比，加上一些（通常是微不足道的）用于一些二进制搜索的时间，这些时间等于使用的不同硬币的数量。因此，“坏情况”是需要使用每枚硬币的情况；例如，

>>> coins = [2**i for i in range(10)]
>>> makechange(sum(coins), coins)
[512, 256, 128, 64, 32, 16, 8, 4, 2, 1]

这基本上就是在O(n + n log n)哪里。nlen(coins)

寻找最佳解决方案

正如@Stef 在评论中指出的那样，贪心算法并不总是能找到最少数量的硬币。这要困难得多。通常的方法是通过动态编程，最坏的情况O(amt * len(coins))时间。但这也是最好的情况：它“自下而上”地工作，找到最少数量的硬币达到 1，然后是 2，然后是 3，然后是 4，...，最后是amt。

所以我将建议一种不同的方法，使用广度优先树搜索，从初始数量向下直到达到 0。最坏情况下O()的行为是相同的，但最好情况下的时间要好得多。对于评论：

mincoins(10000, [1, 2000, 3000])

在找到最佳 4 币解决方案之前，它会查看少于 20 个节点。因为它是广度优先搜索，它知道不可能有更短的路径到根，所以可以立即停止。

举一个最坏的例子，试试

mincoins(1000001, range(2, 200, 2))

所有硬币都是偶数，因此它们的任何集合都不可能与奇数目标相加。在意识到 0 无法到达之前，树必须扩展 50 万级深。但是，虽然高级别的分支因子是O(len(coins))，但整个扩展树中的节点总数以amt + 1（鸽洞原则：dict 不能有多个amt + 1键，因此超出此范围的任何节点数必然是重复的目标和所以一旦生成就会被丢弃）。所以，实际上，这种情况下的树很快就会变宽，但很快就会变得很窄很深。

另请注意，这种方法可以很容易地重建总和为的最小硬币集合amt。

def mincoins(amt, coins):
    from collections import deque
    coins = sorted(set(coins)) # increasing, no duplicates

    # Map amount to coin that was subtracted to reach it.
    a2c = {amt : None}
    d = deque([amt])
    while d:
        x = d.popleft()
        for c in coins:
            y = x - c
            if y < 0:
                break # all remaining coins too large
            if y in a2c:
                continue # already found cheapest way to get y
            a2c[y] = c
            d.append(y)
            if not y:    # done!
                d.clear()
                break
    if 0 not in a2c:
        raise ValueError("not possible", amt, coins)
    picks = []
    a = 0
    while True:
        c = a2c[a]
        if c is None:
            break
        picks.append(c)
        a += c
    assert a == amt
    return sorted(picks)

python - 贪心递归算法的时间复杂度

问题描述

解决方案

寻找最佳解决方案

推荐阅读