Сложность времени смены жадных монет

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) тогда вы будете зацикливаться n раз в цикле while -> сложность O(n).

Если m>>n (m намного больше, чем n, так D имеет много элементов, которые больше, чем n) тогда вы будете зацикливаться на всех m элемент, пока вы не получите samller один тогда 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)