硬币找零问题：这两种方法的区别

Question

我正在 CS50 的 pset6 中实现 python 中的硬币找零问题。当我第一次解决这个问题时，这是我使用的算法：

import time

while True:
    try:
        totalChange = input('How much change do I owe you? ')
        totalChange = float(totalChange)  # check it it's a valid numeric value
        if totalChange < 0:
            print('Error: Please enter a positive numeric value')
            continue
        break
    except:
        print('Error: Please enter a positive numeric value')
start_time1 = time.time()
change1 = int(totalChange * 100)  # convert money into cents
n = 0
while change1 >= 25:
    change1 -= 25
    n += 1
while change1 >= 10:
    change1 -= 10
    n += 1
while change1 >= 5:
    change1 -= 5
    n += 1
while change1 >= 1:
    change1 -= 1
    n += 1

print(f'Method1: {n}')

print("--- %s seconds ---" % (time.time() - start_time1))

看了动态规划的讲座，想把它实现到这道题中。这是我的尝试：

while True:
    try:
        totalChange = input('How much change do I owe you? ')
        totalChange = float(totalChange)  # check it it's a valid numeric value
        if totalChange < 0:
            print('Error: Please enter a positive numeric value')
            continue
        break
    except:
        print('Error: Please enter a positive numeric value')
start_time2 = time.time()

change2 = int(totalChange*100)
rowsCoins = [1,5,10,25]
colsCoins = list(range(change2 + 1))
n = len(rowsCoins)
m = len(colsCoins)
matrix = [[i for i in range(m)] for j in range(n)]

for i in range(1,n):
    for j in range(1,m):
        if rowsCoins[i] == j:
            matrix[i][j] = 1
        elif rowsCoins[i] > j:
            matrix[i][j] = matrix[i-1][j]
        else:
            matrix[i][j] = min(matrix[i-1][j], 1 + matrix[i][j-rowsCoins[i]])

print(f'Method2: {matrix[-1][-1]}')

print("--- %s seconds ---" % (time.time() - start_time2))

当我运行程序时，它给出了正确的答案，但需要更长的时间。

我如何调整第二个代码以使其正确实现动态规划。我的问题是我从矩阵的左上角而不是右下角开始循环吗？
我编写的每个代码的算法的时间复杂度是多少（以及动态规划的正确实现）。我怀疑对于第一个代码，它遵循 O(n^4)，对于第二个代码 O(n*m)，动态规划的正确实现应该是 O(n)。我这样想对吗？

非常感谢任何有助于更好地理解这些算法的帮助。提前致谢。

Answer 1

我认为这两种算法基本上都是O(n)。

n 在这种情况下是输入的数字的大小。

在第一个算法中，它不是 O(n^4)，因为这表明您有 4 个嵌套循环循环 n 次。相反，您有 4 个循环运行顺序。如果他们根本不修改 change1，那可能是 O(4n)，这与 O(n) 相同。

在第二种算法中，您对变量名的选择有点混乱。 n 是一个常数，m 基于输入的大小，因此通常称为 n。因此，如果我们将 n 重命名为 c 并将 m 重命名为 n，我们将得到 O(c*n)，这与 O(n) 相同。

这里的关键点是对于任何特定的 n，O(n) 算法不一定比 O(n^2) 算法快。大 O 符号只是描述完成的工作量如何随输入的大小而变化。它所说的是，随着 n 变大，O(n) 算法所花费的时间将比 O(n^2) 算法所花费的时间增加慢，所以对于足够大的 n，复杂度较低的算法会更快。

Answer 2

How could I adjust the second code so that it is correctly implementing dynamic programming. Is my problem that I am starting the loops from the top left corner of the matrix instead of the bottom right?

恕我直言，这道题不适合动态规划，所以很难实现正确的dp。检查一个贪婪的解决方案 https://github.com/endiliey/cs50/blob/master/pset6/greedy.py 这应该是最好的解决方案。

What are the time complexities of the algorithms for each code that I wrote (as well as for a correct implementation of dynamic programming).

基本上你的两个代码都应该是O(n)，但这并不意味着它们具有相同的时间复杂度，正如你所说，dp解决方案要慢得多。那是因为他们有不同的因素（比率）。例如，4n和0.25n都是O(n)，但它们的时间复杂度不同。

贪心解的时间复杂度应该是O(1)。

硬币找零问题：这两种方法的区别

Coin change porblem: difference between these two methods

python

algorithm

big-o

cs50