固定大小堆上的操作的複雜性

我正在爲即將到來的考試唸書，並遇到了一個問題，我必須從傳入的無限數據流中構建和維護最高整數的前10位。我認爲我可以使用固定大小的10分鐘，並且當我收到一個新號碼時，我可以檢查最小值是否低於新來的號碼，如果是這樣，我必須更新堆通過順序提取根直到我得到一個更高的值，然後插入新的數字，以及先前彈出的根（減去第一個，以保留10的固定大小）。現在我有了這個堆，我可以通過彈出並打印堆中的每個節點輕鬆獲得前10名。固定大小堆上的操作的複雜性

我用Java編寫了一個方法，可以用PriorityQueue完成我所說的。

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

根據我的測試，此代碼完成工作並按預期工作。現在，我的問題出現了。這兩項行動的複雜性是什麼？我們有一個PriorityQueue，所以insert和extract-min操作是對數的。但在這種情況下，堆的大小「n」至多爲10.這是否意味着複雜度是O（log 10），這基本上是O（1）次的常數？

來源

2016-03-28 JaimeAL

是;常數的對數也是恆定的。

通常，通過將這些算法的運行時間描述爲多個變量的函數來分析這些算法。例如，我們可以說您的算法在O（n log k）時間和O（k）空間中提取出n數字中的頂部k。

但是，如果k的值已知，那麼我們不妨使用該事實來簡化我們的分析。

來源

2016-03-28 21:28:49 meriton

感謝您的回答。是的，我認爲複雜性取決於我們想要顯示在頂部K中的元素的數量，但由於在這種情況下我有一個固定大小的列表，我可以說它在不變的時間運行。 – JaimeAL

固定大小堆上的操作的複雜性

回答

相關問題