C++环境下n阶下三角矩阵两种存储的复杂度及数组大小查询

下三角矩阵两种存储方式的复杂度与空间占用对比 #

一、时间复杂度对比 #

首先明确前提：你提到的常规存储O(n²)是遍历整个n×n 2D数组（包含上三角无效占位元素）的时间开销。

• 改用1D数组压缩存储下三角矩阵后，时间复杂度不是O(n)，量级仍然为O(n²)，仅常数系数比2D存储更小。
• 核心逻辑：下三角矩阵的有效元素总数是固定值，第1行1个、第2行2个……第n行n个，总和为n(n+1)/2 ≈ n²/2。不管用2D还是1D存储，遍历所有有效元素的渐进时间复杂度都是O(n²)，区别仅在于1D存储不需要跳过无效的上三角元素，实际运行耗时更低。
• 随机存取单个元素的时间复杂度：两种存储方式都是O(1)。2D存储直接用a[i][j]寻址即可，1D存储仅需要做一次常数级的偏移量计算：行优先存储规则下，i行j列（下标从0开始、且满足i≥j）的偏移量为i*(i+1)/2 + j，直接取a[偏移量]即可。

二、C++环境下的数组大小对比 #

我们以元素为常见的double类型（单元素占8字节）为例，两种存储的数组大小如下：

• 常规2D存储方案
  需要分配n行n列的数组，总元素个数为n²。
  代码示例：vector<vector<double>> mat(n, vector<double>(n));
  总空间占用为n² * sizeof(元素类型)字节，以n=1000的矩阵为例，总占用为1000*1000*8 = 8MB。
• 1D压缩存储方案
  仅需要分配容纳所有有效元素的1D数组，总元素个数为n*(n+1)/2。
  代码示例：vector<double> mat(n*(n+1)/2);
  总空间占用为n*(n+1)/2 * sizeof(元素类型)字节，同样以n=1000的矩阵为例，总占用约为1000*1001/2 *8 = 4.004MB，比2D存储节省近一半空间。

三、误区澄清 #

不要把空间复杂度的量级和存储系数搞混：下三角矩阵的1D压缩存储和常规2D存储的空间复杂度渐进阶都是O(n²)，仅常数系数更小，不存在降低到O(n)的情况。只有对角矩阵等有效元素总数为O(n)的特殊矩阵，压缩存储后的空间复杂度才会达到O(n)。

内容的提问来源于stack exchange，提问作者mia.tt