Space 复杂性示例
Space Complexity Example
所以我想知道何时在 for 循环内创建对象（或原语），这对 space 复杂性有何影响？
例如，这是一个代码示例：
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;
}
所以我正在尝试分析此算法的 space 复杂性。看起来是 O(n)。这是我的推理：迭代次数等于输入大小，并且在每次迭代中我们创建一个 StringBuilder 对象，因此我们创建的 StringBuilder 对象与输入大小成比例。同样的推理可以应用于我们在每次迭代中创建 String 对象和 char 的事实。这个推理正确吗？
我问的原因是因为我遇到了一种算法，每次迭代后都会进行以下分配：
int val = str.charAt(i);
然而这个算法的复杂度为 O(1) space。那么我的理解一定是不正确的吗？在这种情况下，checkUnique 算法的复杂度也为 space O(1)。
为了进行复杂性分析，你必须非常清楚你的机器是如何工作的。机器如何 运行 你的代码？机器的功能是什么？
机器 运行 运行该代码至少有两种非常相似的方式，每一种方式都会对您的问题给出不同的答案。
假设每个新的变量声明都会导致分配一个唯一的内存位，并且一旦分配，该内存就不能再使用。这可能就像磁带存储器，或者就像您用墨水在纸上写下步骤。如果你这样做，space 复杂度确实与循环迭代次数成正比，因为你在循环体中分配了内存。
相反，假设新变量声明使用分配的第一个可用内存位，并且一旦变量超出范围，该内存就会被释放并可以自由重新分配。在这种情况下，到函数结束时，除恒定数量的变量外，所有变量都超出了范围，因此 space 复杂度是恒定的。
Java 有自动垃圾收集，所以我们可以合理地说我们处于第二种情况甚至 w.r.t。堆分配的内存（堆栈分配的内存，像基元一样，绝对以第二种方式工作）。实际上，垃圾收集可能不会在所有情况下都立即发生，因此我们可能介于这两种情况之间。但在快乐的情况下，我们可以安全地说，在 Java 中，这是 O(1).
在 C++ 中，情况会有所不同。在那里，我们需要 new 和 delete（或等效）我们的堆分配内存处于第二种情况；否则，我们会是第一！
如您所见，很大程度上取决于代码的真正含义，只有在其执行的系统方面才能完全理解。
抛开这个算法的实现很差
你说：
The number of iterations is equivalent to the input size, and in each iteration we are creating a StringBuilder object...
到目前为止一切顺利。
... hence we are creating StringBuilder objects proportional to the input size.
是的，这也是事实。但。您没有将那些创建的对象从一个迭代保存到另一个。它们逐渐消失。
事实上，编译器可能会检测到范围仅限于循环主体的对象并优化内存使用，因此它始终使用相同的位置（可以是像 c 这样的小对象的寄存器在你的代码中）。
总之，如果编译器运行良好，你的算法是 O(1)。
如果您在每次迭代中将 c 或 str 放入列表中，情况就会有所不同。
我将回顾该算法中的错误设计决策，并提出更好的建议。
现有的答案很好地回答了复杂度-class的问题，但是不要指出你问题中的错误：你的space复杂度是O(N)，因为你做了一个整个输入的副本（减去一个字符）。
如果您的循环在每次迭代中都保留临时副本，space 复杂度将与时间复杂度相匹配：O(N*M)，其中 M 是包含重复项的最短前缀的长度. （或者 M = N 如果没有重复项）。
鸽巢原理确保M <= 216（一个char可以拥有的唯一值的数量）。
如果 input.length() > Character.MAX_VALUE，任何算法的优化总是 return 为真。 （或者对于代码点，input.length() > Character.MAX_CODE_POINT，即 1114111）
如果您输入的大部分是 ASCII，则 M 最多会更接近 80。实际上，大多数语言并没有使用很多不同的代码点，即使范围不是从 0 开始。我认为非字母语言可以有几千个字形。但无论如何，关键是，如果第一个字符恰好是唯一的，那么检查字符串的早期部分是否有重复是有用的，而不是做任何扫描整个潜在巨大字符串的事情。
剧透：将字符添加到集合中是迄今为止查找重复项的最佳方法。 O(M) 时间和 space，常数因子开销较低。
除了性能，请记住 Java char 是 utf16，但 some Unicode codepoints have a multi-char encoding。对于 Java 来说真的很不幸，它得到了两个世界中最糟糕的：与 ASCII 的 utf8 相比，space 使用量增加了一倍，但仍然必须处理多元素“字符”。在设计Java的时候，16bits足以容纳任何Unicode字符，所以utf16确实避免了utf8那样的多字节字符编码的困难。宽字符流行了一段时间，也许现在还在 Windows，IDK 上。 Unix / POSIX / Internet 协议在 utf8 上几乎已经对所有内容进行了标准化。
看起来the best way to iterate over codepoints是和
int cp = str.codePointAt(pos);
pos+=Character.charCount(cp);
循环 i=0..N 并执行 codePointAt(i) 可能必须在每次迭代时从字符串的开头扫描以找到代理项对。智能 JVM 可能会注意到冗余并进行优化，但我不会指望它。
原算法分析
这种遍历每个字符并检查所有其他字符的基本设计很有意义，也很容易想到。有很多多余的工作（当我们已经知道 a!=b 时检查 a==c 和 b==c），所以它将是 O(N2 )（请参阅下面的 diff 算法），但我们可以用比您的版本少得多的恒定开销来实现它。
- 遍历原始字符串的字符。没问题，在
i 位置获取字符非常便宜。
- 制作一个输入字符串的临时副本，其中包括除此字符以外的所有字符。 这是迄今为止你的算法中最大的错误。复制内存很慢，尤其是。如果输入字符串太大而无法放入缓存。
表示现代 JVM 通常可以识别循环何时在每次迭代中创建/销毁对象，而不会淹没垃圾收集器。除了复制开销之外，每次迭代都触及原始和副本的每个字节意味着您的字符串将停止适合 CPU 的缓存，达到更好设计的 N 的一半。
有很多方法可以避免每次都重新复制字符串：
复制一次到一个char[]数组，通过修改把当前char去掉。 （例如 c = tmpbuf[i]++; search tmpbuf for c、tmpbuf[i]--）。
将其复制一次到StringBuffer中，并像步骤1中那样用buf.setCharAt(int, char)修改当前位置。然后你可以像以前一样使用 StringBuffer.indexOf() 。嗯，只有 String 具有针对单个字符的 indexOf 特化，因此 .toString().indexOf() 可能更好。 StringBuilder 也一样：只有 indexOf(String)。 （不要试图使用 deleteCharAt() 和 insert()，因为它们可能是通过打乱剩余元素来实现的）。
由于数组搜索的主要库函数建议不适用于基本类型的数组（如 char），您可以手动循环并跳过 i .根据 JVM，使用 charAt 循环输入字符串手册可能同样快。
使用indexOf的多参数版本之一：String.indexOf(int ch, int fromIndex)从头搜索（期望搜索在位置i处停止），然后来自 i+1（预计未找到）。
使用String.lastIndexOf(int ch)向后搜索。期待它 return i。或者使用 lastIndexOf(ch, i-1) 向后搜索字符串的开头，并使用 indexOf(ch, i+1) 向前搜索。
- 检查整个 字符串（除了这个字符）看它是否与当前字符相同。我们实际上可以只检查字符串的 rest，因为我们已经检查了当前的所有先前字符，当它们是当前字符时。选择任何不复制字符串的解决方案，并省略从 0..i 开始检查的部分。
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)，这可能会更慢。
位图也是实现检测重复的集合的一个选项。 2^16 位只有 2^13 字节，因此您可以在 8k 位图中测试和设置位，直到找到已经设置的位。 （不过，这种方法对代码点不利。）
备选方案：从字符串中获取字符数组。把它分类。然后循环，寻找buf[i] == buf[i-1]。不过，这是 O(N log n)，并且比使用哈希集慢 很多 。 （Hashset 方法就像执行 RadixSort 或 BucketSort 并动态检测重复项）。
虽然 utf16 多字符代码点有问题。 IDK 如何在保留 char[] 数组的同时有效地对它们进行排序。
所以我想知道何时在 for 循环内创建对象（或原语），这对 space 复杂性有何影响？
例如，这是一个代码示例：
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;
}
所以我正在尝试分析此算法的 space 复杂性。看起来是 O(n)。这是我的推理：迭代次数等于输入大小，并且在每次迭代中我们创建一个 StringBuilder 对象，因此我们创建的 StringBuilder 对象与输入大小成比例。同样的推理可以应用于我们在每次迭代中创建 String 对象和 char 的事实。这个推理正确吗？
我问的原因是因为我遇到了一种算法，每次迭代后都会进行以下分配：
int val = str.charAt(i);
然而这个算法的复杂度为 O(1) space。那么我的理解一定是不正确的吗？在这种情况下，checkUnique 算法的复杂度也为 space O(1)。
为了进行复杂性分析，你必须非常清楚你的机器是如何工作的。机器如何 运行 你的代码？机器的功能是什么？
机器 运行 运行该代码至少有两种非常相似的方式，每一种方式都会对您的问题给出不同的答案。
假设每个新的变量声明都会导致分配一个唯一的内存位，并且一旦分配，该内存就不能再使用。这可能就像磁带存储器，或者就像您用墨水在纸上写下步骤。如果你这样做，space 复杂度确实与循环迭代次数成正比，因为你在循环体中分配了内存。
相反，假设新变量声明使用分配的第一个可用内存位，并且一旦变量超出范围，该内存就会被释放并可以自由重新分配。在这种情况下，到函数结束时，除恒定数量的变量外，所有变量都超出了范围，因此 space 复杂度是恒定的。
Java 有自动垃圾收集，所以我们可以合理地说我们处于第二种情况甚至 w.r.t。堆分配的内存（堆栈分配的内存，像基元一样，绝对以第二种方式工作）。实际上，垃圾收集可能不会在所有情况下都立即发生，因此我们可能介于这两种情况之间。但在快乐的情况下，我们可以安全地说，在 Java 中，这是 O(1).
在 C++ 中，情况会有所不同。在那里，我们需要 new 和 delete（或等效）我们的堆分配内存处于第二种情况；否则，我们会是第一！
如您所见，很大程度上取决于代码的真正含义，只有在其执行的系统方面才能完全理解。
抛开这个算法的实现很差
你说：
The number of iterations is equivalent to the input size, and in each iteration we are creating a StringBuilder object...
到目前为止一切顺利。
... hence we are creating StringBuilder objects proportional to the input size.
是的，这也是事实。但。您没有将那些创建的对象从一个迭代保存到另一个。它们逐渐消失。
事实上，编译器可能会检测到范围仅限于循环主体的对象并优化内存使用，因此它始终使用相同的位置（可以是像 c 这样的小对象的寄存器在你的代码中）。
总之，如果编译器运行良好，你的算法是 O(1)。
如果您在每次迭代中将 c 或 str 放入列表中，情况就会有所不同。
我将回顾该算法中的错误设计决策，并提出更好的建议。
现有的答案很好地回答了复杂度-class的问题，但是不要指出你问题中的错误：你的space复杂度是O(N)，因为你做了一个整个输入的副本（减去一个字符）。
如果您的循环在每次迭代中都保留临时副本，space 复杂度将与时间复杂度相匹配：O(N*M)，其中 M 是包含重复项的最短前缀的长度. （或者 M = N 如果没有重复项）。
鸽巢原理确保M <= 216（一个char可以拥有的唯一值的数量）。
如果 input.length() > Character.MAX_VALUE，任何算法的优化总是 return 为真。 （或者对于代码点，input.length() > Character.MAX_CODE_POINT，即 1114111）
如果您输入的大部分是 ASCII，则 M 最多会更接近 80。实际上，大多数语言并没有使用很多不同的代码点，即使范围不是从 0 开始。我认为非字母语言可以有几千个字形。但无论如何，关键是，如果第一个字符恰好是唯一的，那么检查字符串的早期部分是否有重复是有用的，而不是做任何扫描整个潜在巨大字符串的事情。
剧透：将字符添加到集合中是迄今为止查找重复项的最佳方法。 O(M) 时间和 space，常数因子开销较低。
除了性能，请记住 Java char 是 utf16，但 some Unicode codepoints have a multi-char encoding。对于 Java 来说真的很不幸，它得到了两个世界中最糟糕的：与 ASCII 的 utf8 相比，space 使用量增加了一倍，但仍然必须处理多元素“字符”。在设计Java的时候，16bits足以容纳任何Unicode字符，所以utf16确实避免了utf8那样的多字节字符编码的困难。宽字符流行了一段时间，也许现在还在 Windows，IDK 上。 Unix / POSIX / Internet 协议在 utf8 上几乎已经对所有内容进行了标准化。
看起来the best way to iterate over codepoints是和
int cp = str.codePointAt(pos);
pos+=Character.charCount(cp);
循环 i=0..N 并执行 codePointAt(i) 可能必须在每次迭代时从字符串的开头扫描以找到代理项对。智能 JVM 可能会注意到冗余并进行优化，但我不会指望它。
原算法分析
这种遍历每个字符并检查所有其他字符的基本设计很有意义，也很容易想到。有很多多余的工作（当我们已经知道 a!=b 时检查 a==c 和 b==c），所以它将是 O(N2 )（请参阅下面的 diff 算法），但我们可以用比您的版本少得多的恒定开销来实现它。
- 遍历原始字符串的字符。没问题，在
i位置获取字符非常便宜。
- 制作一个输入字符串的临时副本，其中包括除此字符以外的所有字符。 这是迄今为止你的算法中最大的错误。复制内存很慢，尤其是。如果输入字符串太大而无法放入缓存。
有很多方法可以避免每次都重新复制字符串：
复制一次到一个
char[]数组，通过修改把当前char去掉。 （例如c = tmpbuf[i]++;searchtmpbufforc、tmpbuf[i]--）。将其复制一次到StringBuffer中，并像步骤1中那样用
buf.setCharAt(int, char)修改当前位置。然后你可以像以前一样使用StringBuffer.indexOf()。嗯，只有String具有针对单个字符的 indexOf 特化，因此.toString().indexOf()可能更好。 StringBuilder 也一样：只有indexOf(String)。 （不要试图使用 deleteCharAt() 和 insert()，因为它们可能是通过打乱剩余元素来实现的）。由于数组搜索的主要库函数建议不适用于基本类型的数组（如
char），您可以手动循环并跳过i.根据 JVM，使用charAt循环输入字符串手册可能同样快。使用
indexOf的多参数版本之一：String.indexOf(int ch, int fromIndex)从头搜索（期望搜索在位置i处停止），然后来自i+1（预计未找到）。使用
String.lastIndexOf(int ch)向后搜索。期待它 returni。或者使用lastIndexOf(ch, i-1)向后搜索字符串的开头，并使用indexOf(ch, i+1)向前搜索。
- 检查整个 字符串（除了这个字符）看它是否与当前字符相同。我们实际上可以只检查字符串的 rest，因为我们已经检查了当前的所有先前字符，当它们是当前字符时。选择任何不复制字符串的解决方案，并省略从 0..i 开始检查的部分。
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 来进一步加快速度。 String.indexOf(int codepoint)，因此基于搜索的方法可能必须使用 indexOf(String str)，这可能会更慢。
位图也是实现检测重复的集合的一个选项。 2^16 位只有 2^13 字节，因此您可以在 8k 位图中测试和设置位，直到找到已经设置的位。 （不过，这种方法对代码点不利。）
备选方案：从字符串中获取字符数组。把它分类。然后循环，寻找buf[i] == buf[i-1]。不过，这是 O(N log n)，并且比使用哈希集慢 很多 。 （Hashset 方法就像执行 RadixSort 或 BucketSort 并动态检测重复项）。
虽然 utf16 多字符代码点有问题。 IDK 如何在保留 char[] 数组的同时有效地对它们进行排序。