想问一下如果单纯用c语言递归是不是一定会超时啊，我是只学过c语言的小白

hongjingxuan @ 2022-11-23 14:47:29

#include<stdio.h>
long long louti(long long n){
 if(n==1)return 1;
 if(n==2)return 2;
 else return louti(n-1)+louti(n-2);
}
int main(){
 long long n;
 scanf("%lld",&n);
 printf("%lld",louti(n));
 return 0;
}

by WaterSun @ 2022-11-23 14:51:40

@hongjingxuan 你可以用记忆化呀。

by WaterSun @ 2022-11-23 14:54:04

@hongjingxuan 而且这题还要用高精度吧。

by liuzr156 @ 2022-11-23 14:56:11

这题的n最大到5000，本蒟蒻没记错的话你这个是O(2^n)的时间复杂度的，这题要用递推以O(n)的时间复杂度过。其次这题要用高精度。

by A1C3 @ 2022-11-23 14:58:48

@hongjingxuan 你这超时是肯定的，而且还要高精度。

by Madsome @ 2022-11-23 15:09:53

@liuzr156 复杂度是O(fib(n))

by Mysterious_Cat @ 2022-11-23 15:15:34

@_Mizuki 复杂度是 O(2^n)，因为平时没有人用 O(fib(n))

by As_Snow @ 2022-11-23 15:19:22

显然会炸

by As_Snow @ 2022-11-23 15:19:42

你用什么语言好像都差不多

by Zhen_Dea @ 2022-12-06 23:42:55

我用的c语言递归写的,一开始得数都一样,但月靠后越慢,而且得数也不一样了,所以要用高精度