如何分析下面代码的增长？

Question

我已经知道最坏情况的复杂度是 N，最好的情况是 Mlog(M)，但我只是不知道如何。任何人都可以向我解释为什么会这样，以及不同的输入会导致每种情况吗？

public static Iterable<Integer> topM(int[] a, int M){
int N = a.length;
MinPQ<Integer> pq = new MinPQ<Integer>(M+1);
for(int i = 0; i < N; i++){
    if(pq.size() < M)
        pq.insert(a[i]);
    if(pq.min() <= a[i]){
        pq.insert(a[i]);
        pq.delMin();
    }
}
return pq;

}

Answer 1

复杂度为O(Nlog(M))。最坏的情况是当数组按升序排序时，在这种情况下每个元素都被插入到队列中。 最好的情况是数组按降序排序，在这种情况下只插入前 M 个元素。最好情况下的复杂度是 O(N+Mlog(M))。 p.s。第一条评论是正确的，第二条 if 应该是 else if.