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

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

Спасибо за помощь.Я изменил алгоритм, который мне нужен, на что-то, для чего я мог легко рассчитать сложность времени.Вот что я изменил:

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)

Answer 2

Давайте посмотрим на крайние случаи.

В худшем случае D включает только 1 элемент (когда m=1), тогда вы будете циклировать n раз в цикле while -> сложность O (n).

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

Строка кнопок: O (max (m, n))

Надеюсь, это поможет!