Изменения

Алгоритм в виде, описанном выше, требует <math>\Theta(M \cdot N)</math> операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 10⁵ строк потребуется около 40 гигабайт памяти. Если однако, если требуется только расстояние, легко уменьшить требуемую память до <math>\Theta(\min(M,N))</math>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как