对称矩阵加法和乘法的C语言实现及其时间复杂度分析

本文将展示用C语言实现的两个对称矩阵的加法和乘法算法，并分析其时间复杂度。

代码实现

#include <stdio.h>
#define N 3
#define M N*(N+1)/2

int value(int mat[], int i, int j) //返回存储在a[M]中对应二维数组a[i][j]的值
{
    if (i >= j) return mat[(i*(i+1)/2 + j)];
    else return mat[(j*(j+1)/2 + i)];
}

void input(const char *name, int mat[]) // 输入对称矩阵
{
    int i, j;
    printf("请输入一个%d*%d的对称矩阵%s，共需要输入%d个数 ", N, N, name, M);
    for (i = 0; i < N; i++)
    {
        for (j = 0; j <= i; j++)
        {
            int x;
            scanf("%d", &x);
            mat[value(mat, i, j)] = x;
            if (i != j) mat[value(mat, j, i)] = x;
        }
    }
}

void put(int mat[])
{
    int i, j;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            printf("%4d", value(mat, i, j));
        }
        printf("\n");
    }
}

void add(int a[], int b[], int c[N][N])
{
    int i, j;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            c[i][j] = value(a, i, j) + value(b, i, j);
        }
    }
}

void mult(int a[], int b[], int c[N][N])
{
    int i, j, k;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            c[i][j] = 0;
            for (k = 0; k < N; k++)
            {
                c[i][j] += value(a, i, k) * value(b, k, j);
            }
        }
    }
}

int main(void)
{
    int a[M] = {};
    input("a", a);
    printf("矩阵a为:\n");
    put(a);
    int b[M] = {};
    input("b", b);
    printf("矩阵b为:\n");
    put(b);
    int c1[N][N], c2[N][N];
    printf("a+b=\n");
    add(a, b, c1);
    put(c1);
    printf("a*b=\n");
    mult(a, b, c2);
    put(c2);
    return 0;
}

时间复杂度分析

这段代码的时间复杂度为 $O(N^3)$，因为其中调用了两个 $N^2$ 的循环，以及在矩阵相加、相乘时调用了 $N^2$ 次 value 函数。而 value 函数的时间复杂度为 $O(1)$，可以忽略不计。因此总的时间复杂度为 $O(N^3)$。

代码说明

代码利用了对称矩阵的性质进行优化，减少了存储空间，因为对称矩阵只需要存储一半的元素。
value 函数用于根据下标返回对称矩阵中存储的元素值。
input 函数用于输入对称矩阵，并将其存储在数组中。
put 函数用于输出对称矩阵。
add 函数用于计算两个对称矩阵的加法。
mult 函数用于计算两个对称矩阵的乘法。

这段代码展示了如何用C语言实现对称矩阵的加法和乘法，并分析了其时间复杂度。可以根据实际需要对代码进行修改和扩展。