python - 渐近运行时间分析——硬币找零算法

Question

我需要帮助找到以下算法的渐近运行时间，即 Big O(n) -> change_slow() 。我尝试了大师方法和其他技术，但似乎找不到答案。

这是一个硬币找零问题，使用以下数据范围处理：

for i in range(50, 950, 50):
    data.append(([1,10,25,50],i))

for i in range(50, 600, 50):
     data.append(([1,3,4,17,31],i))

这是算法：

coins = item[0]
amount = item[1]

coins_needed = [j for j in change_slow(amount, coins, [])]


def change_slow(a, v, c):
    if(len(v) == 0):
        pass
    elif(sum(c) == a):
        yield c
    elif(sum(c) > a):
        pass
    else:
        for i in change_slow(a, v[:], c + [v[0]]):
            yield i
        for i in change_slow(a, v[1:], c):
            yield i

T(n) = 形式的方程是什么？

Answer 1

这不会给你一个确切的答案（递归关系），但你可以通过在改变输入的同时计算步数来通过实验找到它。

steps = 0

def change_slow(a, v, c):
    global steps
    steps += 1
    if(len(v) == 0):
        pass
    elif(sum(c) == a):
        yield c
    elif(sum(c) > a):
        pass
    else:
        for i in change_slow(a, v[:], c + [v[0]]):
            yield i
        for i in change_slow(a, v[1:], c):
            yield i

print "\n== Varying number of coins =="

for i in range(1, 40):
    coins = range(1, i+1)
    result = list(change_slow(19, coins, []))
    print "%s\t%s" % (len(coins), steps)
    steps = 0

print "\n== Varying the amount =="

for i in range(1, 1000):
    result = list(change_slow(i, [1,2,3,4,5,6,7,8,9,10], []))
    print "%s\t%s" % (i, steps)
    steps = 0

绘制此数据：

https://plot.ly/~skryskalla/11

增加硬币的数量会导致步数线性增加，而增加数量会导致步数呈指数增加。