2.3.2 Library SortBender et al (Ben

2.3.2 Library Sort
Bender et al (Bender et al. 2004) have shown that by having
a wn bits space overhead as gaps, and keeping gaps
evenly distributed by redistributing the gaps when the 2i-
th element is inserted, GAPPED INSERTION SORT, or LIBRARY
SORT for short, has a high probability of achieving
O(n lg n) operations. As most sorting algorithms can
be done in-place, we can make a fair assumption that the
sorted result must use the same memory location. The
auxiliary space cost of LIBRARY SORT is (1 + )wn bits
as it needs to create a temporary continuous array A0. Alternatively,
their approach can be improved by tagging a
temporary auxiliary wn space to A, thus creating a virtual
(1 + )wn size array A0, making the algorithm less
elegant but not affecting the time bound or space bound.
Unfortunately,  needs to be chosen beforehand, and
large  does not guarantee O(n lg n) operations as they
have made an assumption that A is a randomly permuted
sequence within U. To describe it in another way, the algorithm
can randomly permute the input with O(n) time

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

2.3.2 ไลบรารีเรียงBender et al (Bender et al. 2004) มีแสดงที่มีดับเบิ้ลยูเอ็นเป็นบิตพื้นที่จ่ายเป็นช่องว่าง และช่องเก็บกระจายเท่า ๆ กัน โดย redistributing ช่องว่างเมื่อ 2i -องค์ประกอบของ th จะเรียงลำดับแบบแทรกแทรก GAPPED หรือไลบรารีเรียงสั้น ๆ มีความสูงของการบรรลุเป้าหมายการดำเนินการ (n lg n) O อัลกอริทึมการเรียงลำดับมากที่สุดสามารถจะทำในตำแหน่ง เราสามารถทำให้อัสสัมชัญเป็นธรรมที่จะผลการเรียงลำดับต้องใช้ตำแหน่งหน่วยความจำเดียวกัน ที่ต้นทุนในพื้นที่เสริมจัดเรียงไลบรารี (1 +) บิตดับเบิ้ลยูเอ็นเป็นต้องสร้างแบบชั่วคราวอย่างต่อเนื่อง อาร์เรย์ A0 หรือวิธีการของพวกเขาสามารถปรับปรุง โดยการติดป้ายเป็นดับเบิ้ลยูเอ็นเสริมชั่วคราวพื้นที่ให้เป็น ดังนั้นการสร้างเสมือน(1 +) ดับเบิ้ลยูเอ็นขนาดอาร์เรย์ A0 ทำให้อัลกอริทึมน้อยสง่างามแต่ไม่ส่งผลกระทบต่อเวลาที่ผูกหรือพื้นที่ที่ถูกผูกไว้อับ ต้องเลือกล่วงหน้า และใหญ่ไม่รับประกันการดำเนินงาน (n lg n) O เป็นพวกเขาทำให้สมมติฐานที่ว่า คือ permuted สุ่มลำดับภายในประเทศ อธิบายทาง ขั้นตอนวิธีการสามารถสุ่ม permute อินพุต ด้วยเวลา O(n)

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

2.3.2
ห้องสมุดประเภทเบนเดอร์, et al (Bender et al. 2004)
แสดงให้เห็นว่าโดยมีหรือไม่? WN
บิตค่าใช้จ่ายในพื้นที่เป็นช่องว่างและทำให้ช่องว่างการกระจายอย่างสม่ำเสมอโดยกระจายช่องว่างเมื่อ2i-
องค์ประกอบครั้งที่ถูกแทรก gapped แทรกเรียงลำดับ
หรือห้องสมุดเรียงลำดับสำหรับระยะสั้นมีโอกาสสูงในการบรรลุ
O (n ๆ lg n) การดำเนินงาน ในฐานะที่เป็นอัลกอริทึมการเรียงลำดับส่วนใหญ่สามารถทำได้ในสถานที่ที่เราสามารถทำให้สมมติฐานยุติธรรมว่าผลเรียงต้องใช้หน่วยความจำตำแหน่งเดียวกัน ค่าใช้จ่ายในพื้นที่เสริมของห้องสมุดเรียงลำดับคือ (1 +?) บิต WN ตามความต้องการที่จะสร้างอาร์เรย์ชั่วคราว A0 อย่างต่อเนื่อง อีกวิธีหนึ่งคือแนวทางของพวกเขาได้ดีขึ้นโดยการติดแท็กเสริมชั่วคราวพื้นที่WN ถึง A จึงสร้างเสมือน(1 +?) ขนาด WN อาร์เรย์ A0 ทำให้อัลกอริทึมน้อยที่สง่างามแต่ไม่ส่งผลกระทบต่อเวลาที่ถูกผูกไว้หรือพื้นที่ที่ถูกผูกไว้. แต่น่าเสียดายที่? ความต้องการที่จะได้รับการแต่งตั้งก่อนและขนาดใหญ่? ไม่รับประกัน O (n ๆ lg n) การดำเนินงานตามที่พวกเขาได้ทำสมมติฐานที่ว่าเป็นpermuted สุ่มลำดับภายในU. เพื่ออธิบายในอีกทางหนึ่งขั้นตอนวิธีการสุ่มสามารถเปลี่ยนรูปการป้อนข้อมูลที่มีO (n) เวลา

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

2.3.2 ห้องสมุดเรียง
ดัด et al ( ดัด et al . 2547 ) ได้แสดงให้เห็นว่ามีการ  WN บิตพื้นที่เหนือศีรษะเป็นช่องว่าง และรักษาช่องว่าง
กระจายตัวโดยกระจายช่องว่างเมื่อ 2i -
th องค์ประกอบแทรกช่องว่างการเรียงลำดับแบบแทรก หรือห้องสมุด
เรียงสั้น มีความน่าจะเป็นสูงที่จะบรรลุ
o ( N ) N ) งาน ส่วนใหญ่เป็นขั้นตอนวิธีการเรียงลำดับสามารถ
ทำในสถานที่เราสามารถสร้างสมมติฐาน Fair ที่
เรียงผลต้องใช้ตำแหน่งหน่วยความจำเดียวกัน
เสริมต้นทุนเรียงพื้นที่ห้องสมุด ( 1  ) รูปแบบบิต
ตามความต้องการที่จะสร้าง A0 เรย์อย่างต่อเนื่อง ชั่วคราว หรือ
วิธีการของพวกเขาสามารถปรับปรุงให้มี
ชั่วคราวเสริม  WN พื้นที่ให้ ดังนั้น การสร้างเสมือน
( 1  ) รูปแบบอาร์เรย์ขนาด A0 ให้น้อยลง
ขั้นตอนวิธีหรูหราแต่ไม่มีผลต่อเวลา จำกัด หรือพื้นที่ที่ถูกผูกไว้ 
ขออภัย ต้องเลือกไว้ล่วงหน้า และ 
ขนาดใหญ่ไม่รับประกัน O ( N ) N ) ปฏิบัติการตามที่พวกเขา
ทำให้สมมติฐานที่ว่าเป็นแบบสุ่ม permuted
ลำดับภายใน U ที่จะอธิบายมัน ในอีกทางหนึ่ง , อัลกอริทึม
สามารถสุ่มเรียงลำดับข้อมูลด้วย O ( n ) เวลา