Этот рекурсивный алгоритм Левенштейна настолько медленный или я ошибаюсь?

Я видел эту формулу Левенштейна в Википедии:

введите описание изображения здесь

Я реализовал этот алгоритм рекурсивным способом (я знаю, что это неэффективный способ реализовать его таким образом, но я хотел посмотреть, насколько он неэффективен), вот код (на PHP):

function lev($str1, $str2, $i, $j) {

if (min($i, $j) == 0) {
return max($i, $j);
}
else {
$m = ($str1[$i-1] == $str2[$j-1]) ? 0 : 1;
return min(lev($str1, $str2, $i, $j - 1) + 1,
lev($str1, $str2, $i - 1, $j) + 1,
lev($str1, $str2, $i - 1, $j - 1) + $m);
}
}

$str1 = "long long text";
$str2 ="absolute";

echo lev($str1, $str2, strlen($str1),strlen($str2));

Когда я проверяю это, как я делал для этих двух строк (даже если «длинный длинный текст» не такой длинный), я получаю «Максимальное время выполнения 30 секунд» …, но функция, кажется, работает со строками, где Левенштейн небольшое расстояние (например, $ str1 = «word», $ str2 = «corw»)

Превышение 30 секунд для завершения этого сценария слишком много, поэтому, возможно, я ввел что-то неправильно в реализации (но когда я смотрю на реализацию, я не вижу ошибок, мне кажется, что я написал правильный алгоритм, если он основан на формула вики)

Эта реализация слишком медленная или я где-то ошибаюсь в коде?

Спасибо за внимание!

0

Решение

Вы не используете памятку в своем коде, поэтому она имеет экспоненциальную временную сложность. Вот почему это так медленно. Вы можете добавить памятку, чтобы избежать вычисления значения функции более одного раза для одного и того же i а также j достигать O(N * M) сложность времени.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]