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

Question

考虑一下这段代码:

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

在每个串联上创建一个新的字符串副本,以便整体复杂化O(n^2).幸运的是,在Java中,我们可以使用a来解决这个问题,每个附加StringBuffer都有O(1)复杂性,然后整体复杂性就是这样O(n).

虽然在C++中,std::string::append()有复杂性O(n),而且我不清楚它的复杂性stringstream.

在C++中,是否存在StringBuffer具有相同复杂性的方法？

Answer 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事先需要大小,则以线性时间运行.问题是,循环向量以获取大小是否比让字符串自动调整大小要慢.那,我不能告诉你.时间吧.:)

如果你不想std::string出于某种原因使用它自己(你应该考虑它;它是一个非常值得尊重的类),C++也有字符串流.

#include <sstream>
...

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

它可能没有比使用更有效std::string,但在其他情况下它更灵活一点 - 你可以用它来串行化任何原始类型,以及指定operator <<(ostream&, its_type&)覆盖的任何类型.

Answer 2

这与您的问题有些相关,但仍然相关.(而且评论太大了!)

在每个串联上创建字符串的新副本,以使总体复杂度为O(n ^ 2).

在Java中,复杂性s1.concat(s2)或s1 + s2是O(M1 + M2)其中M1和M2是各自的字符串的长度.将其转化为一系列连接的复杂性通常是困难的.但是,如果你假设N长度为字符串的连接M,那么复杂性确实O(M * N ^ 2)与你在问题中所说的相匹配.

幸运的是,在Java中,我们可以使用a来解决这个问题,每个附加StringBuffer都有O(1)复杂性,然后整体复杂性就是这样O(n).

在这种StringBuilder情况下,对大小字符串的调用的分摊复杂性是.这里的关键词是摊销.将字符追加到a时,实现可能需要扩展其内部数组.但扩展策略是将阵列的大小加倍.如果你进行数学计算,你会发现平均每个字符在整个调用序列中都会被复制一次.所以整个序列仍然可以作为...而且,它发生的是总字符串长度.Nsb.append(s)MO(M*N)StringBuilderappendO(M*N)M*N

所以你的最终结果是正确的,但你对单个调用的复杂性的陈述append是不正确的.(我明白你的意思,但你说它的方式是不正确的.)

最后,我要注意在Java中你应该使用StringBuilder而不是StringBuffer除非你需要缓冲区是线程安全的.