递归的时间复杂度
洛谷2020初赛模拟第16题, 这个算复杂度的题不会, 求助, 代码如下#include<iostream>using namespace std;
#define MAXN 20
int gu;
int luo(int n, int m) {
if(n <= 1 || m < 2)
return 1;
if(gu != -1)
return gu;
int ans = 0;
for(int i = 0; i < m; i += 2)
ans += luo(n - 1, i);
gu = 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 = -1;
cout << luo(n, m);
return 0;
}
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时有这题讲解
我看答案就看的这个 , 这个跟没解释没区别吧
算了, 反正这种题也只能猜猜了{:10_266:} 如图，最坏的情况下就是求？处的值，而？处的值是所有？？处的值的和，一个？？处的值又是所有？？？处的值的和，这样一直递归下去，可得第三列的未知值就是第2列中的m/2个元素的和，时间复杂度就是m，而第三列有m个未知值，因此求出第三列所有未知值的时间复杂度就是m2。
此时第三列变成了已知值，问题变成了 已知第三列的值求第四列的值，此时的时间复杂度和 已知第二列的值求第三列的值 的时间复杂度一样，都是m2。自此，我们可以推断出 已知上一列的值求下一列的值 的时间复杂度是m2，而这个过程进行了n-2次，时间复杂度就是m2n 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
页:
[1]