面试题：C语言中稀疏矩阵存储的时空权衡

存储方式

对于大规模稀疏矩阵，常见的存储方式是三元组（Triplet）存储法。其基本思想是只存储矩阵中的非零元素，每个非零元素用一个三元组 (i, j, value) 表示，其中 i 是行下标，j 是列下标，value 是该位置的元素值。同时，再用一个结构体来管理这些三元组，如下：

#include <stdio.h>
#include <stdlib.h>

// 定义三元组结构体
typedef struct {
    int row;
    int col;
    int value;
} Triplet;

// 定义稀疏矩阵结构体
typedef struct {
    Triplet *data;
    int rows;
    int cols;
    int num_nonzero;
} SparseMatrix;

// 创建稀疏矩阵
SparseMatrix* createSparseMatrix(int rows, int cols, int num_nonzero) {
    SparseMatrix *matrix = (SparseMatrix*)malloc(sizeof(SparseMatrix));
    matrix->rows = rows;
    matrix->cols = cols;
    matrix->num_nonzero = num_nonzero;
    matrix->data = (Triplet*)malloc(num_nonzero * sizeof(Triplet));
    return matrix;
}

// 插入非零元素
void insertElement(SparseMatrix *matrix, int row, int col, int value) {
    static int index = 0;
    matrix->data[index].row = row;
    matrix->data[index].col = col;
    matrix->data[index].value = value;
    index++;
}

空间复杂度优势

常规矩阵存储：对于一个 m * n 的矩阵，如果使用二维数组存储，空间复杂度为 $O(m \times n)$。
三元组存储：对于稀疏矩阵，假设非零元素个数为 k，三元组存储法只需存储 k 个三元组以及矩阵的行数 m、列数 n 和非零元素个数 k，空间复杂度为 $O(k)$。因为稀疏矩阵中 k << m \times n，所以三元组存储法在空间上有显著优势。

矩阵加法时间复杂度

算法思路：遍历两个稀疏矩阵的三元组，比较当前元素的行和列，若相同则相加并插入结果矩阵，否则将较小的元素直接插入结果矩阵。
时间复杂度：假设两个稀疏矩阵非零元素个数分别为 k1 和 k2，最坏情况下需要遍历完两个矩阵所有非零元素，时间复杂度为 $O(k1 + k2)$。

矩阵乘法时间复杂度

算法思路：对于矩阵乘法 C = A * B，A 矩阵的每一行与 B 矩阵的每一列进行点乘。在稀疏矩阵中，通过遍历 A 矩阵的每一个非零元素，找到 B 矩阵中对应列的非零元素进行相乘并累加。
时间复杂度：假设 A 矩阵非零元素个数为 k1，B 矩阵非零元素个数为 k2，对于 A 矩阵的每个非零元素，在最坏情况下需要遍历 B 矩阵所有非零元素，时间复杂度为 $O(k1 \times k2)$。

空间时间权衡

增加空间以降低时间复杂度：
- 采用十字链表法：十字链表为每个非零元素建立行指针和列指针，这样在矩阵乘法时，查找对应行列的非零元素更高效。虽然十字链表的空间复杂度比三元组略高，但其在矩阵乘法等操作上的时间复杂度会降低。
- 预计算和存储部分结果：在矩阵乘法中，可以预先计算并存储一些中间结果，例如 A 矩阵每行与 B 矩阵每列的部分乘积。这样虽然增加了空间使用，但在后续计算中可以减少重复计算，降低时间复杂度。

综上所述，三元组存储法在空间上对稀疏矩阵有显著优势，而在操作时间复杂度和空间使用之间需要根据具体应用场景进行权衡。

星途面试题库