java - 时间复杂度说明

Question

使用以下算法(来自 Leetcode):

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

例如，给定s = "力扣",dict = ["leet", "code"].

返回true，因为“leetcode”可以分割为“leet code”。

天真的解决方案如下:

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 步:使用 start = end 递归调用 word_Break，其中 end 是 j

• 第二步:使用长度为 end - start + 1 的子字符串调用 wordDict.contains。

  既然 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) 将给出以下图:

它不是线性的，并且增长快得多(注意纵轴上的数字)。