Було порівняно ефективність жадібного алгоритму та алгоритму динамічного програмування на прикладі задачі з повернення решти монетами різного номіналу.

У якості вхідних даних було використано:

• досутпні номінали монет - 50, 25, 10, 5, 2, 1
• сумму решти яку треба повернути монетами - 1000000

За допомогою модулю timeit було виконано вимірювання часу виконання алгоритмів у секундах для кожного з алгоритмів на основі 10 повторів.

Результати наведені на зображенні нижче:

Отже, на основі результатів тестових замірів алгоритмів можна зробити висновок, що жадібний алгорим працює значно швидше. Це можна пояснити наступними причинами:

• жадібний алгоритм має швидищий час виконання при даних умовах, оскільки він при кожному проході вибирає найбільший можливий номінал, який перевищує залишок суми. В той самий час, динамічний алгортим додатково обчислює мінімальну кількость монет для кожної можливої підсуми
• динамічний алгормти використовує більше памʼяті для збереження проміжних результатів для кожної підсуми

Варто зауважити, що за інших умов жадібний алгоритм може призводити до неоптимального результату, в той час як динамічний алгорити, не дивлячись на більшу часову складність, завжди дає оптимальний результат. Динамічний алгоритм, може бути більш ефективним в такій задачі, як "задача про рюкзак", напрклад.