Proof. For insert in ROTATED LIBRAR

Proof. For insert in ROTATED LIBRARY SORT, hard exchanges on Jk are unavoidable initially. However, the larger the  is, fewer hard exchanges on Jr−1 will be required at the end. Therefore, the worst case sceanrio happens when insertion occurs at Jk where k = r/2. Each in sertion consists of a binary search with O(lgr)operations. The first (f(k)−1) insertions include a hard exchange, that costs worst case O(f(k)) operations, because of the empty gaps. The (f(k))-th insertion will incur the initial hard exchange plus a soft exchange on Jk+1 that costs O(f(k)) operations.

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

หลักฐานการ การแทรกในหมุนจัดเรียงไลบรารี แลกเปลี่ยนยากใน Jk ได้หลีกเลี่ยงไม่ได้เริ่ม อย่างไรก็ตาม มีขนาดใหญ่เป็น แลกเปลี่ยนยากน้อยกว่าใน Jr−1 จะต้องจบ ดังนั้น sceanrio กรณีเลวร้ายที่สุดเกิดขึ้นเมื่อแทรกที่ Jk ที่ k = r/2 แต่ละใน sertion ประกอบด้วยการค้นหาแบบไบนารี O (lgr) การดำเนินงาน first (f(k)−1) แทรกรวมถึงแลกเปลี่ยนยาก ว่า ต้นทุนที่เลวร้ายที่สุดกรณีดำเนินงาน O(f(k)) เนื่องจาก มีช่องว่าง (F(k)) -th แทรกจะใช้แลกเปลี่ยนยากเริ่มต้นพร้อมแลกเปลี่ยนนุ่ม Jk + 1 ที่ค่าใช้จ่ายที่ O (f(k)) การดำเนินการ

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

หลักฐาน สำหรับใส่ในห้องสมุดหมุนเรียงลำดับการแลกเปลี่ยนอย่างหนักใน Jk จะหลีกเลี่ยงไม่ในขั้นต้น แต่ที่มีขนาดใหญ่หรือไม่ มีการแลกเปลี่ยนอย่างหนักน้อยลงในจูเนียร์-1 จะต้องในตอนท้าย ดังนั้น sceanrio กรณีที่เลวร้ายที่เกิดขึ้นเมื่อแทรกที่เกิดขึ้นใน Jk ที่ k = R / 2 ในแต่ละ sertion ประกอบด้วยการค้นหาแบบไบนารีกับ O (LGR) การดำเนินงาน สายแรก (? f (k) -1) รวมถึงการแทรกการแลกเปลี่ยนอย่างหนักที่ค่าใช้จ่ายกรณีที่เลวร้าย O (f (k)) การดำเนินงานเพราะช่องว่างที่ว่างเปล่า (F (k)?) - ณ แทรกจะเกิดการแลกเปลี่ยนการเริ่มต้นอย่างหนักรวมทั้งการแลกเปลี่ยนอ่อน Jk + 1 ที่ค่าใช้จ่ายการดำเนินงาน O (f (k)?)

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

พิสูจน์ สำหรับแทรกในหมุนเรียงห้องสมุด , แลกเปลี่ยนยาก เจเค จะหลีกเลี่ยงไม่ได้ในตอนแรก อย่างไรก็ตาม , ขนาดใหญ่  เป็นน้อยยากแลกเปลี่ยน JR − 1 จะต้องอยู่ที่ปลาย ดังนั้น กรณีเลวร้ายที่สุด sceanrio เกิดขึ้นเมื่อแทรกเกิดขึ้นที่ JK ที่ K = r / 2 ในแต่ละ sertion ประกอบด้วยการค้นหาแบบไบนารีที่มี O ( lgr ) งาน จึงตัดสินใจเดินทางไป (  F ( K ) − 1 ) ใหม่รวมถึงแลกเปลี่ยนยากที่ค่าใช้จ่ายที่เลวร้ายที่สุดกรณี O ( F ( k ) การดำเนินงาน เพราะช่องว่างที่ว่างเปล่า (  F ( k ) ) - . th จะต้องเสียเริ่มต้นยากแลกบวกตรานุ่ม JK 1 ราคา O (  F ( k ) ) งาน