scramble string的时间复杂度

原题 https://leetcode.com/problems/scramble-string/
个人感觉这种没用DP的递归解法比较通俗易懂，不过查了半天也没找到一个确定的关于复杂度的解释。
解法比如这个 http://fisherlei.blogspot.com/2013/01/leetcode-scramble-string.html
想请教下这个情况的复杂度是多少，具体是怎么分析的。非常感谢！

1. 
   
2. 
   
3.     bool isScramble(string s1, string s2) {
   
4.         if(s1==s2)
   
5.             return true;
   
6.             
   
7.         string a = s1, b = s2;
   
8.         sort(a.begin(), a.end());
   
9.         sort(b.begin(), b.end());
   
10.         
    
11.         if(a!=b) return false;
    
12.          
    
13.         for(int i=1; i<s1.length(); i++){
    
14.             
    
15.             string left = s1.substr(0, i);
    
16.             string right = s1.substr(i);
    
17.             
    
18.             
    
19.             string l = s2.substr(0,i);
    
20.             string r = s2.substr(i);
    
21.             
    
22.             if(isScramble(l, left)&&isScramble(r, right))
    
23.                
    
24.                 return true;
    
25.                
    
26.                
    
27.             l = s2.substr(0, right.length()) ;
    
28.             r = s2.substr(right.length());
    
29.             
    
30.             
    
31.             if( isScramble(l, right)&&isScramble(r, left))
    
32.             
    
33.                 return true;
    
34.   
    
35.         }
    
36.         
    
37.         return false;
    
38.         
    
39.     }

复制代码

忽略掉前几行的prune部分，我们只看for loop的话，可以发现：
T(n) = T(1)+T(n-1) + T(2)+T(n-2) + ...    T(n-1) + T(1)
       = 2 (T(1)+T(2)+T(3)+ ... + T(n-1))
      
稍微变形得到 T(n) = 3T(n-1)
所以可以得出复杂度是O(3^n)

handsomecool 发表于 2016-7-4 10:01
忽略掉前几行的prune部分，我们只看for loop的话，可以发现：
T(n) = T(1)+T(n-1) + T(2)+T(n-2) + .. ...

懂了，非常感谢🙏

手抖点了个反对。。

分析得好