使用集合对log（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::sortlike 并没有什么不同

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;
}

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