Каково время и пространство сложности этой реализации? - PullRequest
Новая
       62

Каково время и пространство сложности этой реализации?

1 голос
/ 08 апреля 2020

Я пытаюсь оценить временную и пространственную сложность нижеприведенной задачи о разрыве слов Python реализация: 

def _word_break(s, pos, n, dictionary, cache):
    if pos >= n:
        return True

    if pos not in cache:
        result = False
        for i in range(pos+1, n+1):
            substring = s[pos:i]
            if substring in dictionary: 
                if _word_break(s, i, n, dictionary, cache):
                    result = True
                    break
        cache[pos] = result
    return cache[pos]

def word_break(string, dictionary):
    return _word_break(string, 0, len(string), dictionary, {})

Насколько я понимаю, она имеет пространственную сложность O (n ^ 2), потому что несмотря на сохраняя только n позиций в Cache, он также создает n * n подстрок. Что касается сложности времени, я считаю, что это что-то вроде O (n ^ 3), потому что оно похоже на другие реализации, но я не могу понять, почему.

Не могли бы вы помочь мне оценить их?

...