c++ - 将字符串插入到 C++ STL 集的时间复杂度

Question

c++ STL的插入字符串设置容器的时间复杂度是多少？根据我的说法，它应该是 O(xlogn)，其中 x 是要插入的字符串的长度，n 是集合的大小。此外，要设置的字符串复制应与字符串长度成线性关系。但是我的这段代码是即时运行的。

#include<bits/stdc++.h>
using namespace std;
int main(){

    set<string> c;
    string s(100000,'a');
    for(int i=0;i<100000;i++){
        c.insert(s);
    }

}   

我哪里错了，复杂度不应该是 10^10 的数量级吗？

Answer 1

您应该以某种方式使用 set 来降低循环被优化掉的风险，例如通过添加 return c.size(); 。

此外，您选择的迭代次数可能太低。向循环计数器添加一个数字，您将看到明显的运行时间。

现代 CPU 可以轻松处理 >2*10⁹ ops/s。假设您的编译器使用 memcmp，这可能是手动矢量化的，具有像您这样的小型工作集，您完全从缓存中工作并且每次比较可以达到高达 512 字节的吞吐量(使用 AVX2 ).假设每次迭代 10 个周期的中等速率，我们仍然可以比较 >10¹⁰ 字节/秒。因此，您的程序应该在 <1 秒内在中等硬件上运行。

试试这个更新后的代码:

#include <string>
#include <set>
using namespace std;
int main(){

    set<string> c;
    string s(100000,'a');
    for(int i=0;i<1000000;i++) { // Add a digit here
        c.insert(s);
    }
    return c.size(); // use something from the set
}

在 (-O3) 上进行优化后，这需要约 5 秒才能在我的系统上运行。

换句话说，是的，插入二叉树的复杂度为 O(log n)，但比较字符串的复杂度为 O(n)。这些 n 不相同，在 map 的情况下，它表示 map 大小，在 string 的情况下 - 字符串的长度。

在您的特定情况下， map 只有一个元素，因此插入是 O(1)。纯粹从字符串比较中得到线性复杂度 O(n)，其中 n 是 string_length * number_of_iterations。