首页 > 试题广场 >

假设包含t个非零元素的稀疏矩阵A含有m行n列，并采用三元组顺

[单选题]
假设包含t个非零元素的稀疏矩阵A含有m行n列，并采用三元组顺序表压缩存储，其快速转置算法的时间复杂度为（    ） 
  • O（m+t）
  • O（n+t）
  • O（m+n）
  • O（m*n）
查看正确选项
添加回答
jamke头像 jamke
快速转置：
1.初始化所有列的非零元素的个数统计为0（n）
2.统计每一列的非零元素个数（t）
3.接着求每一列第一个非零元素的首位置（n）
4.最后对每一个非零个数转置（t）。
总共时间：2*（n+t）
于是，时间复杂度：O（n+t）

PS：
参考1中“Cpot[0]是留给储存三元表行列数和非零元个数的。”的这句不正确。
参考2中的
for(col=2; col<=M.tu; ++col) cpot[col]=cpot[col-1]+num[col-1]; //2.统计每一列的非零元素个数（t）
应该是：
for(col=2; col<=M.nu; ++col) cpot[col]=cpot[col-1]+num[col-1];//2.统计每一列的非零元素个数（t）
编辑于 2019-05-16 10:04:20 回复(0)
牛客291046824号头像 牛客291046824号
发表于 2018-07-24 19:07:46 回复(2)
阳光下的米雪头像 阳光下的米雪
压缩存储一般是变成上三角或者下三角，然而这个矩阵是转置，所以应该为O(n+t)
发表于 2019-05-07 11:56:31 回复(0)
学术废物头像 学术废物
三元组表要做的是反转后排序 我感觉只跟t有关……？
发表于 2022-03-19 17:53:21 回复(0)
对方正在输入...21头像 对方正在输入...21

B

发表于 2018-07-09 00:01:52 回复(1)
提交观点

问题信息

复杂度
上传者：逍遥20180616142306
难度：
5条回答 5688浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号