poly_sum.m

四种不同的算法在实现多项式相乘时的时间复杂度比较

%四种不同的算法在实现多项式相乘时的时间复杂度比较
clear,clc
n=[1000,2000,3000,4000,5000,6000,7000,8000,9000];
m=[1000,2000,3000,5000,7000,10000,15000,20000,30000];
x=2;
for i=1:9
tic,P=poly_sum1(x,n(i));T1(i)=toc;
tic,P=poly_sum2(x,n(i));T2(i)=toc;
tic,P=poly_sum3(x,m(i));T3(i)=toc;
tic,P=poly_sum4(x,m(i));T4(i)=toc;
end
p1=polyfit(n,T1,2);
p2=polyfit(n,T2,2);
p3=polyfit(m,T3,1);   
p4=polyfit(m,T4,1);
n2=1000:50:15000;
m2=1000:100:30000;
T21=polyval(p1,n2);
T22=polyval(p2,n2);
T23=polyval(p3,m2);
T24=polyval(p4,m2);
subplot(2,2,1); plot(n,T1,'O',n2,T21),title('直接求解，O(n^2)')
subplot(2,2,2); plot(n,T2,'*',n2,T22),title('递归求解，O(n^2)')
subplot(2,2,3); plot(m,T3,'+',m2,T23),title('归纳求解，O(n)')
subplot(2,2,4); plot(m,T4,'x',m2,T24),title('Horner规则，O(n)')