多项式求值算法性能评估与对比系统

资 源 简 介

本项目使用MATLAB开发一套专门用于评估和对比多项式求值效率的实验系统。

详 情 说 明

多项式求值四种算法的时间复杂度比较与性能评估系统

项目介绍

本项目是一个基于 MATLAB 开发的实验性评估系统，旨在通过定量分析的方法，对比四种经典多项式求值算法在处理不同阶数多项式时的计算效率。系统通过模拟大规模随机实验，采集各算法段的运行耗时，并生成直观的性能曲线与数值报告，为算法效率研究提供数据支持。

功能特性

1. 多算法集成：系统完整实现了直接幂迭代法、秦九韶算法（Horner's Method）、Estrin 并行结构算法以及 MATLAB 原生内置函数（polyval）四种求值方案。
2. 自动化实验流程：通过设置阶数跨度（10阶至5000阶）和步长，系统可以自动完成多轮测试并记录时间戳。
3. 计算精度校验：以秦九韶算法为基准，对其他算法的结果进行实时误差计算，确保各算法实现的正确性。
4. 可视化分析：通过双子图布局展示耗时增长趋势图和加速比对比图。
5. 详细统计报告：在控制台输出包括平均耗时、相对效率倍数在内的对比表格。

系统要求

• MATLAB R2016b 或更高版本。
• 具备基础图形界面支持（用于显示可视化图表）。

使用方法

1. 在 MATLAB 编辑器中加载该脚本程序。
2. 直接运行程序。系统会自动清理现有工作区、重置随机数种子并开始实验。
3. 运行完成后，查阅产生的实验分析图表。
4. 在 MATLAB 命令行窗口查看自动生成的性能评估报告。

实现逻辑详细说明

1. 环境与参数配置

系统首先固定随机种子（rng 42）以确保实验的可重复性。实验规模设定为最大 5000 阶多项式，采用 250 的步长递增测试。每次实验均在 [-1, 1] 区间内生成 1000 个随机测试点，以模拟真实的计算负担。

2. 核心实验循环流程

系统遍历预设的阶数序列，在每一个阶数节点：

• 随机生成对应的多项式系数向量。
• 依次调用四种算法，使用 tic/toc 精确捕获各算法对所有测试点求值的总耗时。
• 针对内置函数 polyval 的输入特性，自动对系数进行翻转处理以便兼容。
• 每次循环末尾加入误差控制逻辑，若算法间计算结果差异超过 1e-10，则抛出警告提醒。

3. 数据分析与可视化逻辑

• 加速比计算：以直接幂迭代法作为基准（Baseline），计算其他算法相对于基准的提速倍数。
• 统计汇总：计算全量测试样本下的平均运行耗时。
• 图形呈现：

* 第一子图：展示随阶数（Degree）增加，四种算法耗时（Seconds）的增长曲线。 * 第二子图：展示相对于直接法的加速比演变趋势，并绘制基准线。

关键算法实现细节分析

直接幂迭代法 (Naive Direct)

该方法通过遍历多项式的每一项，直接计算自变量 $x$ 的 $i$ 次幂并乘以对应系数。虽然简单直观，但由于涉及大量的幂运算和重复加法，其计算量相对较大。

秦九韶算法 (Horner's Method)

该算法采用由内向外的嵌套形式降低运算次数。其逻辑为：从最高阶系数开始，逐步执行“乘以 $x$ 后加前一阶系数”的操作。该实现将原有的幂运算转化为 $n$ 次乘法和 $n$ 次加法，极大地提升了串行计算效率。

Estrin 并行结构算法 (Estrin's Scheme)

该算法采用分治思想将多项式分解为二叉树结构。具体的代码实现中：

• 使用 cell 数组（layers_coeffs）模拟树的层级。
• 通过 while 循环迭代合并相邻的系数项，合并公式为 $P_{new} = P_{even} + P_{odd} cdot x^{2^k}$。
• 在每一层的迭代中，通过 $x_pow = x_pow cdot x_pow$ 快速更新自变量的幂次（$x^2, x^4, x^8 dots$）。

这种结构在理论上更适合并行处理（CPU 指令集优化或多核环境）。

MATLAB 内置函数 (polyval)

作为系统的对照组，使用官方优化后的内置函数。该函数在底层进行了深度优化，通常代表了在 MATLAB 环境下串行求值的性能上限。