多项式相加（两种算法对比）

例题：写程序计算给定多项式在给定点x处的值：

算法一：

根据表达式公式直接编写程序

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

 

算法二：

将表达式写成如下形式，再写程序

double f2(int a[], double x, int n)
{
    double sum = 0;
    int i;
    for (i = n-1; i >= 0; i--)
    {
        sum = a[i] + x*sum;
    }
    
    return sum;
}

 

最后通过计算机的时钟记时来比较两种算法所消耗的时间（关于时钟打点方法文末介绍）

#include <stdio.h>
#include <math.h>
#include <time.h>

#define MAX 10    //设置多项式一共十项 
#define MAXF 1e6    //重复执行函数1000 000次 



double f1(int a[], double x, int n); 
double f2(int a[], double x, int n); 

int main()
{
    clock_t start, stop;
    double duration;
    int a[MAX];
    double x;
    double sum;
    int i;
    x = 2;
    for(i=0; i<MAX; i++)
        a[i] = i+1;
    
    //执行常规算法 
    start = clock();
    for(i=0; i<MAXF; i++)
        sum = f1(a, x, MAX);
    stop = clock();
    duration = ((double)(stop-start))/CLK_TCK;
    
    printf("运算结果为：%.2lf\n", sum);
    printf("常规算法相对运行时间为：%.2lf秒\n", duration); 
    
    //执行优化之后的算法
    start = clock();
    for(i=0; i<MAXF; i++)
        sum = f2(a, x, MAX);
    stop = clock();
    duration = ((double)(stop-start))/CLK_TCK;
    
    printf("运算结果为：%.2lf\n", sum);
    printf("优化算法相对运行时间为：%.2lf秒\n", duration); 

    return 0;
}

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

double f2(int a[], double x, int n)
{
    double sum = 0;
    int i;
    for (i = n-1; i >= 0; i--)
    {
        sum = a[i] + x*sum;
    }
    
    return sum;
}

 运行结果为：

可以看出优化后的算法时间效率明显高于一般算法

 

 clock介绍：

clock()：记录从开始调用到第二次再调用clock()函数所耗费的时间，时间单位为clock tick，即“时钟打点”。

常数CLK_TCK：机器始终每秒的打点数

用法：

 

posted on 2018-12-18 12:58 路漫漫我不畏 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为huwt原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/huwt/p/10136455.html