数据结构算法每日一练（二）Laguerre多项式

1、N次Laguerre多项式 P n ( x ) P_n(x) Pn​(x)的递归定义是：

P 0 ( x ) = 1 P_0(x)=1 P0​(x)=1
P 1 ( x ) = 1 − x P_1(x)=1-x P1​(x)=1−x

P n ( x ) = ( 2 n − 1 − x ) P n − 1 ( x ) − ( n − 1 ) 2 P n − 2 ( x ) ( n > 1 ) P_n(x) = (2n-1-x) P_{n-1}(x) - (n-1)^2 P_{n-2}(x) (n>1) Pn​(x)=(2n−1−x)Pn−1​(x)−(n−1)2Pn−2​(x)(n>1)

(1)请按照上面的定义用递归的方式求n次Lagureer 多项式在x处的值: double laguerre (double x，int n);

(2)给出此递归函数的时间复杂度。

（1）

#include <iostream>
using namespace std;
double laguerre (double x, int n){
 if(n == 0) {
     return 1;
 }else if(n == 1) {
     return 1 - x;
 }else {
     return (2*n - 1 - x) * laguerre(x, n - 1) - (n - 1) * (n - 1) * laguerre(x, n - 2);
 }
}
int main() {
 double x;
 int n ;
 cin >> x >> n;
 double res = laguerre(x, n);
 cout << res << endl;
 return 0;
}

（2）时间复杂度为 O ( 2 n ) O(2^n) O(2n)
分析与上道斐波那契数列一样
数据结构算法每日一练（一）斐波那契数列