Ein Greedy-Algorithmus trifft bei jedem Schritt die lokal optimale Wahl in der Hoffnung, dass dies zum globalen Optimum führt. Er ist einfach und schnell, aber nur korrekt, wenn das Problem die Greedy-Choice-Eigenschaft und optimale Substruktur besitzt.
Überdenken Sie frühere Entscheidungen nie — verpflichten Sie sich zur besten sofortigen Option und fahren Sie fort.
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
Dies ist optimal für US-Münzen, aber schlägt fehl für Mengen wie {1, 3, 4}, wobei Greedy 4+1+1 für 6 statt 3+3 ergibt.
Beispiele, die funktionieren: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
Gewöhnlich schnell — oft O(n log n) nach dem Sortieren.
Greedy ist nicht immer korrekt. Beweisen Sie die Greedy-Choice-Eigenschaft oder testen Sie gegen einen Brute-Force/DP-Baseline, bevor Sie sich darauf verlassen.
Wenn Greedy zutrifft, ist es far einfacher und schneller als DP oder Brute Force.
Zu wissen, wann es gültig ist — und wann es heimlich falsche Antworten liefert — ist ein Zeichen algorithmischer Reife.
Viele grundlegende Graph-Algorithmen sind im Kern Greedy-Algorithmen.
Eine Sammlung von IT-Interviewfragen mit ausführlichen Antworten — vom Junior bis zum Senior.
Spenden