数据结构引论和两种复杂度

引论和复杂度

递归对空间的占用巨大

计算多项式在定点的值要用秦九韶算法

算法

一个有限指令集，接受输入，产生输出，有限终止，指令能够执行（实现不依赖计算机语言）

算法的空间复杂度S（n）和时间复杂度T（n）

void printN( int N)
{ if(N){
printN（N-1）；
printf("%d\n",N);
}
retrun;
}
高空间复杂度

一般的多项式的算法的时间复杂度（n^2+n）/2次乘法 c1n ^2+c2n
秦九韶多项式的算法的时间复杂度 n 次乘法 cn

复杂度的渐进表示：上界O 下界$\Omega$Ω 同阶$\theta$θ

if……else代码：取复杂度最大的那一种情况

典例：给定{1，5，-4，9，0，6，-2，7，-9，5，6，7，5，-1，5，3，2}

求所有连续区间的项的和的最大值
（追求nlog2n，这个2应该是算法中总是使用2等分而来的—分而治之）

在线处理算法 n

chapter2

一元多项式的表示与运算
$x^{5}+3x^{3}-4x^{2}+3$x5+3x3−4x2+3
$x^{2000}+1$x2000+1
用一维数组
用结构数组，按指数递降的排列
用链表
|系数| 次数|下一个的位置|

广义表和多重链表

二元多项式？

多重链表

矩阵的表示：

1. 二维数组
2. 十字链表