时间复杂性澄清

Question

给定一个非空字符串s和一个包含非空单词列表的字典字词，确定s是否可以被分割成一个或多个字典单词的空格分隔序列。您可以假定字典不包含重复的单词。

例如，给定s=“leetcode”，dict=[“leet”,“code”]。

返回true，因为“leetcode”可以分段为“leetcode”。

朴素解给出如下：

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return word_Break(s, new HashSet(wordDict), 0);
    }
    public boolean word_Break(String s, Set<String> wordDict, int start) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end)) {
                return true;
            }
        }
        return false;
    }
}

时间复杂度被列为O(n^n)，因为这是递归树的大小。我完全同意递归树的最后一层有n^n个元素，但在该层之前的不是有n^(N-1)吗？所以我们看的是n^n+n^(N-1)+n^(N-2)...导致更高的时间复杂度，对吗？

Answer 1

让我们从时间复杂度函数的上界的一个简单递推关系开始（即假设它循环整个过程而没有找到匹配）：

这里i是start，而n是s.length()。每个术语对应于：

>

1:递归调用word_break，使用start=end，其中end是j

第二：调用worddict.contains，子字符串长度end-start+1。

因为Worddict是一个哈希集，所以这个调用是O(L)，其中L是输入单词的长度（因为我们需要复制子字符串并对其进行哈希）

扩展的：

（Wolfram alpha的最后一步）

uint64_t T(uint32_t N, uint32_t start)
{
   if (start >= N) return 1;
   uint64_t sum = 0;
   for (uint32_t end = start + 1; end <= N; end++)
      sum += (end - start + 1) + T(N, end);
   return sum;
}

N        T(N)
-----------------
1        3 
2        9 
3        22 
4        49 
5        104 
6        215 
7        438 
8        885 
9        1780 
10       3571 
11       7154 
12       14321 
13       28656 
14       57327 
15       114670 
16       229357 
17       458732 
18       917483 
19       1834986 
20       3669993 
21       7340008 
22       14680039 
23       29360102 
24       58720229 
25       117440484 
26       234880995 
27       469762018 
28       939524065 
29       1879048160 
30       3758096351 
31       7516192734 
32       15032385501 
33       30064771036 
34       60129542107 

时间复杂度的对数标度图：

正如您所看到的，这是线性的，这意味着时间复杂度的形式为a^n，而不是n^n。

相比之下，t(N)=O(N^N)将给出如下图：