Анализ сложности времени для разрыва слова

Question

Что такое анализ сложности времени и анализ сложности пространства для следующего кода:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not s or not dict:
            False

        N=len(s)
        ans=[False for i in range (N+1)]
        ans[0]=True


        for index in range(N):
            if ans[index]:
                for word in wordDict:
                    L=len(word)
                    if index+L <= N and s[index:index+L]==word:
                        ans[index+L]=True

        return ans[-1]

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

Answer 1

Временная сложность этого решения составляет O(n*m*k) - где:

• n - длина строки s.
• m - число слова в wordDict.
• k - это средняя длина слова в wordDict.

Пояснения, вы повторяете n раз, для каждого проверяемого каждого слово в wordDict (* m всего), и для каждого такого повтора вы читаете все слово (длиной k).

Сложность пространства равна O(n) - ваш вспомогательный массив не зависит от количество слов в wordDict или их длина, и нет дополнительного выделения места ¹ в зависимости от словаря.

---

(1) Ну, я не уверен, как python реализует s[index:index+L], но в любом случае это не умножается на n, и никогда не выделяется более одного раза за раз, и никогда не выделяется, если L > n - так что это не влияет на сложность пространства в любом случае.