python - 这个算法的复杂性用大O表示法？

Question

def ways(n, coin):
    if n < 0 or len(coin) == 0:
        return 0
    if n > 0:
        return ways(n, coin[:-1]) + ways(n-coin[-1], coin)
    return 1

这样调用:

ways(100, [1, 5, 10, 25, 50]) 输出为 292

该算法计算仅使用 50, 25, 10, 5, 1 即可兑换 100 美元的方法数。最初的问题使用 1 美元和 50 美分、25 美分等......但我已经简化了乘以 100。

我的问题如下。 big-o 复杂度是多少？

该算法似乎以 2 倍分支，但其不完全是 O(2^N)，如输入 N= 且深度大于 292 所示5.

我注意到它可以分支的方式数量取决于。例如，一种可能的方式可以是从n=100，到n=50，到n=0。两个分支，另一种方式是 n=50、n=25、n=0 等等。我知道其中一个分支可能的最大深度是 N。

所以它一定是O(2^M)但是M相对于N是多少？

注意:抱歉，如果这引起了困惑，但是 n = 当前的货币值(value)，并且我假设(大写)N 是硬币数组的长度

Answer 1

Ollie 对于硬币常数的 n 的复杂性给出了正确的答案，如图所示，这次使用您的函数计算并使用 matplotlib 绘制的图形(经过一些平滑处理):

我们认识到一条漂亮的抛物线 (n^2)

如果我们将 n 设为常数，并使硬币数量发生变化(随机生成硬币)，则曲线会陡峭得多，并且如您所想的呈指数增长

还有更好的算法如memoized版本:

# memways(n, k, coins) = number of ways of making 
# change of n with less or equal k coins
calculated = {}
def memways(n, k, coins):
    if n<0:
        return 0
    if (n, k) in calculated:
        return calculated[n,k]
    if k == 0:
        v = 1
    else:
        v = memways(n-coins[k], k, coins) + memways(n, k-1, coins)
    calculated[n,k] = v
    return v