秦九韶算法

普通算法

f1(x) = a0 + a1x + a2x^2 + ... + an-1x^(n-1) + anx^n

double f1(int n, double a[], double x){
    int i;
    double p = a[0];
    for (int i = 1; i <= n; ++i){
        p += (a[i] * pow(x, i));
    }
    return p;
}

秦九韶算法

每次把x当做公因子提取出来,然后从最里面向外计算。
f2(x) = a0 + x(a1 + x(...x(an-1 + x(an))...))

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;
}

速度测试

#include <iostream>
#include <vector>
#include <time.h>

#define MAXN 10 /* 多项式最大项数,即多项式阶数+1 */
#define MAXK 1e6 /* 被测函数最大重复调用次数 */

using namespace std;

clock_t start, stop;
/* clock_t是clock()函数返回的变量类型 */
double duration;
/* 记录函数运行时间,以秒为单位 */


double f1(int n, double a[], double x){
    int i;
    double p = a[0];
    for (int 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 main(){
    int i;
    double a[MAXN]; /* 存储多项式的系数 */
    for (i = 0; i < MAXN; ++i){
        a[i] = (double)i;
    }

    /* 不在测试范围的准备工作写在clock()调用之前 */
    start = clock(); /* 开始计时 */
    for (int j = 0; j < MAXK; ++j){
        f1(MAXN - 1, a, 1.1);
    }
    stop = clock(); /* 停止计时 */
    duration = ((double)(stop - start)) / CLK_TCK / MAXK;
    printf("f1-duration: %6.2e\n", duration);

    start = clock(); /* 开始计时 */
    for (int j = 0; j < MAXK; ++j){
        f2(MAXN - 1, a, 1.1);
    }
    stop = clock(); /* 停止计时 */
    duration = ((double)(stop - start)) / CLK_TCK / MAXK;
    printf("f2-duration: %6.2e\n", duration);
    return 0;
}
运行结果

分析

可以看出来单次运行的时间上,秦九韶算法比普通算法快了一个数量级。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 姓名:李浩然 学号:16030410020 转自:http://blog.csdn.net/Dreaming_My...
    洛花无阅读 2,682评论 0 1
  • sì 支zhī茶chá 对duì 酒jiǔ,赋fù 对duì 诗shī,燕yàn子zi 对duì 莺yīng 儿é...
    每个人的孟母堂阅读 1,269评论 0 6
  • 遇到问题,没有想法或方案,怎么破?在职场或生活中,我们会遇到很多问题,解决问题成了很多人的难题。解决问题在于洞悉问...
    帅小周阅读 450评论 0 0
  • 让你自卑的理由在别人看来并没有什么,同样,让你骄傲的原因在别人看来也不过如此! -----------------...
    Minilychang阅读 427评论 2 1
  • 和什么样的人在一起,就会有什么样的人生。在生活中,和谁在一起的确很重要,甚至能改变你的成长轨迹,决定你人生成败。 ...
    小蜗牛Tina阅读 967评论 7 6