作業不搶佔時最短作業​​優先算法的時間複雜度

Question

最短作業優先算法通過最小堆數據結構實現。 那麼SJF算法的時間複雜度是多少？

我在什麼地方讀它，這是N * 2 *日誌n的等於n日誌ñ。請解釋如何。 （很抱歉，如果這個問題太easy.I是新來的吧。）事先

感謝。

Answer 1

Insert和Extract-Min操作的運行時間都是O(log n)。有n任務，每個任務必須插入到堆中，然後從堆中提取，導致運行時間爲O(n log n)。

Insert的運行時間爲O(log n)的原因是插入時我們先將新任務添加到堆的最終位置。這並不一定保持heap property，因爲新任務的優先級可能比其父級的優先級更高（具有更小的密鑰）。這就是爲什麼Insert操作涉及Heapify-Up procedure，其目的是恢復堆順序。 Heapify-Up程序的運行時間爲O(log n)。

原因Extract-Min有O(log n)運行時間是在Extract-Min操作，我們先刪除堆的根（第一個任務），然後最後一個任務移動到第一位置（即與更換根任務位於最後的位置）。由於這可能違反堆屬性，因此Extract-Min涉及執行Heapify-Down procedure。 Heapify-Down程序的運行時間也爲O(log n)。