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

img


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

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

前面第一行创建了一个指针的数组
后面循环，为每个数组分配了一个n长度的空间
分配的空间类似一个倒三角形
是n+1/2(n*n)，去掉了低阶项和常数系数，所以是n^2

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7782216
  • 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：任意给定一个正整数N， 如果是偶数，执行： N / 2 如果是奇数，执行： N * 3 + 1 生成的新的数字再执行同样的动作，循环往复。 通过观察发现，这个数字会一会儿上升到很高， 一会儿又降落下
  • 除此之外, 这篇博客: 给定一个大小为n的非空整数数组，找出使所有数组元素相等所需的最小移动数，其中移动将n-1元素增加1中的 代码 部分也许能够解决你的问题。
  • 以下回答由chatgpt基于相关博客总结生成:

    问题涉及到一个二维数组，数组有n行，每行分别有1,2,3,...n列。你想要了解为什么要使用二维数组以及如何计算它的空间复杂度。

    首先，二维数组可以用来表示具有行和列的数据结构。在这种情况下，每一行都代表一个数字序列，序列的长度逐行递增。这种数据结构可以用于解决问题，并且在LeetCode上经常出现。例如，给定一个整数n，要求输出一个二维数组，其中每一行都是从1到n的自然数序列。

    现在，让我们来计算这个二维数组的空间复杂度。

    首先，我们需要了解一个二维数组在内存中的存储方式。二维数组在内存中是以连续的方式存储的，即每一行都相邻存放。假设我们的二维数组有n行，每行分别有1,2,3,...n列。那么，第一行需要1个单位的空间，第二行需要2个单位的空间，以此类推，第n行需要n个单位的空间。

    计算整个二维数组的空间复杂度时，我们要计算每一行所需的空间并求和。具体计算方法如下：

    1. 初始化一个变量totalSpace为0，用于记录总的空间消耗。
    2. 使用一个for循环，从1到n遍历每一行，假设当前行数为i。
      • 累加totalSpace的值，加上i，表示当前行需要的空间。
    3. 最后的总空间复杂度就是totalSpace的值。

    下面是示例代码：

    int calculateSpaceComplexity(int n) {
    int totalSpace = 0;
    for (int i = 1; i <= n; i++) {
        totalSpace += i;
    }
    return totalSpace;
}

    这个函数接受一个整数n作为输入，并返回二维数组的总空间复杂度。你可以调用这个函数来获取具体的空间复杂度值。

    希望这个解答对你有帮助，如果还有其他问题，请随时提问。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632