稀疏矩阵乘法时间代价 A为p×m的矩阵,B为m×n的矩阵, 乘得的结果C为p×n的矩阵 口若矩阵A中行向量的非零元素个数最多为 口矩阵B中列向量的非零元素个数最多为t 总执行时间降低为O(tn+t)×p×n) 经典矩阵乘法所需要的时间代价为 Op×mxn “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 稀疏矩阵乘法时间代价 ◼ A为p×m的矩阵，B为m×n的矩阵， 乘得的结果C为p×n的矩阵 ❑ 若矩阵A中行向量的非零元素个数最多为 ta ❑ 矩阵B中列向量的非零元素个数最多为tb ◼ 总执行时间降低为O((ta+tb )×p×n) ◼ 经典矩阵乘法所需要的时间代价为 O(p×m×n)
稀疏矩阵的应用 一元多项式 P(x)=ao+ax+a2x'+.+a,x ∑ a. 012 degree murDeree coe ao a1 a2 几 十一五”国家級规划教材。张铭,王膳腾蛟,赵海燕,《数据结构与算法》,高教社,B08.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 稀疏矩阵的应用 ◼ 一元多项式 i n i i n n n a x P x a a x a x a x = = = + + + + 0 2 0 1 2 ( )
122广义表和存储管理 中广义表 今储存管理 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 12.2 广义表和存储管理 ◼ 广义表 ◼ 储存管理
1221广义表 基本概念 广义表的各种类型 中广义表的存储 心广义表的周游算法 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 12.2.1 广义表 ◼ 基本概念 ◼ 广义表的各种类型 ◼ 广义表的存储 ◼ 广义表的周游算法
基本概念 回顾线性表 口由n(n≥0)个数据元素组成的有限有序序列 口线性表的每个元素都具有相同的数据类型 如果一个线性表中还包括一个或者多个子表 那就称之为广义表( Generalized lists,也称 Multi-list)一般记作: 0,X “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 基本概念 ◼ 回顾线性表 ❑ 由n（n≥0）个数据元素组成的有限有序序列 ❑ 线性表的每个元素都具有相同的数据类型 ◼ 如果一个线性表中还包括一个或者多个子表， 那就称之为广义表（Generalized Lists，也称 Multi-list）一般记作： ❑ L＝（x0，x1，…，xi，…，xn-1）