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

柿子饼同学

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

#include<iostream>
using namespace std;
#define MAXN 20
int gu[MAXN][MAXN];
int luo(int n, int m) {
    if(n <= 1 || m < 2)
        return 1;
    if(gu[n][m] != -1)
        return gu[n][m];
    int ans = 0;
    for(int i = 0; i < m; i += 2)
        ans += luo(n - 1, i);
    gu[n][m] = ans;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < MAXN; i++)
        for(int j = 0; j < MAXN; j++)
            gu[i][j] = -1;
    cout << luo(n, m);
    return 0;
} 

最佳答案

月排行榜 / 总排行榜

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