单词时间复杂度的递归解决方案？

Question

在以下代码中递归解决方案的时间复杂度是什么:http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/:

// returns true if string can be segmented into space separated
// words, otherwise returns false
bool wordBreak(string str)
{
    int size = str.size();

    // Base case
    if (size == 0)  return true;

    // Try all prefixes of lengths from 1 to size
    for (int i=1; i<=size; i++)
    {
        // The parameter for dictionaryContains is str.substr(0, i)
        // str.substr(0, i) which is prefix (of input string) of
        // length 'i'. We first check whether current prefix is in
        // dictionary. Then we recursively check for remaining string
        // str.substr(i, size-i) which is suffix of length size-i
        if (dictionaryContains( str.substr(0, i) ) &&
            wordBreak( str.substr(i, size-i) ))
            return true;
    }

    // If we have tried all prefixes and none of them worked
    return false;
}

我正在考虑它的n ^ 2,因为对于该方法的n个调用,最坏的情况是(n-1)工作(递归迭代其余的字符串？).或者它是指数/ n!？

我很难搞清楚这些递归函数的大(O).任何帮助深表感谢!

Answer 1

确切地说，答案是指数级的O(2^(n-2))。(2 power n-2)

在每次调用中，您都在调用具有长度的递归函数1,2....n-1（在最坏的情况下）。要完成 length 的工作，n您将递归地完成所有 length 字符串的工作n-1, n-2, ..... 1。所以 T(n) 是你当前调用的时间复杂度，你在内部做sum of T(n-1),T(n-2)....T(1).

数学上：

  T(n) = T(n-1) + T(n-2) +.....T(1);
  T(1) = T(2) = 1 

如果您真的不知道如何解决这个问题，那么解决上述递归问题的更简单方法就是通过替换值。

  T(1) = T(2) = 1
  T(3) = T(1) + T(2) = 1+1 =2; // 2^1
  T(4) = T(1)+ T(2) + T(3) = 1+1+2 =4; //2^2
  T(5) = T(1) + T(2) +T(3) +T(4) = 1+1+2+4 =8; //2^3

所以如果你替换前几个值，很明显时间复杂度是 2^(n-2)