固定サイズのヒープ上での操作の複雑さ

Question

私は次回の試験を勉強しています。無限に流れてくる無限のストリームから、最高の整数の上位10個を構築して維持しなければならないという問題に直面しました。私は固定サイズのミニヒープを使用することができたと思っていました。新しい番号を受け取ったときに、最小値が新しい着信番号よりも小さいかどうかを確認するだけでした。もしそうなら、ヒープを更新する必要があります新しい数値を、以前にポップされた根と一緒に挿入して（固定サイズの10を保持するために最初のものを引いたもの）、挿入します。今、私はこのヒープを持っているので、ヒープ内のすべてのノードをポップして印刷することで簡単にトップ10を得ることができます。

私はPriorityQueueを使って、私が言っていることを達成するJavaでメソッドをコード化しました。

public void addNumber(int number){ 
    if(pq.size() < 10){ 
     pq.offer(number); 
    } 
    else if(pq.peek() < number){ 
     List<Integer> topNumbers = new LinkedList<Integer>(); 
     while(!pq.isEmpty() && pq.peek() < number){ 
      topNumbers.add(pq.poll()); 
     } 
     pq.offer(number); 
     for(int i = 1; i < topNumbers.size(); i++){ 
      pq.offer(topNumbers.get(i)); 
     } 
    } 
} 

public void printTop10(){ 
    List<Integer> topNumbers = new LinkedList<Integer>(); 
    while(!pq.isEmpty()){ 
     topNumbers.add(pq.poll()); 
    } 

    for(int i = 0; i < topNumbers.size(); i++){ 
     Node thisOne = topNumbers.get(topNumbers.size() - 1 - i); 
     System.out.println(thisOne); 
     pq.offer(thisOne); 
    } 
} 

私のテストによれば、このコードは仕事をして、期待どおりに動作します。今、私の質問が来る。これら2つの操作の複雑さは何ですか？ PriorityQueueがあるので、insertとextract-min演算は対数です。しかし、この場合、ヒープのサイズ "n"は最大で10です。これは、複雑さがO（log 10）であり、基本的には一定のO（1）時間であることを意味しますか？

Answer 1

はい。定数の対数も一定です。

多くの場合、そのようなアルゴリズムは、ランタイムをいくつかの変数の関数として記述することによって解析されます。例えば、あなたのアルゴリズムが、O（n log k）時間とO（k）空間のkのうちn番のうちの上位を抽出すると言うかもしれません。

ただし、値がkであることがわかっている場合は、そのことを使用して分析を簡略化することもできます。