Algorytmy i struktury danych · Senior · Pytanie 36 z 75
Którego algorytmu domyślnie używa git diff i wiele narzędzi diff?
- 1Algorytmu Dijkstry na grafie wierszy
- 2Odległości Levenshteina liczonej znak po znaku
- ✓Poprawna odpowiedź: Algorytmu Myersa opartego na najkrótszym skrypcie edycji
Wyjaśnienie
Myers znajduje najkrótszy ciąg wstawień i usunięć w O((n + m) × d), gdzie d to liczba różnic, więc podobne pliki porównuje się szybko. Jest blisko związany z najdłuższym wspólnym podciągiem.