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

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！？

我很难搞清楚这些递归函数的Big（O）。任何帮助深表感谢！

Answer 1

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

在每次调用中，您都调用递归函数，其长度为1,2....n-1（最差情况下）。要做长度为n的工作，你正在递归地完成所有长度为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)