C语言初阶数据结构空间复杂度计算

Question

希望有兄弟解释一下，为什么此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,...n列，所以是n(n + 1)/2个元素空间，空间复杂度为n^2

Answer 1

int** s = (int**)malloc(n * sizeof(int*)); 
//这一行代码申请了n个空间，用于保存n个地址（指针）

while (n--) //执行n次循环
    s[n] = (int*)malloc(n * sizeof(int)); //每次循环申请n个空间，这里n递减

//整个内存分配状态如下：
/*
1 2 3 4 ... n-1  n
1 2 3 4 ... n-1
...
1 2 3 4
1 2 3
1 2
1
*/

//所以，while循环总共申请的空间是 n * (n+1)/2，s就是一个不规则的二维数组

//这块代码总共申请的内存空间是 n + n * (n+1)/2 ,空间复杂度一般只用最高次幂来表示，
//所以，这段代码的空间复杂度就是n^2