秦九韶算法的思想与解多项式算法时间比较附代码-白红宇的个人博客

秦九韶算法的思想与解多项式算法时间比较附代码

发布日期：2021-05-10 14:12:47 浏览次数：19 分类：精选文章

本文共 2300 字，大约阅读时间需要 7 分钟。

多项式求值与秦九韶算法

一、引言

　　多项式函数常常用于描述现实世界的各种规律，而在用计算机计算多项式的值的时候，不同算法的计算时空复杂度通常不一样。如一个n次多项式

　　f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0],我们的常规计算办法是，直接计算，这样我们的时间复杂度为:O(n^2)

下面我们介绍秦九韶算法：

其核心思想：后面每一次计算都依赖于前面计算的结果，这样以减少重复的计算。

简单引例:

计算 x^8 直接算将算8次乘法，而这8次都是必要的吗？显然不是，当我们知道x^2的值后，计算x^4只需要用x^2*x^2即可。秦九韶算法正是这样来减少计算量的。

一、推导

　　a0--->an依次是最高项，到常数项系数

　　从而bn就是所求的解

三、算法描述

由以上推导知，bn就是我们所求的值，要求bn就得逆推到b0,由于b0=a0我们就可以求出b1依次下去就可以求出bn。

数据结构:

1.数组

1.a[]用于保存系数

ps:一般做法还需要保存b[],我们这里只是用到前一项，所以一个常数即可

c++实现：

#include 
         
          using namespace std;inline double calculate(double x, double* a, int n)/*    x:f(x)中的x。a是系数数组*/{    double b = a[0];    for (int i = 1 ; i <= n; i++)    {        b = b * x + a[i];    }    return b;}

int main(int argc, char const argv[])

{

double x = 0;
int n = 0;
cout << “最高项幂:”;
cin >> n;
double a = new double[n+1];

cout << “\n请输入个项系数（系数为0输入0）：”;

for (int i = 0; i <= n; i++)

{

cin >> *(a + i);

}

cout<<"\n要计算的x:";

cin>>x;

double res = calculate(x, a, n);

cout << res << endl;

return 0;

}

MyTest.cpp : 定义控制台应用程序的入口点。/*时间测量函调用*/#include "stdafx.h"#include 
   
    #include 
    
     #include 
     
      #pragma warning(disable:4996)#define  MAXN 10#define MAXK 1e4 //代表10的7次方/*f(x)=a0 +a1*x+a2*x*x+a3*x*x*x +...+an*x的N次方  */clock_t start,stop;/*clock_t是clock()函数返回的变量的类型*/double duration;/*记录被测函数运行的时间,以秒为单位*/double f1(int n, double a[], double x){	int i;	double p = a[0];	for (i = 1; i <= n; i++){		p += a[i] * pow(x, i);	}	return p;}/*         秦九韶算法          */double f2(int n, double a[], double x){	int i;	double p = a[n];	for (i = n; i > 0; i--){		p = a[i - 1] + x*p;	}	return p;}int _tmain(int argc, _TCHAR* argv[]){	/*不在测试范围内的准备函数,写在开始之前*/	int i;	double a[MAXN];	for (i = 0; i < MAXN; i++)a[i] = (double)i;	start = clock();	for (i = 0; i < MAXK;i++)		f1(MAXN - 1, a, 1.1);	stop = clock();	duration = ((double)(stop - start)) / CLK_TCK / MAXK;	/*其他不在测试范围外的处理写在后面*/	printf("ticks1 = %f\n", (double)(stop - start));	printf("duration1 = %6.2e\n", duration);	start = clock();	for (i = 0; i < MAXK;i++)		f2(MAXN - 1, a, 1.1);	stop = clock();	duration = ((double)(stop - start)) / CLK_TCK/MAXK;	/*其他不在测试范围外的处理写在后面*/	printf("ticks2 = %f\n", (double)(stop - start));	printf("duration2 = %6.2e\n", duration);	/*%6.2e  表示6表示输出长度（包含小数点），2表示输出小数点位数，	d表示输出为十进制	e表示用科学计数法表示*/	return 0;}

上一篇：Visual Studio添加Visual Basic Power Packs工具箱

下一篇：数据结构与算法新解

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

多项式求值与秦九韶算法

发表评论

最新留言

关于作者

推荐文章