确定时间复杂度的算法

Question

对于以下算法：

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

我写了以下代码：

def word_break(s, word_dict)
can_break?(s, word_dict, memo = {})
end
def can_break?(s, word_dict, memo)
return true if s.empty?
(0...s.length).each do |index|
string_to_pass = s[index + 1...s.length]
memo[string_to_pass] ||= can_break?(string_to_pass, word_dict, memo)
return true if word_dict.include?(s[0..index]) && memo[string_to_pass]
end
false
end

我对这里分析的理解是，我们让递归调用的数量与输入字符串大小线性缩放(因为我们使用记忆减少了递归调用的数量(，并且每个递归调用都做 N 工作(扫描数组(。这是否计算为 O(N^2( 时间和 O(N( 空间？ (请注意，字典是一个数组，而不是哈希(。

Answer 1

这是对基本原理的一个很好的总结;是的，你是对的。 从理论上讲，通过记忆，每个字符都需要作为m扫描的起点，其中m是到字符串近端的距离。 您可以应用各种标量级优化，但复杂性仍然是O(N^2(