数组是这样声明的：
int array[M], O(1)in space 还是O(n)? 其中 M 是某个固定值。对我来说O(n)是有道理的，因为它不仅仅是一个变量，而是一个完整的数组。但是我认为这可能是O(1)因为我们有一个固定的大小并且它没有改变！
时间复杂度为 O( n )的算法能否具有O( n 2 ) 或更多的空间复杂度？
我有一个问题.
在理论计算机科学方面,当我们分析算法时,如果算法初始化一个新的数据结构,那么我们认为数据结构是空间复杂性的一部分.
现在我对这部分不太确定.
假设我有一个数组,int我想通过使用int指针映射来映射它们.如
std::map<int*,int*> mymap;
for (int i = 1; i < arraySize; i++) {
mymap[&arr[i-1]]=&arr[i];
}
如果这个算法没有使用指针,那么我们可以清楚地说它正在初始化一个大小为n的映射,因此空间复杂度是O(n),但是对于这种情况,我们使用指针的地方,空间复杂度会是多少这个算法？
我正在寻找guava TreeRangeMap,它似乎非常适合我对项目的需求.java文档说它基于(java标准？)TreeMap,它具有get(put和next)的O(log(n))时间.
但TreeRangeMap应该是某种范围树实现,根据这个SO问题,查询的O(k + log(n))时间复杂度为O(n)空间,k为范围大小？有人可以证实这一点吗？
我对TreeRangeMap.subRangeMap()操作的时间复杂性也很感兴趣.它是否具有相同的O(k + log(n))？
谢谢.
对于一个简单的程序:
public class solution{
public void start(int m, int n){
for(int i = 0; i < m; i++)
recur(n);
}
public void recur(int n){
for(int j = 0; j < n; j++)
recur(n-1);
}
}
谁能帮助我分析空间复杂性？我认为是O(m*n).
谢谢.
这直接取自 Gayle Lakmaan McDowell 的 Cracking the coding interview。
她列出了以下代码：
int f(int n) {
if(n<=1){
return 1;
}
return f(n-1) + f(n-1);
}
她清楚地解释了为什么时间复杂度是 O(2^n)，但为什么这里的空间复杂度只有 O(N)？
因此，我在实习中遇到了编码挑战，其中一部分是确定我的程序的空间和时间复杂性。程序大致如下。
while(A){
int[][] grid;
// additional variables
while(B){ //for loop involves iterating through grid
// additional variables
for(...)
for(....)
}
for(...) //for loop involves iterating through grid
for(....)
}
所以我说的是，程序总体的时间复杂度为 (A N^2+B N^2)，因此得出结论，它的摊余时间为 O(N^2)。
至于空间复杂度，我是否应该将所有变量使用的数字空间相加？假设每个变量都是 int，并且循环 A 中有 3 个变量，循环 B 中有 2 个变量，那么空间复杂度是 (A*24 + B*16)？
什么是空间复杂度以及我们如何获得它？（其中a和b是大小为N和的数字数组M）
a.filter(function(v) {
return !b.includes(v);
})
在计算算法的空间复杂度时，我们被告知找出额外空间的最简单方法是创建数据结构，如 Set、Map、Stack 等。
以下面的代码为例，它尊重字符串（在Java中）
private String reverse(String string){
if (string == null || string.length() == 0) return string;
char[] strArray = string.toCharArray(); // Does this consume space?
int first = 0, last = strArray.length - 1;
while (first < last){
char temp = strArray[first];
strArray[first++] = strArray[last];
strArray[last--] = temp;
}
return String.valueOf(strArray);
}
str转字符数组会占用空间吗