Проблема смены монет: разница между этими двумя методами - PullRequest
Новая
       12

Проблема смены монет: разница между этими двумя методами

0 голосов
/ 31 декабря 2018

Я реализую проблему смены монет в python в CS50 для pset6.Когда я впервые решил эту проблему, я использовал следующий алгоритм: 

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))

Когда я запускаю программу, она дает правильные ответы, но это занимает гораздо больше времени.

  1. Как я могу настроить второй кодтак что он правильно реализует динамическое программирование.Моя проблема в том, что я запускаю циклы из верхнего левого угла матрицы, а не из нижнего правого?
  2. Каковы временные сложности алгоритмов для каждого написанного мной кода (а также для правильногореализация динамического программирования).Я подозреваю, что для первого кода следует O (n ^ 4), а для второго кода O (n * m) и правильная реализация динамического программирования должна быть O (n).Правильно ли я так думаю?

Любая помощь для лучшего понимания этих алгоритмов очень ценится.Заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 31 декабря 2018

Как я могу настроить второй код так, чтобы он правильно реализовывал динамическое программирование.Моя проблема в том, что я запускаю циклы из верхнего левого угла матрицы, а не из нижнего правого?

ИМХО, эта проблема не подходит для динамического программирования, поэтому трудно реализовать правильно дп.Проверьте жадное решение https://github.com/endiliey/cs50/blob/master/pset6/greedy.py, которое должно быть лучшим решением.

Каковы временные сложности алгоритмов для каждого кода, который я написал (а также для правильной реализации динамическогопрограммирование).

В основном оба ваших кода должны быть O(n), но это не значит, что они имеют одинаковую сложность по времени, как вы сказали, решение dp намного медленнее.Это потому, что они имеют другой коэффициент (отношение).Например, 4n и 0.25n оба являются O(n), но имеют разную временную сложность.

Жадное решение должно иметь временную сложность O(1).

0 голосов
/ 31 декабря 2018

Я думаю, что оба алгоритма в основном 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).Обозначение Big O просто описывает, как объем выполненной работы зависит от размера ввода.Что он говорит, так это то, что с ростом n время, затрачиваемое алгоритмом O (n), будет увеличиваться на медленнее , чем время, затрачиваемое алгоритмом O (n ^ 2), поэтому для некоторых достаточно большихп, алгоритм с меньшей сложностью будет быстрее.

...