求一个数组中第k大的元素，两种不同的priority_queue解时间复杂度

Question

我对两个具体使用 priority_queue 的解决方案感兴趣。虽然他们都使用priority_queue，但我认为他们的时间复杂度不同。

解决方案一：

int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end()); //O(N)
        for (int i = 0; i < k - 1; i++) //O(k*log(k))
            pq.pop(); 
        return pq.top();
}

时间复杂度：O(N) + O(k*log(k))

编辑：抱歉，应该是 O(N) + O(k*log(N)) 感谢您指出！

方案二：

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> p;
    int i = 0;
    while(p.size()<k) {

        p.push(nums[i++]);
    }

    for(; i<nums.size(); i++) {

        if(p.top()<nums[i]){
            p.pop();
            p.push(nums[i]);
        }

    }

    return p.top();
}

时间复杂度：O(N*log(k))

所以在大多数情况下，第一个解决方案比第二个好得多？

Answer 1

嗯，不，第一个是 O(N)+O(k*log(N)) 因为 pop 是 O(log(N))

int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end()); //O(N)
        for (int i = 0; i < k - 1; i++) //O(k*log(N))
            pq.pop(); // this line is O(log(N))
        return pq.top();
}

大多数情况下还是比第二种好。

Answer 2

在第一种情况下，复杂度是 O(n)+klog(n) 而不是 O(n)+klog(k)，因为堆中有 n 个元素。在最坏的情况下，k 可以和 n 一样大，因此对于无限数据 O(nlog(n)) 是正确的最坏情况复杂度。

在第二种情况下，优先级队列中的项目永远不会超过 k，因此复杂度为 O(nlog(k)) 并且对于无限数据，k 可以和 n 一样大，所以它是 O (nlog(n)).

对于较小的 k，第二个代码会运行更快，但随着 k 变大，第一个代码会变得更快。我做了一些实验，结果如下：

k=1000
Code 1 time:0.123662
998906057
Code 2 time:0.03287
998906057
========
k=11000
Code 1 time:0.137448
988159929
Code 2 time:0.0872
988159929
========
k=21000
Code 1 time:0.152471
977547704
Code 2 time:0.131074
977547704
========
k=31000
Code 1 time:0.168929
966815132
Code 2 time:0.168899
966815132
========
k=41000
Code 1 time:0.185737
956136410
Code 2 time:0.205008
956136410
========
k=51000
Code 1 time:0.202973
945313516
Code 2 time:0.236578
945313516
========
k=61000
Code 1 time:0.216686
934315450
Code 2 time:0.27039
934315450
========
k=71000
Code 1 time:0.231253
923596252
Code 2 time:0.293189
923596252
========
k=81000
Code 1 time:0.246896
912964978
Code 2 time:0.321346
912964978
========
k=91000
Code 1 time:0.263312
902191629
Code 2 time:0.343613
902191629
========

我稍微修改了第二个代码，使其类似于代码 1:

int findKthLargest2(vector<int>& nums, int k) {
    double st=clock();
    priority_queue<int, vector<int>, greater<int>> p(nums.begin(), nums.begin()+k);

    int i=k;
    for(; i<nums.size(); i++) {
        if(p.top()<nums[i]){
            p.pop();
            p.push(nums[i]);
        }

    }
    cerr<<"Code 2 time:"<<(clock()-st)/CLOCKS_PER_SEC<<endl;
    return p.top();
}
int findKthLargest1(vector<int>& nums, int k) {
        double st=clock();
        priority_queue<int> pq(nums.begin(), nums.end()); //O(N)
        for (int i = 0; i < k - 1; i++) //O(k*log(k))
            pq.pop(); 

        cerr<<"Code 1 time:"<<(clock()-st)/CLOCKS_PER_SEC<<endl;
        return pq.top();
}

int main() {   

 READ("in");
 vector<int>v;
 int n;
 cin>>n;
 repl(i,n)
 {
     int x;
     scanf("%d",&x);
     v.pb(x);
 }

 for(int k=1000;k<=100000;k+=10000)
 {
     cout<<"k="<<k<<endl;
    cout<<findKthLargest1(v,k)<<endl;
    cout<<findKthLargest2(v,k)<<endl;
    puts("========");
  }
}

我使用 0 到 10^9 之间的 1000000 个随机整数作为数据集，由 C++ rand() 函数生成。

求一个数组中第k大的元素，两种不同的priority_queue解时间复杂度

Find kth largest element in an array, two different priority_queue solutions time complexity

algorithm

sorting

heap

priority-queue