试题详情
- 简答题若在矩阵A中存在一个元素ai,j(0≤i≤n-1,0≤j≤m-1),该元素是第i行元素中最小值且又是第j列元素中最大值,则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A,试设计一个求该矩阵所有马鞍点的算法,并分析最坏情况下的时间复杂度。
- 在矩阵中逐行寻找该行中的最小值,然后对其所在的列寻找最大值,如果该列上的最大值与该行上的最小值相等,则说明该元素是鞍点,将它所在行号和列号输出。
具体算法如下:
分析算法,外层for循环共执行n次,内层第一个for循环执行m次,第二个for循环最坏情况下执行n
次,所以,最坏情况下的时间复杂度为O(mn+n2)。分析算法,外层for循环共执行n次,内层第一个for循环执行m次,第二个for循环最坏情况下执行n
次,所以,最坏情况下的时间复杂度为O(mn+n2)。 关注下方微信公众号,在线模考后查看
热门试题
- 数据结构在计算机中的表示是指()
- 设如下图所示的二叉树B的存储结构为二叉链
- 简述稳定排序和不稳定排序的含义。
- 在执行某个排序算法过程中,出现了排序码朝
- 已知有实现同一功能的两个算法,其时间复杂
- 假定一个待哈希存储的线性表为(32,75
- 设矩阵A是一个对称矩阵,为了节省存储,将
- 下面关于B-和B+树的叙述中,不正确的是
- 数据结构里,6个顶点的有向图,最多有()
- 图所示是一个无向带权图,请分别按Prim
- 举例说明顺序队列的“假溢出”现象。
- 单链表
- 若某线性表最常用的操作是存取任一指定序号
- 一个串的任意个连续的字符组成的子序列称为
- 若二叉树的一个叶子结点是某子树中根遍历序
- 已知数据序列为(12,5,9,20,6,
- 下面()的时间复杂性最好,即执行时间最短
- 某二叉树的中序遍历序列为:DEBAC,后
- 评价排序算法优劣的主要标准是()和()
- 用某种排序方法对线性表(25,84,21