首页 文章

空间复杂性示例

提问于
浏览 次
3

所以我想知道在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） .

java algorithm big-o space-complexity

3 回答

  • 3

    我将在这个算法中回顾糟糕的设计决策，并建议一个更好的 .

    现有的答案很好地回答了复杂性问题，但是没有指出你的问题中的错误：你的空间复杂度是O（N），因为你复制了整个输入（减去一个字符） .

    如果循环保持每次迭代的临时副本，则空间复杂度将匹配时间复杂度：O（N * M），其中M是包含重复的最短前缀的长度 . （如果没有重复，则为 M = N ） .

    鸽笼原理确保M <= 216（ char 可以具有的唯一值的数量） .

    对于任何算法的优化是，如果 input.length() > Character.MAX_VALUE ，则始终返回true . （或者对于代码点， input.length() > Character.MAX_CODE_POINT ，这是1114111）

    如果您的大部分输入都是ASCII，则M最多会更像80 . 实际上，大多数语言都没有使用很多不同的代码点，即使范围不是从0开始 . 我认为非字母语言可以有几千个字形 . 但无论如何，重点是，在字符串的早期部分检查重复是有用的，而不是在第一个字符碰巧是唯一的时候做任何扫描整个潜在巨大字符串的事情 .

    Spoiler：在Set中添加字符是迄今为止找到重复的最佳方法 . O（M）时间和空间，具有低常数因子开销 .

    除了性能之外，请记住Java char s是utf16，但是some Unicode codepoints have a multi-char encoding . 对于Java而言，它实际上是两个世界中最糟糕的事情是非常不幸的：与用于ASCII的utf8相比，空间使用量增加了一倍，但仍然需要处理多元素"characters" . 设计Java时，16位足以容纳任何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）（参见下面的差异算法），但是我们可以用比你的更少的常量开销来实现它 . 版 .

    • 循环原始字符串的字符 . 没有什么不对，在位置 i 获得炭是非常便宜的 .
    • 制作包含除此之外的所有字符的输入字符串的临时副本 . This is by far the biggest sin in your algorithm . 复制内存很慢，尤其是如果输入字符串太大而无法放入缓存中 . Louis Wasserman表示现代JVM通常可以识别循环何时每次迭代创建/销毁一个对象，而不是泛滥垃圾收集器 . 除了复制开销之外，每次迭代触摸原始和副本的每个字节意味着你的字符串将在更好的设计的N的一半处停止适应CPU的缓存 .

    有很多方法可以避免每次重复复制字符串：

    • 将其复制一次到 char[] 数组，并通过修改它来取消当前的char . （例如 c = tmpbuf[i]++; search tmpbuf for c， tmpbuf[i]-- ） .

    • 将其复制一次StringBuffer，并使用buf.setCharAt(int, char)修改当前位置，如步骤1中所示 . 然后你可以像以前一样使用 StringBuffer.indexOf() . Hrm，只有 String 对单个字符有indexOf的特化，所以 .toString().indexOf() 可能更好 . StringBuilder也是如此：只有 indexOf(String) . （唐't be tempted to use deleteCharAt() and insert(), because they'可能通过改组其余元素来实现） .

    • 由于数组搜索的主库函数建议不适用于基本类型的数组（如 char ），您可以手动循环并跳过 i . 根据JVM，使用 charAt 循环输入字符串手册可能同样快 .

    • 使用多个arg版本的 indexOf 之一： String.indexOf(int ch, int fromIndex) 从头开始搜索（期望搜索停在位置 i ），然后从 i+1 （期待未找到） .

    • 使用 String.lastIndexOf(int ch) 向后搜索 . 期待它返回 i . 或者使用 lastIndexOf(ch, i-1) 向后搜索字符串的开头，然后使用 indexOf(ch, i+1) 搜索向前搜索 .

    • 检查整个字符串（此char除外）以查看它是否与当前char相同 . 我们实际上可以只检查字符串的其余部分，因为我们已经检查了当前的当前所有字符 . 选择任何不复制字符串的解决方案，并省略从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;
   }

    你可能会变得更复杂，并继续在块中工作，但让我们停止优化，因为整个算法基本上比它需要的慢 .

    一个更好的算法

    We can actually do it using O(M) temporary storage and O(M) time

    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，可以进一步提高速度 . See my answer on a question about finding the most frequent character . 这将适用于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[] 数组进行排序 .

    回复于
  • 1

    为了进行复杂性分析，您必须非常清楚机器的工作原理 . 机器如何运行你的代码？机器的功能是什么？

    运行该代码的机器至少有两种非常相似的方式可以工作，每种方法都可以为您的问题提供独特的答案 .

    假设每个新的变量声明都会导致分配一个唯一的内存位，并且一旦分配，该内存就无法重用 . 这可能就像磁带存储器，或者就像你在纸上写下墨水的步骤一样 . 如果你这样做，空间复杂度确实与循环迭代次数成正比，因为你在循环体中分配了内存 .

    相反，假设新的变量声明使用分配的第一个可用内存位，并且一旦变量超出范围，该内存就会被释放并可以自由重新分配 . 在这种情况下，在函数结束时，除了常量数量的变量之外的所有变量都超出了范围，因此空间复杂性是恒定的 .

    Java有自动垃圾收集，所以我们可以合理地说，即使是w.r.t，我们也处于第二种情况 . 堆分配的内存（堆栈分配的内存，就像基元一样，肯定是以第二种方式工作） . 实际上，垃圾收集可能不会在所有情况下立即发生，因此我们可能介于两种情况之间 . 但在幸福的情况下，我们可以安全地说，在Java中，这是O（1） .

    在C中，故事会有所不同 . 在那里，我们需要 new 和 delete （或等效的）我们的堆分配内存在第二个场景中;否则，我们会在第一个！

    正如您所看到的，很大程度上取决于代码的真正含义，只能根据代码执行的系统来完全理解 .

    回复于
  • 6

    我撇开这个算法的实现非常差的事实 .

    你说：

    迭代次数等于输入大小，在每次迭代中我们创建一个StringBuilder对象......

    到现在为止还挺好 .

    ...因此我们创建与输入大小成比例的StringBuilder对象 .

    是的，这也是事实 . 但 . 您没有将迭代中创建的对象保留到另一个 . 他们逐渐消失 .

    实际上，编译器可能检测到对象的范围仅限于循环体并优化内存使用情况，因此它始终与使用的位置相同（可能是代码中的小对象的寄存器，如 c ） .

    总之，如果编译器运行良好，则算法为O（1） .

    如果你有，在每次迭代时，将 c 或 str 放在一个列表中就会有所不同 .

    回复于

相关问题