我正在解决关于空间复杂性的问题,当我们谈到空间复杂性时,我们不考虑input.but在下面的代码中使用的空间,我从一个网站上看到,不是应该是O(1)吗,为什么他们说它依赖于n?请澄清我的困惑
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‘值的增加,所需空间也按比例增加。这种空间复杂性被称为线性空间复杂性。
发布于 2020-05-27 13:17:03
不同的作者和网站使用“空间复杂性”来表示不同的东西,所以您必须检查特定网页的符号。
https://www.studytonight.com/data-structures/space-complexity-of-algorithms表示空间复杂性=辅助空间+输入空间(我假设这与您使用的站点相关)。
https://theory.cs.princeton.edu/complexity/book.pdf将空间复杂度定义为排除输入空间(在这种情况下,输入空间是只读的),这似乎更正常。
https://stackoverflow.com/questions/62042568
复制相似问题