two functions—easyExchange, where t

two functions—easyExchange, where the new smallest
element x < L[i], 0  i < n replaces the largest element
L[m] and returns L[m]; hardExchange is identical
to easy exchange, but x can be any number. This paper
defines an extra function normalize that transform the
rotated list to a sorted array.
As described in (Frederickson 1983), easy exchange
can be done in O(1) operations once L[m] is found, as the
operation only needs to replace L[m] with the new smallest
element x. Array L still satisfies as a rotated list, but
the position m0 of the new largest element L[m0] is leftcircular-
shifted by one (m0 = m - 1, or m0 = n - 1 if
m = 0). Hard exchange is O(n) since it needs to shift
all the elements larger than x in the worst case. Figure 1
shows easy exchange and hard exchange examples on a
rotated list.
Normalization can be done in O(n) time, an obvious
way to achieve this is by having a temporary duplicate but
the exact bound can also be achieved in-place recursively
by using Algorithm 1, which has exactly optimal 2n words
read and 2n words write for the array L. The same algorithm
can also be done iteratively.

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

ฟังก์ชันสอง — easyExchange ที่ใหม่น้อยที่สุดองค์ประกอบ x < L [i], 0 ฉัน < n แทนที่องค์ประกอบที่ใหญ่ที่สุดL [m] และคืน [m]; L hardExchange เป็นเหมือนกันแลกเปลี่ยนให้ง่าย แต่สามารถ x เป็นจำนวนใด ๆ กระดาษนี้กำหนดเพิ่มเติมฟังก์ชันปกติที่แปลงนี้รายการหมุนไปเรียงลำดับตามที่อธิบายไว้ใน (Frederickson 1983), แลกเปลี่ยนง่ายสามารถทำได้ในการดำเนินงานของ O(1) เมื่อพบ L [m] เป็นการการดำเนินงานจำเป็นต้องแทน L [m] กับใหม่น้อยที่สุดตรงองค์ประกอบไฟร์เรย์ L ยังคงเป็นรายการหมุน แต่มี m0 ตำแหน่งขององค์ประกอบที่ใหญ่ที่สุดใหม่ L [m0] leftcircular-เปลี่ยนหนึ่ง (m0 = m - 1 หรือ m0 = n - 1 ถ้าm = 0) แลกเปลี่ยนยากเป็น O(n) เนื่องจากต้องเลื่อนทุกองค์ประกอบมากกว่า x ในกรณีเลวร้ายที่สุด รูปที่ 1แสดงแลกเปลี่ยนง่ายและแลกเปลี่ยนยากตัวอย่างในการรายการหมุนฟื้นฟูสามารถทำได้ใน O(n) ชัดเจนวิธีการเพื่อให้บรรลุนี้คือการมีแต่ซ้ำแบบชั่วคราวขอบเขตที่แน่นอนยังสามารถทำได้ในสถาน recursivelyโดยใช้อัลกอริทึม 1 ซึ่งมีคำสูงสุด 2n ตรงเขียนคำอ่านและ 2n เรย์ L. อัลกอริทึมเดียวกันสามารถทำซ้ำ ๆ

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

สองฟังก์ชั่-easyExchange
ที่มีขนาดเล็กที่สุดใหม่องค์ประกอบx <L [ผม], 0? i <n แทนที่องค์ประกอบที่ใหญ่ที่สุด
L [ม] และผลตอบแทน L [ม]; hardExchange
เป็นเหมือนการแลกเปลี่ยนง่ายแต่ x สามารถเป็นตัวเลขใด ๆ กระดาษนี้จะกำหนดปกติฟังก์ชั่นพิเศษที่เปลี่ยนรายการหมุนเป็นแถวเรียง. ตามที่อธิบายไว้ใน (Frederickson 1983) การแลกเปลี่ยนได้ง่ายสามารถทำได้ในO (1) การดำเนินงานครั้งเดียว L [ม] พบในขณะที่การดำเนินงานเพียงต้องการที่จะแทนที่ L [ม] มีขนาดเล็กที่สุดใหม่องค์ประกอบx อาร์เรย์ L ยังคงตอบสนองเป็นรายการที่หมุน แต่m0 ตำแหน่งขององค์ประกอบใหม่ L ที่ใหญ่ที่สุด [m0] ถูก leftcircular- ขยับโดยหนึ่ง (m0 = เมตร - 1 หรือ m0 = n - 1 ถ้าm = 0) แลกเปลี่ยนที่ยากคือ O (n) เนื่องจากความต้องการที่จะเปลี่ยนองค์ประกอบทั้งหมดที่มีขนาดใหญ่กว่าx ในกรณีที่เลวร้ายที่สุด รูปที่ 1 แสดงให้เห็นถึงการแลกเปลี่ยนได้ง่ายและมีตัวอย่างการแลกเปลี่ยนอย่างหนักในรายการหมุน. ปกติที่สามารถทำได้ใน O (n) เวลาเห็นได้ชัดวิธีการเพื่อให้บรรลุนี้โดยมีซ้ำกันชั่วคราวแต่ขอบเขตที่แน่นอนนอกจากนี้ยังสามารถประสบความสำเร็จในสถานที่ซ้ำโดยโดยใช้อัลกอริทึมที่ 1 ซึ่งมีคำว่า 2n ที่ดีที่สุดในการอ่านและเขียนคำ2n สำหรับอาร์เรย์ลิตรขั้นตอนวิธีการเดียวกันยังสามารถทำซ้ำ

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

สองฟังก์ชัน easyexchange ที่ใหม่ที่สุด
ธาตุ X < L [ I ] , 0  i < n แทนที่ใหญ่ที่สุดองค์ประกอบ
L [ M ] ) L [ M ] ; hardexchange เหมือนกัน
เปลี่ยนง่าย แต่ X สามารถจํานวนใด ๆ
บทความนี้จะกำหนดฟังก์ชันพิเศษปกติที่แปลง
หมุนรายการเพื่อจัดการอาร์เรย์ .
ตามที่อธิบายไว้ใน ( เฟรเดอริกสัน 1983 ) , แลกเปลี่ยนง่าย
ที่สามารถทำได้ใน O ( 1 ) การดำเนินงานเมื่อฉัน [ M ] พบ เช่น การต้องการเพียงแทนที่
L [ M ] กับใหม่น้อยที่สุด
องค์ประกอบ X เรย์ยังน่าพอใจเป็นหมุนรายการ แต่ m0
ตำแหน่งใหม่ขององค์ประกอบที่ใหญ่ที่สุด m0 L [ ] เป็น leftcircular -
เปลี่ยน โดยหนึ่ง ( m0 = M - 1 หรือ - 1 ถ้า m0 =
M = 0 ) แลกยากคือ O ( n ) เนื่องจากความต้องการที่จะเปลี่ยนแปลง
องค์ประกอบทั้งหมดที่มีขนาดใหญ่กว่า X ในกรณีเลวร้ายที่สุด รูปที่ 1
แสดงตราง่าย และยาตราตัวอย่างบน

ปกติหมุนรายการ สามารถทำได้ในเวลา O ( n ) เป็นวิธีที่ชัดเจนเพื่อให้บรรลุนี้โดย

มีซ้ำกันชั่วคราว แต่ผูกพันที่แน่นอนยังสามารถบรรลุในสถานที่ recursively
โดยใช้ขั้นตอนวิธีที่ 1 ซึ่งได้ถูกต้องเหมาะสม 2n
อ่านคำ 2 คำและเขียน array L .
ขั้นตอนวิธีเดียวกันยังสามารถทำซ้ำ .