With Lemma 6, ROTATED SORT can be d

With Lemma 6, ROTATED SORT can be done in P n i=1(2li1+1 l ) operations; we know that to minimize the sorting cost, l should be chosen to minimize 2ln1 l . We can always choose the perfect l but make the cost amortized, by performing normalization that takes O(n) operations whenever the array grows until l is not optimal. A perfectly sorted array can be visualized as an l-levels rotated list, regardless of l. We can maintain the optimal value of l by normalization, with the amortized constant cost. Therefore, the overall sorting cost can remain the same.

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

ด้วยการจับมือ 6 เรียงลำดับหมุนสามารถทำได้ใน P n ฉัน = 1 (2li1 + 1 l) การดำเนินงาน เรารู้ว่าเพื่อลดต้นทุนในการเรียงลำดับ l ควรเลือกเพื่อลด 2ln1 l เราจะสามารถเลือก l โก แต่ทำให้ต้นทุนที่ซึ่งตัดจำหน่าย โดยดำเนินการฟื้นฟูที่ดำเนิน O(n) เมื่อขยายอาร์เรย์จนกว่า l ไม่เหมาะสม สามารถจะ visualized แถวเรียงลำดับอย่างสมบูรณ์ที่มี l ระดับหมุนรายการ ว่า l เราสามารถรักษามูลค่าเหมาะสมของ l โดยฟื้นฟู ด้วยต้นทุนคงซึ่งตัดจำหน่าย ดังนั้น ต้นทุนรวมเรียงลำดับสามารถเหมือนเดิม

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

ด้วยบทแทรก 6 เรียงลำดับหมุนสามารถทำได้ในพรรณี P = 1 (2li1 + 1 ลิตร) การดำเนินงาน เรารู้ว่าเพื่อลดค่าใช้จ่ายในการเรียงลำดับลิตรควรจะเลือกที่จะลด 2ln1 ลิตร เราสามารถเลือกเสมอลิตรสมบูรณ์แบบ แต่ให้ค่าใช้จ่ายตัดจำหน่ายโดยการดำเนินการฟื้นฟูที่ใช้เวลา O (n) การดำเนินงานเมื่อใดก็ตามที่อาร์เรย์เติบโตจนลิตรไม่ดีที่สุด แถวเรียงที่ดีที่สุดที่สามารถมองเห็นเป็นระดับ l-หมุนรายการโดยไม่คำนึงถึงลิตร เราสามารถรักษามูลค่าที่เหมาะสมของการฟื้นฟูลิตรโดยมีค่าใช้จ่ายคงที่ตัดจำหน่าย ดังนั้นค่าใช้จ่ายในการเรียงลำดับโดยรวมยังคงเหมือนเดิม

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

กับแทรก 6 หมุนเรียงได้ P N = 1 ( 2li1 1 ลิตร ) การดำเนินงาน เรารู้ว่าการลด คัดแยก ต้นทุน ฉันควรจะเลือกที่จะลด 2ln1 L . เราสามารถเลือกที่สมบูรณ์แบบฉันแต่ให้ต้นทุนของขวัญ โดยแสดงบรรทัดฐานที่ใช้เวลา O ( n ) การดำเนินงานเมื่อเรย์เติบโตจนไม่เหมาะ กริบเรียง array สามารถมองเห็นเป็น l-levels หมุนรายการไม่ . เราสามารถรักษามูลค่าที่เหมาะสมของ L โดยบรรทัดฐาน กับของขวัญที่คงที่ ค่าใช้จ่าย ดังนั้น การรวมต้นทุนจะยังคงเหมือนเดิม