The algorithm is sorting the job in

The algorithm is sorting the job in decreasing order of their PC times (fi),
and schedule them in this order. Sorting n numbers costs O(n log n) running
time, which is the time complexity of this algorithm.
To simplify the proof of the correctness of this algorithm, we rename the
jobs so that
f1  f2  :::  fn (1)
We say that a schedule has an inversion if a job i is scheduled before another
job j, but fi < fj .
Claim 1 In a schedule without inversions, the order of the jobs with the
same PC time does not affect the completion time.
Proof Since there is no inversion in the schedule, jobs with the same PC
time must stay together as consecutive jobs. Among the jobs with PC time
f, the last one is the last to finish, and its finishing time is not affected by
the order of the jobs.
Claim 2 In a schedule with an inversion, there must be two adjacent jobs i
and j such that fi < fj .
This claim has been proved during the class.
Starting from an optimal schedule, if there is any inversion in it, from
Claim 2 we know that there must be two adjacent jobs i and j such that
fi < fj . We now prove that swapping i and j does not make the schedule
worse.
Figure 1 roughly pictures the swapping effect. We denote the finishing
time of job r as dr before swapping and ¯ dr after swapping, then the completion
time before swapping is C = maxr dr and is ¯ C = maxr ¯ dr after swapping.
We can see that the finishing times are not changed by the swapping for all
the jobs except i and j, and we have
¯ dj

ผลลัพธ์ (ไทย) 1:

อัลกอริทึมจะเรียงลำดับงานลำดับของพีซีที่ลดลงเวลา (ไร้สาย),และกำหนดตารางเวลาในใบสั่งนี้ ต้นทุนหมายเลข n O (ล็อก n n) ใช้การเรียงลำดับเวลา ซึ่งเป็นเวลาที่มีความซับซ้อนของอัลกอริทึมนี้การทำหลักฐานของความถูกต้องของอัลกอริทึมนี้ เราเปลี่ยนงานเพื่อให้f1 f2::: fn (1)เราบอกว่า กำหนดการมีการกลับถ้างานฉันกำหนดการก่อนอื่นงานเจ แต่เน็ต < fjร้อง 1 ในกำหนดการโดย inversions สั่งงานด้วยการกัน PC มีผลต่อเวลาเสร็จสมบูรณ์หลักฐานมีเป็นไฟล์ในกำหนดการ งานที่ มีคอมพิวเตอร์เครื่องเดียวกันเวลาต้องอยู่ร่วมกันเป็นงานต่อเนื่อง ระหว่างงานกับ PC เวลาf สุดท้ายเป็นราคาสุดท้ายที่เสร็จสิ้น และเวลาสิ้นสุดไม่ได้รับผลกระทบจากใบสั่งงานเรียกร้อง 2 ในตารางด้วยการกลับ ต้องมีงานสองติดกับผมและเจดังกล่าวไว้ที่ < fjข้อเรียกร้องนี้ได้รับการพิสูจน์ในระหว่างเรียนเริ่มต้นจากการจัดกำหนดการสูงสุด หากมีใด ๆ กลับไป จากเรียกร้อง 2 เรารู้ว่า ต้องมีงานสองติดผมและเจที่เน็ต < fj เราตอนนี้พิสูจน์ว่า เปลี่ยนฉันและเจไม่ทำให้กำหนดการแย่ลงรูปที่ 1 ภาพผล swapping หยาบ ๆ เราแสดงการเสร็จสิ้นเวลาของงาน r dr ก่อนเปลี่ยนและดร.¯หลังเปลี่ยน แล้วเสร็จก่อนเปลี่ยนเป็น C = maxr dr และเป็น¯ C = maxr ¯ dr หลังจากที่แลกเปลี่ยนเราจะเห็นว่า เวลาจบจะไม่เปลี่ยน โดยเปลี่ยนทั้งหมดงานยกเว้นฉันและเจ และเรามี¯ดีเจ