空间复杂性的例子
所以我想知道什么时候在for循环中创建对象（或基元），这是如何影响空间复杂性的？
例如，继承人一个代码示例：
public boolean checkUnique(String p){
int term = -1;
int len = p.length();
for (int i =0; i<len; i++) {
char c = p.charAt(i);
StringBuilder sb = new StringBuilder(p.substring(0, i));
sb.append(p.substring(i+1, len));
String str = sb.toString();
if (str.indexOf(c) != term) {
return false;
}
}
return true;
}
所以我试图分析这种算法的空间复杂性。 它看起来像是O（n）。 我的推理：迭代次数等于输入大小，并且在每次迭代中我们都创建了一个StringBuilder对象，因此我们创建了与输入大小成比例的StringBuilder对象。 同样的推理可以应用于我们在每次迭代中创建String对象和char的事实。 这个推理是否正确？
我问的原因是因为我遇到了一个算法，在每次迭代之后进行以下分配：
int val = str.charAt(i);
然而这个算法具有O（1）空间复杂度。 所以我的理解一定是不正确的呢？ 在这种情况下，checkUnique算法的空间复杂度也是O（1）。
我将讨论这个算法中的糟糕的设计决策，并提出更好的建议。
现有的答案很好地回答了复杂类问题，但是不要指出问题中的错误：您的空间复杂度为O（N），因为您复制了整个输入（减去一个字符）。
如果循环在每次迭代时保持临时副本，则空间复杂度将与时间复杂度匹配：O（N * M），其中M是包含副本的最短前缀的长度。 （或者如果没有重复，则M = N ）。
鸽子的原理确保M <= 216（一个char的唯一值的数量）。
对任何算法的优化总是返回true，如果input.length() > Character.MAX_VALUE 。 （或者对于input.length() > Character.MAX_CODE_POINT ， input.length() > Character.MAX_CODE_POINT ，它是1114111）
如果你的输入中有很多是ASCII码，那么M最多就是80。 实际上，大多数语言不使用许多不同的代码点，即使范围不是从0开始。我想，非字母语言可以有几千个字形。 但无论如何，重要的是，在字符串的早期部分检查重复是很有用的，而不是在第一个字符是唯一的时候执行扫描整个潜在巨大字符串的任何内容。
扰流板：为Set添加字符是迄今为止找到重复的最佳方式。 O（M）时间和空间，低常数因子开销。
除了性能之外，请记住Java char是utf16，但某些Unicode代码点具有多字符编码。 对于Java来说，真的很不幸，它得到了两个世界中最糟糕的结果：与ASCII的utf8相比，空间使用量增加了一倍，但仍然不得不处理多元素“字符”。 当设计Java时，16位就足以容纳任何Unicode字符，所以utf16避免了像utf8这样的多字节字符编码的困难。 宽字符已经流行了一段时间，也许还在Windows，IDK上。 Unix / POSIX / Internet协议在utf8上对一切都非常标准化。
它看起来像迭代代码点的最佳方式是
int cp = str.codePointAt(pos);
pos+=Character.charCount(cp);
循环i = 0..N并且执行codePointAt(i)可能必须从每次迭代的字符串开头扫描以找到代理对。 一个智能的JVM可能会注意到冗余和优化，但我不会指望它。
分析原始算法
这个循环遍历每个角色的基本设计，并检查所有其他角色，这是很有意义的，很容易想到。 有很多冗余的工作（当我们已经知道a!=b时，检查a==c和b==c ），所以它将是O（N2）（见下面的差异算法），但是我们可以实现它的开销比你的版本低很多。
i也很便宜。 有很多方法可以避免每次重新复制字符串：
将它复制一次到一个char[]数组中，并通过修改它将当前的字符考虑在内。 （例如， c = tmpbuf[i]++;搜索tmpbuf for c ， tmpbuf[i]-- ）。
将其复制一次到一个StringBuffer中，并像buf.setCharAt(int, char)一样修改当前位置。 然后你可以像以前一样使用StringBuffer.indexOf() 。 Hrm，只有String对单个字符有indexOf的专门化，所以.toString().indexOf()可能会更好。 对于StringBuilder也是如此：只有indexOf(String) 。 （不要试图使用deleteCharAt（）和insert（），因为它们可能是通过洗牌剩下的元素来实现的）。
由于数组搜索的主库函数建议对原始类型的数组（如char ）不起作用，因此您可以手动循环并跳过i 。 取决于JVM，使用charAt循环输入字符串手册可能同样快。
使用indexOf的多个arg版本之一： String.indexOf(int ch, int fromIndex)从开始搜索（期望搜索停止在位置i ），然后从i+1 （期待未找到） 。
使用String.lastIndexOf(int ch)向后搜索。 期待它回归i 。 或者使用lastIndexOf(ch, i-1)向后搜索字符串的开头，并使用indexOf(ch, i+1)向前搜索。
p.indexOf(c, i+1)是最明显的选择。 如果在字符串的早期存在重复对，则不会很快停止。 如果对于大N和小M的性能问题，仅搜索0..i-1中的字符不会在第一次重复之后触摸持有输入字符的内存。 在不匹配的情况下，你只是在开始时做另一种算法结束时发生的事情。
ASCII文本输入可能会非常普遍，并且只有大约100个不同的ASCII字符，所以通常会在前100个字符中重复某处。 但是，前几个字符可能不是其中的一个。
一个更好的快速入门可能会选择一个可调参数，比如256或者其他东西（比CPU缓存小得多，但足够大到可以重复），然后在开始查看整个数组之前搜索到该点。
final int fastlen = 256;
int i=0;
while (++i < fastlen) {
char c = p.charAt(i);
if (p.lastIndexOf(c, fastlen) != i) return true;
// maybe lastIndexOf(c, i + fastlen)? We're going to repeat work anyway, so what's a little more?
}
// i == fastlen if we haven't returned yet
for ( ; i < N ; i++ ){
char c = p.charAt(i);
if (p.lastIndexOf(c, fastlen) != -1 ||
p.indexOf(c, i + 1) != -1 )
return true;
}
你可能会变得更加复杂，并继续工作，但是我们不要在那里优化，因为整个算法从根本上来说比需要的慢。
一个更好的算法
我们实际上可以使用O（M）临时存储和O（M）时间来完成它
for (final char c : myarray) { // loop over chars
// add c to a HashSet<char>. If it was already present, return true
}
return false;
通过对ASCII范围使用简单的数组，以及仅对c > 127使用HashMap，您可以加快速度。 在关于寻找最常见角色的问题上查看我的回答。 这将与Unicode码点一起工作。 我没有看到String.indexOf(int codepoint) ，所以基于搜索的方法可能不得不使用indexOf(String str) ，这可能会更慢。
位图也是实现检测重复的Set的选项。 2 ^ 16位只有2 ^ 13个字节，因此您可以在8k位图中测试和设置位，直到找到已设置的位。 （尽管如此，这种方法对代码点并不好。）
替代方法：从字符串中获取char数组。 把它分类。 然后循环查找buf[i] == buf[i-1] 。 不过，这是O（N log n），并且比使用hashset要慢得多。 （Hashset方法就像做一个RadixSort或BucketSort并在运行中检测重复项）。
尽管如此，utf16多字符代码点仍然存在问题。 IDK如何在保存它们的同时有效地对char[]数组进行排序。
为了做复杂性分析，你必须非常清楚你的机器是如何工作的。 机器如何运行你的代码？ 机器的功能是什么？
运行该代码的机器至少有两种非常类似的方式，每种方式都会导致您的问题得到明确的答案。
假设每个新的变量声明都会分配一个唯一的内存位，并且一旦分配了内存就不能重用。 这可能就像一个磁带存储器，或者像您在纸上写下墨水中的步骤一样。 如果你这样做，空间复杂度的确会与循环迭代次数成正比，因为你在循环体内分配了内存。
相反，假设新变量声明使用分配的第一个可用内存位，并且释放该内存，并在变量超出范围时自由重新分配内存。 在这种情况下，在函数结束时，除了恒定数量的变量之外，所有变量都已超出范围，因此空间复杂度是恒定的。
Java有自动垃圾收集功能，所以我们可以合理地说，即使是堆分配内存（栈分配内存，就像基元一样，绝对以第二种方式工作），我们仍然处于第二种情况。 实际上，垃圾收集可能不会在所有情况下立即发生，因此我们可能处于两种情况之间的某处。 但在快乐的情况下，我们可以放心地说，在Java中，这是O（1）。
在C ++中，故事会有所不同。 在那里，我们需要new并delete （或者相当于）我们的堆分配内存才能进入第二种场景; 否则，我们会在第一！
正如你所看到的，很大程度上取决于代码的真正意义，它只能根据它所执行的系统完全理解。
我抛开这个算法的实现非常差的事实。
你说：
迭代次数等于输入大小，并且在每次迭代中，我们都创建一个StringBuilder对象...
到现在为止还挺好。
...因此我们创建了与输入大小成正比的StringBuilder对象。
是的，这也是事实。 但。 您没有将迭代过程中创建的对象保留在另一个迭代中。 他们逐渐消失。
事实上，编译器可能检测到的对象的范围仅限于循环体，并优化了内存使用情况，因此它总是与使用的地方相同（可能是您的代码中的c这样的小对象的注册表）。
总之，如果编译器运行良好，你的算法是O（1）。
如果你在每次迭代时都把c或str放在列表中，情况会不一样。