ジョブがプリエンプティブでない場合の最短ジョブの最初のアルゴリズムの複雑さ

Question

最短ジョブの最初のアルゴリズムは、最小ヒープデータ構造によって実装されます。 次に、SJFアルゴリズムの複雑さはどのくらいですか？

私はどこかでn * 2 * log nでn log nに等しいと読んでいます。方法を説明してください。 （ご質問が簡単すぎる場合は申し訳ありません。新規です。）

ありがとうございます。

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)です。