单词拆分（word-break）递归解法的时间复杂度计算求助

你写的这段无记忆化的暴力递归解法，最坏时间复杂度为 O(2ⁿ × n × m)，其中：

• n 是输入字符串 s 的长度
• m 是字典 wordDict 的元素个数

复杂度计算逻辑 #

• 递归调用量级：长度为n的字符串共有n-1个可拆分位置，每个位置可以选择拆分或者不拆分，最坏情况下（比如字典包含所有单字符、字符串没有合法拆分需要遍历所有可能路径）会遍历完所有2ⁿ⁻¹种拆分组合，递归调用量级为O(2ⁿ)
• 单次递归的操作开销：
  • 你用vector的find方法做字典查找，属于线性查找，每次查找的时间复杂度为 O(m × k)，k是当前待匹配子串的长度，最坏情况k等于n
  • substr截取子串的操作时间复杂度为O(k)，最坏同样为O(n)
    两者合并单次递归内的操作最坏为O(n×m)

如果提前把字典转为无序哈希集合（unordered_set）优化查找效率，查找的时间复杂度可以降到O(k)即O(n)，此时最坏时间复杂度可以简化为 O(2ⁿ × n)，仍然是指数级，核心原因是没有做记忆化缓存，相同的后缀子串会被不同的拆分路径重复调用计算。如果加上记忆化缓存存储已经计算过的后缀结果，时间复杂度可以降到多项式级别的O(n²×m)（哈希优化后为O(n²)）。

内容的提问来源于stack exchange，提问作者Ayushaps1