GoIT_Algo_hw09
Жадібний алгоритм має часову складність O(n), де n - кількість типів монет. Це обумовлено тим, що він проходить по списку монет один раз. Для кожного типу монети він визначає максимальну кількість монет, які можна використати, і віднімає відповідну суму від загальної суми.
Жадібний алгоритм працює дуже швидко для більшості практичних випадків, але він не завжди знаходить оптимальне рішення для деяких специфічних наборів монет.
Алгоритм динамічного програмування має часову складність O(n×k), де n - кількість типів монет, а k - сума, яку потрібно видати. Він створює таблицю значень від 0 до суми, яку потрібно видати, і заповнює її мінімальною кількістю монет, необхідних для досягнення кожного значення.
Цей алгоритм гарантує знаходження оптимального рішення, тобто мінімальної кількості монет для заданої суми. Проте, він може бути повільнішим для великих сум у порівнянні з жадібним алгоритмом.
Жадібний алгоритм: Простий та швидкий, але не завжди оптимальний. Працює добре для великих сум, але може дати неправильний результат для деяких специфічних наборів монет.
Динамічне програмування: Гарантує оптимальне рішення, але може бути повільнішим для великих сум. Підходить для випадків, коли необхідна мінімальна кількість монет.