0

我正在尝试分析以下函数的时间复杂度。该函数用于检查一个字符串是否由其他字符串组成。

set<string> s; // s has been initialized and stores all the strings
bool fun(string word) {
    int len = word.size();

    // something else that can also return true or false with O(1) complexity

    for (int i=1; i<=len; ++i) {
       string prefix = word.substr(0,i);
       string suffix = word.substr(i);
       if (prefix in s && fun(suffix))
           return true;
       else
           return false;
    }
}

我认为时间复杂度是O(n)n 是单词的长度（对吗？）。但是由于递归在循环内，我不知道如何证明它。

编辑：

此代码不是正确的C++代码（例如，prefix in s）。我只是展示这个函数的思想，想知道如何分析它的时间复杂度

4

2 回答 2

4

分析这一点的方法是根据输入的长度和前缀在 中的（未知）概率来开发递归关系s。让我们假设前缀出现的概率由前缀s长度 L 的某个函数 pr(L) 给出。让复杂度（操作数）由 T(len) 给出。

如果 len == 0 （word是空字符串），那么 T = 1。（该函数return在循环之后缺少最后一条语句，但我们假设实际代码只是这个想法的草图，而不是实际执行的代码）。

对于每个循环迭代，用 T(len; i) 表示循环体复杂度。如果前缀不在 中s，则主体具有恒定复杂度 (T(len; i) = 1)。该事件的概率为 1 - pr(i)。

如果前缀在 中s，则函数根据对 的递归调用返回true或，其复杂度为 T(len - i)。该事件的概率为 pr(i)。falsefun(suffix)

因此，对于 的每个值i，循环体复杂度为：

T(len; i) = 1 * (1 - pr(i)) + T(len - i) * pr(i)

最后（这取决于预期的逻辑，而不是发布的代码），我们有

T(len) = sum  i=1...len (T(len; i))

为简单起见，让我们将 pr(i) 视为值为 0.5 的常数函数。那么 T(len) 的递归关系是（直到一个常数因子，这对于 O() 计算并不重要）：

T(len) = sum  i=1...len (1 + T(len - i)) = len + sum  i=0...len-1 (T(i))

如上所述，边界条件是 T(0) = 1。这可以通过标准递归函数方法来解决。让我们看一下前几个术语：

len   T(len)
0     1
1     1 + 1 = 2
2     2 + 2 + 1 = 5
3     3 + (4 + 2 + 1) = 11
4     4 + (11 + 5 + 2 + 1) = 23
5     5 + (23 + 11 + 5 + 2 + 1) = 47

该模式显然是 T(len) = 2 * T(len - 1) + 1。这对应于指数复杂度：

T(n) = O( 2n )

当然，这个结果取决于我们对 pr(i) 所做的假设。（例如，如果所有 i 的 pr(i) = 0，则 T(n) = O(1)。如果 pr(i) 具有最大前缀长度，那么也会出现非指数增长——pr(i) = 0 对于所有 i > M 对于某些 M。) pr(i) 独立于 i 的假设可能是不现实的，但这实际上取决于s填充方式。

于 2013-08-25T18:57:25.267 回答
0

假设您已经修复了其他人注意到的错误，那么这些i值就是字符串被拆分的位置（每个i都是最左边的拆分点，然后您在 右边的所有内容上递归i）。这意味着如果您要展开递归，您将查看n-1不同的分割点，并询问每个子字符串是否是有效单词。如果你的集合的开头word没有很多元素，那一切都很好，从那时起你可以跳过递归。但在最坏的情况下，prefix in s总是如此，并且您尝试每个可能的n-1分割点子集。这给出了2^{n-1}不同的分割集，乘以每个这样的集的长度。

于 2013-08-25T17:41:51.267 回答