C++和 Java 中的字符串串联复杂性

string time-complexity java c++

2022-09-01 06:47:55

请考虑以下代码段：

public String joinWords(String[] words) {
    String sentence = "";
    for(String w : words) {
        sentence = sentence + w;
    }
    return sentence;
}

在每个串联上，都会创建字符串的新副本，因此总体复杂度为。幸运的是，在Java中，我们可以用一个来解决这个问题，它对于每个附加都有复杂性，那么整体复杂性将是。O(n^2)StringBufferO(1)O(n)

虽然在C++，具有的复杂性，但我不清楚的复杂性。std::string::append()O(n)stringstream

在C++中，是否有类似方法的方法具有相同的复杂性？StringBuffer

答案 1

C++字符串是可变的，并且几乎与StringBuffer一样动态大小。与Java中的等效代码不同，此代码不会每次都创建新字符串;它只是附加到当前一个。

std::string joinWords(std::vector<std::string> const &words) {
    std::string result;
    for (auto &word : words) {
        result += word;
    }
    return result;
}

如果您事先需要的大小，这将以线性时间运行。问题是循环访问矢量以获取大小是否比让字符串自动调整大小慢。那个，我不能告诉你。定时。:)reserve

如果你出于某种原因不想使用它本身（你应该考虑它;它是一个非常值得尊敬的类），C++也有字符串流。std::string

#include <sstream>
...

std::string joinWords(std::vector<std::string> const &words) {
    std::ostringstream oss;
    for (auto &word : words) {
        oss << word;
    }
    return oss.str();
}

它可能不比使用更有效，但在其他情况下它更灵活 - 您可以使用它字符串化几乎任何基元类型，以及指定覆盖的任何类型。std::stringoperator <<(ostream&, its_type&)

答案 2

这有点与你的问题有关，但仍然相关。（而且太大了，无法发表评论！

在每次串联时，都会创建字符串的新副本，因此总体复杂度为 O（n^2）。

在 Java 中，or 的复杂性是 where 和是相应的字符串长度。一般来说，将其转化为串联序列的复杂性是很困难的。但是，如果您假设长度字符串的串联，那么复杂性确实与您在问题中所说的相匹配。s1.concat(s2)s1 + s2O(M1 + M2)M1M2NMO(M * N * N)

幸运的是，在Java中，我们可以用一个来解决这个问题，它对于每个附加都有复杂性，那么整体复杂性将是。StringBufferO(1)O(n)

在这种情况下，对大小字符串的调用的摊销复杂度为。这里的关键词是摊销的。当您将字符追加到时，实现可能需要扩展其内部数组。但扩展策略是将阵列的大小增加一倍。如果进行数学运算，您将看到缓冲区中的每个字符将在整个调用序列中额外复制一次。因此，整个序列仍然像...并且，碰巧的是总字符串长度。StringBuilderNsb.append(s)M O(M*N)StringBuilderappendO(M*N)M*N

因此，您的最终结果是正确的，但是您关于单个调用的复杂性的陈述是不正确的。（我明白你的意思，但你说的方式在表面上是不正确的。append

最后，我要指出的是，在Java中，你应该使用而不是除非你需要缓冲区是线程安全的。StringBuilderStringBuffer