[已解决]递归的时间复杂度

柿子饼同学

洛谷2020初赛模拟第16题, 这个算复杂度的题不会, 求助, 代码如下

1. #include<iostream>
   
2. using namespace std;
   
3. #define MAXN 20
   
4. int gu[MAXN][MAXN];
   
5. int luo(int n, int m) {
   
6.     if(n <= 1 || m < 2)
   
7.         return 1;
   
8.     if(gu[n][m] != -1)
   
9.         return gu[n][m];
   
10.     int ans = 0;
    
11.     for(int i = 0; i < m; i += 2)
    
12.         ans += luo(n - 1, i);
    
13.     gu[n][m] = ans;
    
14.     return ans;
    
15. }
    
16. int main() {
    
17.     int n, m;
    
18.     cin >> n >> m;
    
19.     for(int i = 0; i < MAXN; i++)
    
20.         for(int j = 0; j < MAXN; j++)
    
21.             gu[i][j] = -1;
    
22.     cout << luo(n, m);
    
23.     return 0;
    
24. }

复制代码

最佳答案

月排行榜 / 总排行榜

tommyyu

2022-8-18 14:05:27

如图，最坏的情况下就是求  ？处的值，而  ？处的值是所有  ？？处的值的和，一个  ？？处的值又是所有  ？？？处的值的和，这样一直递归下去，可得第三列的未知值就是第2列中的m/2个元素的和，时间复杂度就是m，而第三列有m个未知值，因此求出第三列所有未知值的时间复杂度就是m2。
此时第三列变成了已知值，问题变成了 已知第三列的值求第四列的值，此时的时间复杂度和 已知第二列的值求第三列的值 的时间复杂度一样，都是m2。自此，我们可以推断出 已知上一列的值求下一列的值 的时间复杂度是m2，而这个过程进行了n-2次，时间复杂度就是m2n

跳转到最佳答案楼层

tommyyu

https://www.bilibili.com/video/BV1Ba4y1j75j?p=8
32:51时有这题讲解

柿子饼同学

tommyyu 发表于 2022-8-18 12:32
https://www.bilibili.com/video/BV1Ba4y1j75j?p=8
32:51时有这题讲解

我看答案就看的这个 , 这个跟没解释没区别吧
算了, 反正这种题也只能猜猜了

tommyyu

如图，最坏的情况下就是求  ？处的值，而  ？处的值是所有  ？？处的值的和，一个  ？？处的值又是所有  ？？？处的值的和，这样一直递归下去，可得第三列的未知值就是第2列中的m/2个元素的和，时间复杂度就是m，而第三列有m个未知值，因此求出第三列所有未知值的时间复杂度就是m2。
此时第三列变成了已知值，问题变成了 已知第三列的值求第四列的值，此时的时间复杂度和 已知第二列的值求第三列的值 的时间复杂度一样，都是m2。自此，我们可以推断出 已知上一列的值求下一列的值 的时间复杂度是m2，而这个过程进行了n-2次，时间复杂度就是m2n

tommyyu

tommyyu 发表于 2022-8-18 14:05
如图，最坏的情况下就是求  ？处的值，而  ？处的值是所有  ？？处的值的和，一个  ？？处的值又是所有  ？ ...

其实只要仔细想就可以想出来了，但是这个基本上网上没有人去想，我搜到的答案都说不会，然后没有讲解

柿子饼同学

tommyyu 发表于 2022-8-18 14:05
如图，最坏的情况下就是求  ？处的值，而  ？处的值是所有  ？？处的值的和，一个  ？？处的值又是所有  ？ ...

强啊

嘉岳呀

CSP-J 还是 CSP-S的模拟？

洛谷的我一般不看

柿子饼同学

嘉岳呀 发表于 2022-8-18 17:41
CSP-J 还是 CSP-S的模拟？

洛谷的我一般不看

scpj