Сложность реализации рекурсии сверху вниз с расстоянием редактирования (расстояние Левенштейна)

Я весь день работал над проблемой, с которой, похоже, не мог справиться. Задача состоит в том, чтобы показать, что рекурсивная реализация расстояния редактирования имеет временную сложность (2 max (n, m)), где n & m - длина измеряемых слов.

Реализация сравнима с этим маленьким примером на Python.

def lev(a, b):
    if("" == a):
       return len(b)   # returns if a is an empty string
    if("" == b):
        return len(a)   # returns if b is an empty string
    return min(lev(a[:-1], b[:-1])+(a[-1] != b[-1]), lev(a[:-1], b)+1, lev(a, b[:-1])+1)

От: http://www.clear.rice.edu/comp130/12spring/editdist/

Я пробовал рисовать деревья глубины рекурсии для разных коротких слов, но не могу найти связи между глубиной дерева и сложностью.

Формула рекурсии из моего расчета

m = length of word1
n = length of word2
T(m,n) = T(m-1,n-1) + 1 + T(m-1,n) + T(m,n-1)
With the base cases:
T(0,n) = n
T(m,0) = m

Но я понятия не имею, как действовать дальше, поскольку каждый вызов приводит к 3 новым вызовам, поскольку длины не достигают 0.

Я был бы признателен за любые советы о том, как я могу продолжить, чтобы показать, что нижняя граница сложности составляет (2 max (n, m)).


algorithm big-o complexity-theory edit-distance levenshtein-distance
person John    schedule 31.01.2013    source источник
comment
Вы уверены насчет большой омеги? Давайте оставим n постоянным равным 1. Тогда мы легко увидим, что сложность равна k m (дерево представляет собой почти список) и совершенно очевидно, что k m ‹2 ^ m = 2 ^ max (1, m ) для m ›= m_0   -  person tb-    schedule 01.02.2013

Ответы (1)


arrow_upward
6
arrow_downward

Ваша формула рекурсии:

T(m,n) = T(m-1,n-1) + T(m-1,n) + T(m,n-1) + 1
T(0,n) = n
T(m,0) = m

верно.

Вы можете видеть, что каждый T(m,n) разбивается на три пути. Поскольку каждый узел работает в O(1), нам нужно только подсчитать узлы.

Кратчайший путь имеет длину min(m,n), поэтому дерево имеет не менее 3min(m,n) узлов. Но есть пути и более длинные. Вы получите самый длинный путь, поочередно уменьшая первую и вторую строку. Этот путь будет иметь длину m+n-1, поэтому все дерево имеет не более 3m+n-1 узлов.

Пусть m = min(m,n). В дереве также содержится не менее

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

разные пути, по одному для каждого возможного порядка уменьшения n.

Итак, Ω(2max(m,n)) и Ω(3min(m,n)) - это нижние границы, а O(3m+n-1) - верхняя граница.

person AbcAeffchen    schedule 10.07.2014