Algorytmy i struktury danych · Middle · Pytanie 44 z 75
Jaka jest złożoność DP wydawania reszty dla kwoty A i k rodzajów monet?
- 1O(kᴬ)
- 2O(A + k)
- ✓Poprawna odpowiedź: O(A × k)
Wyjaśnienie
Dla każdej kwoty od 1 do A próbujemy każdej z k monet raz. Wykładnicze O(kᴬ) to rekurencja przeglądu zupełnego bez zapamiętywania.