已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、..

2019年上半年上午试卷综合知识

第 62 题


知识点	递归式矩阵算法设计实例
关键词	空间复杂度时间复杂度实例算法
章/节	计算机软件知识

已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵A₁A₂......A_n相乘的计算顺序具有最优子结构，即A₁A₂......A_n的最优计算顺序包含其子问题A₁A₂......A_k和A_k+1A_k+2……A_n（1≤k<n）的最优计算顺序。
可以列出其递归式为：

其中，A_i的维度为p_i-1*p_i，m[i,j]表示A_iA_i+1……A_j最优计算顺序的相乘次数。
先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策略为（62）。算法的时间复杂度为（63），空间复杂度为（64）。
给定一个实例，（p₀p₁……p₅）=（20,15,4,10,20,25），最优计算顺序为（65）。

A. 分治法

B. 动态规划法

C. 贪心法

D. 回溯法

相关试题算法分析基础

第64题

2018年下半年

在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视..

第65题

2019年上半年

已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n..

第64题

2011年上半年

某算法的时间复杂度可用递归式=表示，则正确的是（64）。

知识点讲解

· 递归式

· 矩阵

· 算法设计

· 实例

递归式

从算法的结构上看，算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单，本小节主要讨论递归算法的时间复杂度分析方法。

（1）展开法。将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直至得到一个求和表达式及其结果。

（2）代换法。这一名称来源于当归纳假设用较小值时，用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤：猜测解的形式；用数学归纳法找出使解真正有效的常数。

（3）递归树法。递归树法弥补了代换法猜测困难的缺点，它适于提供"好"的猜测，然后用代换法证明。在递归树中，每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时，递归树的方法尤其有用。

（4）主方法。也称为主定理，给出求解以下形式的递归式的快速方法，即

T(n)=aT(n/b)+f(n)

式中，a≥1和b>1是常数；f(n)是一个渐进的正函数。

矩阵

特殊矩阵

若矩阵中元素（或非零元素）的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。

对称矩阵：若矩阵A_n_×_n中的元素有

a_ij=a_ji1≤i,j≤n

则称之为n阶对称矩阵。

上（下）三角矩阵：矩阵的上（下）三角（不包括对角线）中的元素均为常数或零。

对角矩阵：矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。

稀疏矩阵

在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。存储稀疏矩阵的非零元素时必须同时存储其位置（行、列号），用三元组（i,j,a_ij）可唯一确定矩阵中的一个元素。因此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。

稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。

算法设计

通常求解一个问题可能会有多种算法可供选择，选择的主要标准首先是算法的正确性和可靠性、简单性和易理解性；其次是算法所需要的存储空间更少和执行速度更快等。

算法设计是一件非常困难的工作，通常设计一个"好"的算法应考虑达到正确性、可读性、健壮性、效率与低存储量需求等目标。

经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪心法、回溯法、分治法和动态规划法等。

实例

某考务处理系统有如下功能：

（1）对考生送来的报名单进行检查。

（2）对合格的报名单进行检查。

（3）对阅卷站送来的成绩清单进行检查，并根据考试中心指定的合格标准审定合格者。

（4）制作考生通知单（内含成绩合格／不合格标志）送给考生。

（5）按地区、年龄、文化程度、职业和考试级别等进行成绩分类统计和试题难度分析，产生统计分析表。

该考务处理系统的分层数据流图如下图所示。

考务处理系统分层数据流图

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5