Изменения

Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(\min(M,N))</tex>. Для этого надо учестьЗаметим, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после для вычисления <tex>D([i, j)]</tex> не нужны также нам нужно только <tex>D([i-1]</tex>,0)поэтому будет вычислять <tex>D[i]</tex> в <tex>\dotsD[1]</tex> , а <tex>D([i-1,j-1)]</tex>. Поэтому алгоритм можно переписать какв <codetex> '''for''' i = 0 '''to''' M '''for''' j = 0 '''to''' N вычислить D[i0][j] '''if''' i </tex> 0 и j , а затем поменяем местами<tex> 0 стереть D[i - 1][j - 1] '''return''' </tex> и <tex>D[M, N0]</codetex>.

'''int''' '''levensteinInstruction'''('''int[]''' D): '''for''' i = 0 '''to''' M '''for''' j = 0 '''to''' N вычислить D[1][j] swap(D[0], D[1]) '''return''' D[0, N]