Algorithmen und Datenstrukturen · Middle · Frage 44 von 75
Welche Komplexität hat die DP für Wechselgeld bei Betrag A und k Münzarten?
- 1O(kᴬ)
- 2O(A + k)
- 3O(A × k)
Antwort zeigen
Richtige Antwort: O(A × k)
Erklärung
Für jeden Betrag von 1 bis A probiert man jede der k Münzen einmal. Exponentielles O(kᴬ) ist die Brute-Force-Rekursion ohne Caching.