内部循环递归函数的时间复杂度分析 [英] Time complexity analysis of function with recursion inside loop

问题描述

我正在尝试分析以下功能的时间复杂度。

I am trying to analysis time complexity of below function. This function is used to check if a string is made of other strings.

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是单词的长度（我对吗？）。但是由于递归是循环的，所以我不知道如何证明这一点。

I think the time complexity is O(n) where n is the length of word (am I right?). But as the recursion is inside the loop, I don't know how to prove it.

编辑：

此代码不是正确的 C ++ 代码（例如s 中的前缀）。我只是展示了此函数的概念，并想知道如何分析其时间复杂度

This code is not a correct C++ code (e.g., prefix in s). I just show the idea of this function, and want to know how to analysis its time complexity

推荐答案

分析方法是通过根据输入的长度和前缀在 s 中的（未知）概率开发递归关系。假设前缀在 s 中的概率由前缀长度L的某些函数pr（L）给出。令复杂度（操作数）由T（len）给出。

The way to analyze this is by developing a recursion relationship based on the length of the input and the (unknown) probability that a prefix is in s. Let's assume that the probability of a prefix being in s is given by some function pr(L) of the length L of the prefix. Let the complexity (number of operations) be given by T(len).

如果len == 0（ word 是空字符串），然后T =1。（该函数在循环后缺少最后一个 return 语句，但我们假设实际代码只是一个

If len == 0 (word is the empty string), then T = 1. (The function is missing a final return statement after the loop, but we're assuming that the actual code is only a sketch of the idea, not what's actually executing).

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

For each loop iteration, denote the loop body complexity by T(len; i). If the prefix is not in s, then the body has constant complexity (T(len; i) = 1). This event has probability 1 - pr(i).

如果前缀在 s 中，则函数返回根据对 fun（后缀） true 或 false c>，其复杂度为T（len-i）。该事件的概率为pr（i）。

If the prefix is in s, then the function returns true or false according to the recursive call to fun(suffix), which has complexity T(len - i). This event has probability pr(i).

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

So for each value of i, the loop body complexity is:

T（len; i）= 1 *（1-pr（i））+ T（len-i）* pr（i ）

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

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

Finally (and this depends on the intended logic, not the posted code), we have

T（len）= sum   _{i = 1 ... len} （T（len; i））

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

为简单起见，我们将pr（i）视为值为0.5的常数函数。然后，T（len）的递归关系为（直到一个恒定因子，对于O（）计算而言并不重要）：

For simplicity, let's treat pr(i) as a constant function with value 0.5. Then the recursive relationship for T(len) is (up to a constant factor, which is unimportant for O() calculations):

T （len）= sum   _{i = 1 ... len} （1 + T（len-i））= len + sum _{&ibsp; i = 0 ... len-1} （T（i））

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

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

As noted above, the boundary condition is T(0) = 1. This can be solved by standard recursive function methods. Let's look at the first few terms:

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。这对应于指数复杂度：

The pattern is clearly T(len) = 2 * T(len - 1) + 1. This corresponds to exponential complexity:

T（n） = O（2 ⁿ ）

当然，此结果取决于我们对pr（一世）。 （例如，如果所有i的pr（i）= 0，则T（n）= O（1）。如果pr（i）的前缀长度上限为，也将出现非指数增长pr（i）=对于所有i> 0，对于所有i，对于某些M，M。）pr（i）独立于i的假设可能是不现实的，但这实际上取决于 s 的填充方式。

Of course, this result depends on the assumption we made about pr(i). (For instance, if pr(i) = 0 for all i, then T(n) = O(1). There would also be non-exponential growth if pr(i) had a maximum prefix length—pr(i) = 0 for all i > M for some M.) The assumption that pr(i) is independent of i is probably unrealistic, but this really depends on how s is populated.

这篇关于内部循环递归函数的时间复杂度分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！