首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >空间复杂性分析中的困惑

问空间复杂性分析中的困惑
EN

Stack Overflow用户
提问于 2020-05-27 11:56:30
回答 1查看 69关注 0票数 0

我正在解决关于空间复杂性的问题,当我们谈到空间复杂性时,我们不考虑input.but在下面的代码中使用的空间,我从一个网站上看到,不是应该是O(1)吗,为什么他们说它依赖于n?请澄清我的困惑

代码语言:javascript
复制
 int sum(int A[ ], int n)
{
   int sum = 0, i;
   for(i = 0; i < n; i++)
      sum = sum + A[i];
   return sum;
}

在上面的代码中,它需要'n*2‘字节的内存来存储数组变量'a’2字节的内存对于整数参数'n‘4字节的本地整数变量'sum’和'i‘(每个2字节)2字节的内存作为返回值。

这意味着,它完全需要'2n+8‘字节的内存来完成它的执行。在这里,所需的内存总量取决于'n‘的值。随着'n‘值的增加,所需空间也按比例增加。这种空间复杂性被称为线性空间复杂性。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-05-27 13:17:03

不同的作者和网站使用“空间复杂性”来表示不同的东西,所以您必须检查特定网页的符号。

https://www.studytonight.com/data-structures/space-complexity-of-algorithms表示空间复杂性=辅助空间+输入空间(我假设这与您使用的站点相关)。

https://theory.cs.princeton.edu/complexity/book.pdf将空间复杂度定义为排除输入空间(在这种情况下,输入空间是只读的),这似乎更正常。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/62042568

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档