这个算法在大 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) 可以看出，深度大于 292，输入 N=5。

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

所以一定是O(2^M)但是M和N的关系是什么？

注意：抱歉，如果这引起了混淆，但 n = 当前的货币价值，我假设（大写）N 是硬币数组的长度

Answer 1

O(n^2).

它是 n 的递归函数，在递归调用中仅修改 coins，给出 n^2.

添加第二个递归调用是无关紧要的，因为它超过了一些x < n。

Answer 2

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

这个算法在大 O 符号中的复杂性？

Complexity of this algorithm in big O notation?

python

algorithm

big-o