贪心换币时间复杂度

Question

我正在尝试计算贪婪硬币兑换算法的时间复杂度。（我知道动态编程方法更适合这个问题，但我已经这样做了）。我不确定如何进行 while 循环，但我确实得到了 for 循环。

我有以下内容，其中 D[1...m] 是面额的数量（始终包含 1），n 是您需要找零的金额。

这是我的算法：

CoinChangeGreedy(D[1...m], n)
    numCoins = 0
    for i = m to 1
        while n ≥ D[i]
            n -= D[i]
            numCoins += 1
    return numCoins

Answer 1

让我们看看边缘情况。

在最坏的情况下 D 仅包含 1 个元素（当 m=1 时），那么您将在 while 循环中循环 n 次 -> 复杂度为 O(n)。

如果m>>n（m比n大很多，所以D有很多比n大的元素）那么你将循环所有 m 元素，直到你得到更小的一个然后 n （大部分工作将在 for 循环部分）-> 然后它 O(m)。

按钮行：O(max(m,n))

希望对您有所帮助！

Answer 2

感谢您的帮助。我改变了我必须的算法，我可以很容易地计算出它的时间复杂度。这是我将其更改为：

CoinChangeGreedy(D[1...m], n)
    numCoins = 0
    for i = m to 1
        if n/D[i] ≥ 1
            numCoins = numCoins + (n/D[i])
            n = n - [(n/D[i]) * D[i]]
    return numCoins

我计算出最坏情况 = 最好情况 \in \Theta(m)

贪心换币时间复杂度

Greedy Coin Change Time Complexity

time-complexity

greedy

coin-change