排序算法中平均時(shí)間復(fù)雜度

作業(yè)排序 (Job sequencing)

Job sequencing is the set of jobs, associated with the job i where deadline di >= 0 and profit pi > 0. For any job i the profit is earned if and only if the job is completed by its deadline. To complete a job, one has to process the job on a machine for one unit of time. Only one machine is available for processing the jobs.

作業(yè)排序是與作業(yè)i相關(guān)聯(lián)的一組作業(yè)，其中期限di> = 0且利潤pi> 0 。 對(duì)于任何工作， 我當(dāng)且僅當(dāng)作業(yè)被其限期完成利潤賺。 為了完成一項(xiàng)工作，必須在一臺(tái)機(jī)器上在一個(gè)單位時(shí)間內(nèi)處理該工作。 僅一臺(tái)機(jī)器可用于處理作業(yè)。

Steps for performing job sequencing with deadline using greedy approach is as follows:

使用貪婪方法在截止日期之前執(zhí)行作業(yè)排序的步驟如下：

Sort all the jobs based on the profit in an increasing order.

根據(jù)利潤按升序?qū)λ凶鳂I(yè)進(jìn)行排序。

Let α be the maximum deadline that will define the size of array.

令α為將定義數(shù)組大小的最大截止日期。

Create a solution array S with d slots.

創(chuàng)建具有d個(gè)插槽的解決方案數(shù)組S。

Initialize the content of array S with zero.

用零初始化數(shù)組S的內(nèi)容。

Check for all jobs.

檢查所有作業(yè)。

If scheduling is possible a lot i^th slot of array s to job i.

如果調(diào)度是可能很多我陣列的^個(gè)時(shí)隙s到工作我 。

Otherwise look for location (i-1), (i-2)...1.

否則尋找位置(i-1)，(i-2)... 1 。

Schedule the job if possible else reject.

Return array S as the answer.

返回?cái)?shù)組S作為答案。

End.

結(jié)束。

作業(yè)排序算法 (Algorithm for job sequencing)

Input: A is the array of jobs with deadline and profit S array will be the output.

輸入： A是具有截止日期的職位數(shù)組，而利潤S數(shù)組將是輸出。

1. Begin2. Sort all the jobs based on profit Pi so3. P1 > P2 > P3 …………………………….>=Pn4. d = maximum deadline of job in A5. Create array S[1,…………………,d]6. For i=1 to n do7. Find the largest job x8. For j=i to 19. If ((S[j] = 0) and (x deadline<= d))10. Then 11. S[x] = i;12. Break;13. End if14. End for15. End for16. End

時(shí)間復(fù)雜度 (Time complexity)

Job sequencing problems has the time complexity of O(n2).

作業(yè)排序問題的時(shí)間復(fù)雜度為O(n2)。

Example:

例：

Given a set of 9 jobs where each job has a deadline and profit associated to it .Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit if and only if the job is completed by its deadline. The task is to find the maximum profit and the number of jobs done.

給定一組9個(gè)工作，每個(gè)工作都有一個(gè)截止日期和與之相關(guān)的利潤。每個(gè)工作需要1個(gè)時(shí)間單位才能完成，并且一次只能安排一個(gè)工作。 當(dāng)且僅當(dāng)工作在截止日期之前完成時(shí)，我們才能賺取利潤。 任務(wù)是找到最大的利潤和完成的工作數(shù)量。

Jobs Profit DeadlineJ1 85 5J2 25 4J3 16 3J4 40 3J5 55 4J6 19 5J7 92 2J8 80 3J9 15 7 .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}} .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}}

Step 1:

第1步：

Step 2:

第2步：

Step 3:

第三步：

Step 4:

第4步：

Step 5:

步驟5：

Step 6:

步驟6：

So, the maximum profit = 40 + 92 + 80 + 55 + 85 + 15 = 367

因此，最大利潤= 40 + 92 + 80 + 55 + 85 + 15 = 367

翻譯自: https://www.includehelp.com/operating-systems/job-sequencing.aspx

排序算法中平均時(shí)間復(fù)雜度

總結(jié)

以上是生活随笔為你收集整理的排序算法中平均时间复杂度_操作系统中的作业排序（算法，时间复杂度和示例）...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。