Algorithmen und Datenstrukturen · Senior · Frage 36 von 75
Welchen Algorithmus nutzen git diff und viele Diff-Werkzeuge standardmäßig?
- 1Dijkstras Algorithmus auf einem Graphen aus Zeilen
- 2Levenshtein-Distanz, Zeichen für Zeichen berechnet
- 3Myers' Algorithmus, basierend auf dem kürzesten Edit-Skript
Antwort zeigen
Richtige Antwort: Myers' Algorithmus, basierend auf dem kürzesten Edit-Skript
Erklärung
Myers findet die kürzeste Folge von Einfügungen und Löschungen in O((n + m) × d), wobei d die Zahl der Unterschiede ist, ähnliche Dateien sind also schnell verglichen. Er ist eng mit der längsten gemeinsamen Teilfolge verwandt.