稀疏矩阵

稠密度：矩阵中非零元素占元素总数的比例称为矩阵的稠密度

稀疏矩阵：

• 包含大量零元素的矩阵
• 无稠密度硬性指标，通常认为 <5% 的矩阵即可视为稀疏矩阵
• 零元素位置分布没有规律
• 为节省存储空间，可以只存储非零元素

稀疏矩阵的转置算法

方法一

1. 依次访问稀疏矩阵的行三元组表中的各个三元组 <i，j，a_ij>，交换元素行列号后依次保存到 B 的行三元组表中

2. 将 B 的行三元组表中的行三元组按照下标值从小到大重新排序

• 步骤 1 的时间复杂度为 O(t)
• 步骤 2 的时间复杂度采用不同算法在 O(t²) 到 O(tlog₂t)

方法二

1. 对 A 的行三元组表进行第一次扫描，找到列下标 j=0 的所有三元组 <i，j，a_i0>，交换元素行列号后依次保存到 B 的行三元组表中
2. 再次对 j=2 进行同样操作，直到 j=n-1

• 最多进行 n 次扫描，每次都访问所有 t 个非零元，时间复杂度为 O(nt)

快速转置算法（以空间换时间）

时间复杂度 O(n+t)

关键代码 O(t)

• 取出非零元列号
• 去 k 数组中查找位置 index
• 更新 k 数组
• 非零元交换行列号后写入 B 的 index 位置

  for (int i=0;i<t;i++)
  {
  	int index = k[A.table[i].col]++;
  	B.table[index].col = A.table[i].row;
  	B.table[index].row = A.table[i].col;
  	B.table[index].value = A.table[i].value;
  }