java - 如何分析以下代码的增长？

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;

}

标签： javaalgorithmcomplexity-theoryanalysis

Answer 1

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