96题的时间复杂度求分析

如题，跪求分析时间复杂度～    （我知道这题应该用DP, 但是为了学习目的，我还是想知道这个时间复杂度是多少～）

1. class Solution {
   
2. 
   
3.     public int numTrees(int n) {
   
4.          
   
5.        return dfs(1, n);            
   
6.      
   
7.     }
   
8.    
   
9.     public int dfs(int left, int right){
   
10.         
    
11.         int res = 0;
    
12.          
    
13.         if(left >= right) return 1;  // base case
    
14.         
    
15.         for(int i = left; i <= right; i++ ){
    
16.       
    
17.             int L = dfs( left, i - 1 );
    
18.             
    
19.             int R = dfs( i+1,  right );
    
20. 
    
21.             res += L*R;
    
22.         }
    
23.    
    
24.         return res;  
    
25.    
    
26.     }
    
27. }
    
28. 
    
29.   

复制代码

如题，跪求分析时间复杂度～


补充内容 (2020-8-2 01:48):
---

为何时间复杂度是 O(n!）更准确点？  （大神告诉我的，但我不知道原因，而我自己粗暴分析是2^n）

补充内容 (2020-8-2 03:08):
--

大神说搞错了，说应该是 4^n    大家能分析下吗？

复杂度是指数级别的。

令f_n为right-left+1=n时的迭代次数，根据你的计算，有

f_n=2 \sum_{k=0}^{n-1} f_k，可以自己用python算一下这个值是多少。

作为一个下界估计，有

f_n >= 2 f_{n-1}，从而

f_n >= 2^(n-1)。

yihong15 发表于 2020-7-31 11:33
复杂度是指数级别的。

令f_n为right-left+1=n时的迭代次数，根据你的计算，有

大神说是O(n!)哦

zurich.hill 发表于 2020-7-31 11:50
大神说是O(n!)哦

我只说是指数级别的啊。

以及准确的计算应该是O(3^n)，

按照f_0=1来进行递推，不难验证

f_n=2*3^(n-1) 对于任意 n>=1成立。

yihong15 发表于 2020-7-31 12:07
我只说是指数级别的啊。

以及准确的计算应该是O(3^n)，

我还是不懂啊～  能做一个详细视频看看吗？