使用set进行日志（N）排序？

Question

是整个代码O（log（N））的时间复杂度吗？ （摊销）。如果，我们每次都可以使用这种方法进行排序吗？最初需要对一些数字进行排序。

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 

    int numbers[]={60 , 2 , 3 , 35, 67, 111, 5, 7};
    set<int> s (numbers,numbers+8);
    for(auto x : s)
    {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

Answer 1

根据[set.cons]\4，std::set的迭代器构造函数有一个

复杂性：N中的线性如果范围[first, last)已经使用comp和N log N排序，其中N是last - first。

所以在你的情况下你仍然有N log N的复杂性，因为numbers没有排序，它与使用std::sort没有任何不同

int main() 
{ 

    int numbers[]={60 , 2 , 3 , 35, 67, 111, 5, 7};
    std::sort(std::begin(numbers), std::end(numbers));
    for(auto x : numbers)
    {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

除了在使用集合的情况下，您需要分配节点，以便添加所有成本。

Answer 2

是整个代码O（log（N））的时间复杂度吗？

不它不是。

set<int> s {60 , 2 , 3 , 35, 67, 111, 5, 7};

是一个快捷方式：

set<int> s;
s.insert(60);

...

s.insert(7);

每个insert的复杂性是O(log(size()))。来自https://en.cppreference.com/w/cpp/container/set/insert：

复杂 1-2）容器大小的对数，O（log（size（）））。

整个行动的复杂性是O(N * log(N))。

Answer 3

严格来说，整个代码的复杂性是不变的。没有n可以增加以观察增加的运行时间。

我猜你实际上指的是：通过构建n对std::set整数进行排序。在这种情况下，您需要考虑该构造函数的复杂性是O（n log（n））（如果输入尚未排序，请参阅例如here。比较通过std::vector对std::sort（或其他一些容器）进行排序，这也是O（n log（n）），你不能通过使用std::set获得。

Answer 4

对于每个插入操作，时间复杂度是log（n），其中n =集合中的元素no。因此，为了插入所有元素，总体时间复杂度将是nlog（n），除非您明确指定插入元素的最佳位置，那么在这种情况下它将是摊销的常量。