[项目003] 多项式的时间复杂度 隐藏答案 | 返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。

最后更新：2023年8月19日

---

【实验目的】

1. 熟练使用循环语句。
2. 熟练掌握使用系统函数 clock() 测试程序运行时间的方法。
3. 学会对比分析程序的时间复杂度和实际运行时间。

【实验内容】

分别使用直接法和秦九韶法测试和分析多项式的时间复杂度和实际运行效率。令 $f(x) = 1 + \sum^{100}_{i=1} x^i/i$，计算 $f(1.2)$ 的值。提示：利用 clock() 函数得到两种算法在同一台计算机上的运行时间。

【实验要求】

1. 将程序代码及实验结果整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。

2. 实验代码包括1个 '.C' 文件或者 '.cpp' 文件，代码中直接输出两种算法的运行时间。

3. 实验报告要求明确对比时间复杂度和实际运行时间。

【参考代码】

#include <stdio.h>
#include <time.h>
#include <math.h>
clock_t start, stop;     // clock_t是clock()函数返回的变量类型
double single, duration; // 以秒为单位记录被测函数的单次执行时间和总执行时间，以秒为单位
#define MAXN 100          // 定义多项式的最大项数
#define MAXK 1e6         // 定义被测函数重复调用的最大次数
#define VALUE_X 1.2

// 1. 定义函数f1，计算 a*x^n 序列。
// f(x) = a_0 + a_1 x +...+ a_{n-1} x^{n-1} + a_n x^n
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;
}

// 2. 定义函数f2，计算 a*x 序列。
// f(x) = a_0 + x(a_1 + x(...(a_{n-1} + x(a_n))...)
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;
}

// 3. 循环遍历函数f1,f2，并输出时间统计结果
int main()
{
    // 3.1 定义多项式的系数
    int i;
    double a[MAXN];
    for (i = 1; i < MAXN; i++)
        a[i] = 1/(double)i;

    // 3.2 对函数f1进行MAXK次遍历，并输出单次执行时间和总执行时间
    start = clock();                               // 开始计时
    for (i = 0; i < MAXK; i++)                     // 被测函数循环执行MAXK次
        f1(MAXN - 1, a, VALUE_X);                  // 执行被测函数f1
    stop = clock();                                // 停止计时
    duration = ((double)(stop - start)) / CLK_TCK; // 计算总执行时间
    single = duration / MAXK;                      // 计算单次执行时间
    // printf("f1_duration = %f \n", duration);       // 输出总执行时间
    printf("f1_single = %7.2e \n", single);        // 输出单次执行时间

    // 3.3 对函数f2进行MAXK次遍历，并输出单次执行时间和总执行时间
    start = clock();                               // 开始计时
    for (i = 0; i < MAXK; i++)                     // 被测函数循环执行MAXK次
        f2(MAXN - 1, a, VALUE_X);                  // 执行被测函数f2
    stop = clock();                                // 停止计时
    duration = ((double)(stop - start)) / CLK_TCK; // 计算总执行时间
    single = duration / MAXK;                      // 计算单次执行时间
    // printf("f2_duration = %f \n", duration);       // 输出总执行时间
    printf("f2_single = %7.2e \n", single);        // 输出单次执行时间

    return 0;
}

f1_single = 9.39e-07 
f2_single = 1.83e-07