秦九昭算法——MATLAB实现

一、引入

对于多项式 $f(x)=a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_0$ 而言，要计算 $x=x_0$ 时的函数值时，需要进行 $\frac{(n+1)n}{2}$ 次乘法和n次加法，其时间复杂度为 $O(N^2)$ .

那我们该用一个什么用的方式来降低其时间复杂度呢？

(1条消息) 一套图搞懂“时间复杂度”_12 26 25的博客-CSDN博客https://blog.csdn.net/qq_41523096/article/details/82142747?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168077800216782427453724%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=168077800216782427453724&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-82142747-null-null.142^v81^insert_down1,201^v4^add_ask,239^v2^insert_chatgpt&utm_term=%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&spm=1018.2226.3001.4187这位大佬对时间复杂度的讲解很透彻，大家可以看看

二、秦九昭算法（Horner算法）

下面我们用著名的秦九昭算法来对这个多项式进行简化：

STEP1:提取x

$f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$

$f(x)=(a_nx^{n-1}+a_{n-1}x^{n-2}+...+a_1)x+a_0$

STEP2:继续提取x

$f(x)=((a_n x^{n-2}+a_{n-1}x^{n-3}+...+a_2)x+a_1)x+a_0$

STEP3:继续提取x，直到

$f(x)=((a_n x+a_{n-1})x+...+a_3)x+a_2)x+a_1)x+a_0$

到这里我们不妨令

$u_0=a_n$

则有

$u_{1}=u_0x+a_{n-1}$

$u_{2}=u_1x+a_{n-2}$

...

$u_n=u_{n-1}x+a_0$

综上，我们在求多项式时，首先计算最内层括号里的一次多项式 $u_{1}=u_0x+a_{n-1}$ ，接着不断的往外计算最终可以得到计算结果。

使用秦九昭算法只需要做n次乘法，n次加法，其时间复杂度为 $O(N)$

三、MATLAB实现

这是一个很常用的递归思想

function f=Horner(A,x)        %A为系数向量
    n=length(A);              %确定该多项式的最高次数
    f=A(1);                   %公式里的u0（an）
    for i=1:n:
        f=f*x+A(1+i)          %A(1+i)即为公式里的（an-1）
    end
end

在读大学生，做一些学习记录嘿嘿嘿。大家在看的过程发现什么错误，欢迎大家批评指正！文章来源地址https://uudwc.com/A/dby2v