ICS 161: Design and Analysis of Alg

ICS 161: Design and Analysis of Algorithms
Lecture notes for January 30, 1996

Deterministic selection
Last time we saw quick select, a very practical randomized linear expected time algorithm for selection and median finding. In practice, this is all you need to use. But for theoretical purposes, it's unsatisfying to have only a randomized algorithm, and in some rare circumstances it may more important to be predictable than to be fast. So can we get a linear worst case time algorithm? We'll describe a solution invented by five people: Blum, Floyd, Pratt, Rivest, and Tarjan.

Recall that quickselect chooses a random "pivot" x, partitions the list into elements less than and greater than x, and calls itself recursively in one of the two sublists. The even quicker selection method I outlined does something similar, but chooses the pivot in a complicated way, by calling itself recursively in a random sample of the input. Our deterministic algorithm will use the same idea of choosing x by performing a recursive call.

If we could do so quickly, one good choice would simply be to let x be the median of the values. Then each recursive call would only be on a subset of half the values. But of course if we knew how to find the median, we'd be done, so finding the median is too good to hope for. Instead let's just try to get something close to the median (say within n/4 positions of it). Then each recursive call would be on a larger fraction of the input (3n/4) but this still might be good enough.
Median of medians
How can we get something close to the median, reasonably quickly? Just like the "quicker selection", Instead of finding the median of the whole set, find a median of a sample. How do we choose the sample? Medians again!

Median-of-medians algorithm:

Line up elements in groups of five (this number 5 is not important, it could be e.g. 7 without changing the algorithm much). Call each group S[i], with i ranging from 1 to n/5.
Find the median of each group. (Call this x[i]). This takes 6 comparisons per group, so 6n/5 total (it is linear time because we are taking medians of very small subsets).
Find the median of the x[i], using a recursive call to the algorithm. If we write a recurrence in which T(n) is the time to run the algorithm on a list of n items, this step takes time T(n/5). Let M be this median of medians.
Use M to partition the input and call the algorithm recursively on one of the partitions, just like in quickselect.

Can we say anything about how many items are included in this last recursive call? It's easier to talk about this in terms of the elements thrown away (not included in the call).

We always throw away either L3 (the values greater than M) or L1 (the values less than M). Suppose we throw away L3.

Among the n/5 values x[i], n/10 are larger than M (since M was defined to be the median of these values).

For each i such that x[i] is larger than M, two other values in S[i] are also larger than x[i] (since x[i] is the median of S[i]).

So L3 has at least 3 elements in each of at least n/10 groups S[i], for a total of at least 3n/10 elements. By a symmetric argument, L1 has at least 3n/10 elements.

Therefore the final recursive call is on a list of at most 7n/10 elements and takes time at most T(7n/10).

This algorithm has the property we want, that each recursive call only involves a constant fraction of the input.
Deterministic selection algorithm
Before we analyze our algorithm, let's write it out more carefully in pseudocode. Also, instead of using a special algorithm to find the median in each subset S[i], let's just call the method recursively again. To prevent infinite recursion, we have to stop when L is so small that there aren't enough x[i] values to find medians of.

select(L,k)
{
if (L has 10 or fewer elements)
{
sort L
return the element in the kth position
}

partition L into subsets S[i] of five elements each
(there will be n/5 subsets total).

for (i = 1 to n/5) do
x[i] = select(S[i],3)

M = select({x[i]}, n/10)

partition L into L1M
if (k length(L1)+length(L2))
return select(L3,k-length(L1)-length(L2))
else return M
}

Analysis
The pseudo-code above gives us a number of comparisons that can be found by solving the recurrence

T(n)

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

ICS 161: การออกแบบและการวิเคราะห์อัลกอริทึม
บันทึกการบรรยายกับ 30 มกราคม 1996


เลือกกำหนดเวลาที่ผ่านมาเราได้เห็นการเลือกอย่างรวดเร็วแบบสุ่มเชิงเส้นจริงมากคาดว่าขั้นตอนวิธีการสำหรับการเลือกเวลาและหาค่าเฉลี่ย ในทางปฏิบัตินี้เป็นสิ่งที่คุณจำเป็นต้องใช้ แต่สำหรับวัตถุประสงค์ทางทฤษฎีก็พอใจที่จะมีเพียงขั้นตอนวิธีการสุ่มและในกรณีที่หายากบางอย่างมันอาจจะมีความสำคัญมากขึ้นเพื่อให้การคาดการณ์กว่าที่จะได้อย่างรวดเร็ว เพื่อให้เราสามารถได้รับกรณีที่เลวร้ายขั้นตอนวิธีการเชิงเส้นเวลา? เราจะอธิบายการแก้ปัญหาการประดิษฐ์คิดค้นโดยคนห้าคน. บลัม, ฟลอยด์แพรตต์, Rivest และ Tarjan

เรียกว่า quickselect เลือกสุ่ม "หมุน" x, พาร์ติชันรายการเป็นองค์ประกอบน้อยกว่าและมีค่ามากกว่า x,และเรียกตัวเองซ้ำในหนึ่งในสองรายการย่อย วิธีการเลือกได้เร็วผมจะอธิบายบางสิ่งบางอย่างที่คล้ายกัน แต่เลือกที่หมุนในวิธีที่ซับซ้อนโดยเรียกตัวเองซ้ำในกลุ่มตัวอย่างแบบสุ่มของข้อมูล ขั้นตอนวิธีการที่กำหนดของเราจะใช้ความคิดเดียวกันในการเลือก x โดยการโทรซ้ำ.

ถ้าเราสามารถทำเช่นนั้นได้อย่างรวดเร็วหนึ่งทางเลือกที่ดีก็จะให้ x เป็นค่าเฉลี่ยของค่า แล้วแต่ละสายซ้ำเพียง แต่จะเป็นในส่วนของค่าครึ่ง แต่แน่นอนถ้าเรารู้วิธีการหาค่าเฉลี่ยที่เราต้องการจะทำเพื่อหาค่ามัธยฐานเป็นสิ่งที่ดีเกินไปที่จะหวัง แทนให้เพียงพยายามที่จะได้รับสิ่งที่ใกล้เคียงกับค่ามัธยฐาน (พูดภายใน n / 4 ตำแหน่งของมัน)แล้วแต่ละสาย recursive จะอยู่บนส่วนใหญ่ของที่นำเข้า (3n / 4) แต่ตอนนี้ยังอาจจะมีดีพอ.
เฉลี่ยของมีเดีย
วิธีการที่เราจะได้รับสิ่งที่ใกล้เคียงกับค่าเฉลี่ยที่เหมาะสมได้อย่างรวดเร็ว เช่นเดียวกับ "เลือกเร็ว" แทนการหาค่าเฉลี่ยของทั้งชุดหาค่าเฉลี่ยของกลุ่มตัวอย่าง ทำอย่างไรเราจะเลือกตัวอย่างหรือไม่ ! มีเดียอีกครั้ง

มัธยฐานของมีเดียขั้นตอนวิธีการ:

แถวองค์ประกอบในกลุ่มห้า (5 หมายเลขนี้ไม่สำคัญมันอาจจะเช่น 7 โดยไม่มีการเปลี่ยนแปลงขั้นตอนวิธีการมาก) เรียกแต่ละกลุ่ม s [i] กับฉันตั้งแต่ 1 ถึง n / 5.
หาค่าเฉลี่ยของแต่ละกลุ่ม (เรียก x นี้ [i]) นี้จะใช้เวลา 6 เปรียบเทียบต่อกลุ่มเพื่อ 6n / 5 รวม (เป็นเวลาเชิงเส้นเพราะเราจะพามีเดียของส่วนย่อยขนาดเล็กมาก).
หาค่าเฉลี่ยของ x [i]ใช้โทรซ้ำขั้นตอนวิธีการ ถ้าเราเขียนเกิดขึ้นอีกในการที่ T (n) เป็นเวลาที่จะใช้ขั้นตอนวิธีการในรายชื่อของรายการ n ขั้นตอนนี้จะใช้เวลาเวลา t (n / 5) ให้เป็นเมตรเฉลี่ยของมีเดียนี้.
ใช้เมตรพาร์ทิชันการป้อนข้อมูลและขั้นตอนวิธีการเรียกซ้ำบนหนึ่งในพาร์ทิชันเช่นเดียวกับใน quickselect.

เราสามารถพูดอะไรเกี่ยวกับจำนวนรายการที่จะถูกรวมในการเรียกซ้ำที่ผ่านมานี้มันง่ายที่จะพูดคุยเกี่ยวกับเรื่องนี้ในแง่ขององค์ประกอบโยนออกไป (ไม่รวมอยู่ในการเรียก).

เรามักจะโยนออกไปอย่างใดอย่างหนึ่ง l3 (ค่าสูงกว่าเมตร) หรือ l1 (ค่าน้อยกว่าเมตร) สมมติว่าเราทิ้ง l3.

ระหว่างค่า n / 5 x [i], n/10 มีขนาดใหญ่กว่าเมตร (ตั้งแต่เมตรถูกกำหนดให้เป็นค่าเฉลี่ยของค่าเหล่านี้).

สำหรับแต่ละ i เช่นว่า x [i ] มีขนาดใหญ่กว่าเมตรสองค่าอื่น ๆ ใน s [i] นอกจากนี้ยังมีขนาดใหญ่กว่า x [i] (ตั้งแต่ x [i] เป็นค่ามัธยฐานของ s [i]).

เพื่อ l3 มีอย่างน้อย 3 องค์ประกอบในแต่ละอย่างน้อย n/10 กลุ่ม s [i] รวมอย่างน้อย 3n/10 องค์ประกอบ โดยอาร์กิวเมนต์สมมาตร l1 มีอย่างน้อย 3n/10 องค์ประกอบ.

จึงโทรซ้ำสุดท้ายคือในรายการที่มากที่สุด 7n/10 องค์ประกอบและต้องใช้เวลาส่วนใหญ่ที่ t (7n/10).

ขั้นตอนวิธีนี้มีคุณสมบัติที่เราต้องการที่แต่ละสายซ้ำเพียง แต่เกี่ยวข้องกับส่วนที่คงที่ของท่าน. ขั้นตอนวิธีการเลือก

กำหนดก่อนที่เราจะวิเคราะห์ขั้นตอนวิธีการของเราให้เขียนมันออกมาอย่างระมัดระวังมากขึ้นใน pseudocode ยังแทนการใช้ขั้นตอนวิธีการพิเศษที่จะหาค่าเฉลี่ยในแต่ละเซต s [i] ให้เพียงเรียกวิธีการซ้ำอีกครั้ง เพื่อป้องกันไม่ให้เรียกซ้ำที่สิ้นสุดเราต้องหยุดเมื่อลิตรมีขนาดเล็กที่มีไม่เพียงพอ x [i] ค่าที่จะหาของมีเดีย.

เลือก (l, k)

{ถ้า (l มี 10 หรือน้อยกว่าธาตุ)
{
เรียงลิตร
กลับองค์ประกอบในตำแหน่ง KTH}


พาร์ทิชันลิตรเป็นส่วนย่อย s [i] ของห้าองค์ประกอบแต่ละ
(จะมี n / 5 ย่อยรวม).

for (i = 1 ถึง n / 5) ทำ
x [i] = เลือก (s [i], 3)

m = เลือก ({x [i]}, n/10) ลิตร

พาร์ทิชันเป็น l1 m
ถ้า (k <= ความยาว (l1))
กลับเลือก (l1, k)
อื่นถ้า (k> ระยะเวลา (l1) ระยะเวลา (l2))
กลับเลือก (l3, k ยาว (l1) ความยาว (l2) )
อื่นกลับ} m



วิเคราะห์หลอกโค้ดข้างต้นทำให้เรามีจำนวนของการเปรียบเทียบที่สามารถพบได้โดยการแก้กำเริบ

T (n) <= 12N / 5 T (n / 5) T (7n / 10)

12N / 5 คำมาจากสองสถานที่: เราสามารถเรียงลำดับ [i] แต่ละชุดกับเจ็ดเปรียบเทียบ (บ้าน 2.31)ดังนั้นขั้นตอนในการที่เราคำนวณ x [i] ค่าใช้ 7n / 5 เปรียบเทียบรวม แล้วขั้นตอนในการที่เราแบ่งพาร์ติชันลิตรใช้ n-1 เพิ่มเติม อีกสองคำมาจากสองสายซ้ำในการที่เราพบเมตรและจากนั้นค่าตอบแทนโดยรวม ในขณะที่เรากล่าวก่อนหน้านี้การเรียกซ้ำที่สองคือในรายการที่มากที่สุด 7n/10 องค์ประกอบจึงทีของ (7n/10) ผูกพัน.

จริงกับบางดูแลมากขึ้นเราสามารถทำได้ดีขึ้นเล็กน้อย: เราไม่ได้จริงๆต้องในการจัดเรียงชุด s [i] เพียงแค่หามีเดียของพวกเขาซึ่งจะต้อง 6n / 5 เปรียบเทียบ ข้อมูลที่เกิดขึ้นพร้อมกับการคำนวณของเมตรแล้วควรจะเพียงพอที่จะกำจัด 3n/10 องค์ประกอบจากลิตร เพื่อให้เราสามารถได้รับการเกิดขึ้นอีกด้วย 6n / 5 ในสถานที่ของ 12N / 5 ข้างต้นและบันทึกปัจจัยที่สองในการเปรียบเทียบรวม แต่เนื่องจากผลนี้เป็นส่วนใหญ่ที่น่าสนใจทฤษฎีฉันได้ทิ้งมันไว้ในที่เรียบง่ายและง่ายต่อการเข้าใจรูปแบบดังกล่าวข้างต้น.

กำเริบนี้ดูเหมือนว่าหนึ่งมาจากการแบ่งและพิชิตอัลกอริทึม แต่หนึ่งในปัญหาที่แยกส่วนไม่เท่ากัน แต่ในกรณีนี้ความจริงที่สำคัญคือส่วนเพิ่มขึ้นน้อยกว่าทั้งเมื่อเกิดเหตุการณ์นี้มันไม่สำคัญเท่าว่าเท่ากันหรือไม่เท่ากันพวกเขามี.

มีสองวิธีในการวิเคราะห์ปัญหาที่เกิดขึ้นเช่นนี้ ครั้งแรกเป็นวิธีการที่ผมแสดงให้เห็นว่าการ quickselect ซึ่งเราพยายามที่จะสร้างหลักฐานอุปนัยว่าสิ่งที่เป็น O (n) โดยสมมติว่ามัน cn สำหรับบางคโดยเฉพาะการขยายตัวทางด้านขวาของการเกิดซ้ำและการทำงานผ่านทางคณิตศาสตร์เพื่อตรวจสอบ สิ่งที่ควรจะเป็นคในกรณีที่เรามี

T (n) <= 12N / 5 T (n / 5) T (7n/10)

= 12N / 5 CN / 5 7cn/10

n = (12/5 9c / 10)

ถ้าเป็นไปได้ที่มากที่สุด CN เพื่อให้หลักฐานเหนี่ยวนำผ่านไปเราต้องให้มันเป็นความจริงที่ว่า

n (12/5 9c/10) <= CN

12/5 9c/10 <= c

12/5 <= c/10

c <= 24

ที่บอกเราว่าเราสามารถพิสูจน์โดยอุปนัยว่า T (n) <= 24N (หรือเวลาใด ๆ ที่มีขนาดใหญ่อย่างต่อเนื่อง n)เรายังต้องจัดการกับกรณีฐาน แต่ที่เป็นเรื่องง่าย.

วิธีที่สองในการวิเคราะห์การเกิดขึ้นอีกเช่นนี้คือการวาดต้นไม้แสดงขนาดของปัญหาในแต่ละโทรซ้ำและวิเคราะห์ขนาดรวมของปัญหา แต่ละระดับของต้นไม้จำนวนรวมของการเปรียบเทียบนั้นจะสามารถพบโดยการคูณขนาด subproblem นี้โดยรวมเป็นปัจจัยที่ 12/5 ของการเปรียบเทียบต่อองค์ประกอบในแต่ละสาย ต้นไม้เริ่มต้นด้วยปัญหารากขนาด n แล้​​วแต่ละโหนดมีสองปัญาเหล่านี้เป็นหนึ่งในขนาด 1/5 สำหรับผู้ปกครองของตนและคนอื่น ๆ ที่มีขนาด 7/10 แม่.

n
/
n / 5 7n / 10
/ /
n/25 7n/50 7n/50 49n/100
/ / / /

ปัญหาในระดับหนึ่งในแต่ละจะถูกแทนที่ด้วยสองปัญหาในระดับถัดลงของขนาดราคา 1/5 และ 7/10 ผู้ปกครอง ดังนั้นขนาดรวมในระดับต่อไปคือ 1/5 7/10 = 9/10 ที่ระดับก่อนหน้า (บางครั้งแม้แต่น้อยเมื่อ subproblem ถึงกรณีฐานและไม่ได้โทรซ้ำมากกว่า).

จึงทั้งหมด จำนวนของการเปรียบเทียบเป็น

12/5 (n 9n/10 81n/100 ... )

= 12/5 n (1 9/10 (9/10)
2 (9/10)
3 ... )

= 12/5 n 1 / (1 - (9/10))

= 24N

เป็นกฎทั่วไปชุดรวมทางเรขาคณิต (x
i) (สําหรับผมจาก 0 ถึง n-1) แก้ (1-x
n) / (1-x) และเมื่อใดก็ตามที่ x น้อยกว่า 1 ขีด จำกัด ของผลรวมเป็น n ไปที่อินฟินิตี้กลายเป็น 1 / (1-x) ผลรวมที่กล่าวมาเป็นเพียงกรณีของสูตรนี้ในการที่ x = 9/10 วิธีต้นไม้ขยายตัวเดียวกันแล้วแสดงให้เห็นว่ามากกว่าปกติถ้า T (n) <= th T () T (พันล้าน) ที่ข <1 ครั้งรวมเป็นค (1 / (1-AB)) n.

ดังนั้นขั้นตอนวิธีการเลือกของเรากำหนดใช้ที่มากที่สุดเปรียบเทียบ 24N และใช้เวลา O (n) เวลา.

มีจำนวนมากของการทำงานอย่างใดอย่างหนึ่งสามารถลดจำนวนของการเปรียบเทียบเพื่อ 2.95n [เห็นง และโด u zwick "เลือกค่ามัธยฐาน" โซดา 6, 1995] ซึ่งเป็นเพียงเล็กน้อยน้อยกว่าสองเท่าของการเลือกสุ่มแต่มีความซับซ้อนมากขึ้นและในทางปฏิบัติน้อย

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

ICS 161: ออกแบบและการวิเคราะห์อัลกอริทึม
บรรยายบันทึกย่อสำหรับ 30 มกราคม ปี 1996

เลือก Deterministic
เลือกครั้งสุดท้ายที่เราเห็นด่วน ขั้นตอนวิธีปฏิบัติมาก randomized เวลาคาดเส้นสำหรับเลือกและค้นหามัธยฐาน ในทางปฏิบัติ นี่คือทั้งหมดที่คุณจำเป็นต้องใช้ แต่ทฤษฎีประสงค์ unsatisfying จะมีเฉพาะแบบ randomized อัลกอริธึม และในบางกรณียาก อาจสำคัญเป็นได้มากกว่าการได้อย่างรวดเร็ว ดังนั้น เราจึงสามารถรับเส้นตอนวิธีเวลากรณีเลวร้ายที่สุด เราจะอธิบายถึงการแก้ปัญหาที่คิดค้น โดยคน 5: สุ่ม ฟลอยด์ คิด Rivest แล้ว Tarjan

เรียกคืน quickselect ที่เลือกสาระการสุ่ม "สำคัญ" ผนังกั้นเป็นองค์ประกอบน้อยกว่า และมากกว่า x, x รายการ และเรียกตัวเอง recursively sublists สองหนึ่ง วิธีเลือกเร็วแม้ฉันอธิบายไม่คล้าย แต่เลือก pivot ในแบบซับซ้อน โดยเรียกตัวเอง recursively ในตัวอย่างที่สุ่มของอินพุต อัลกอริทึม deterministic ของเราจะใช้แนวคิดเดียวกันเลือก x โดยการเรียกซ้ำการ

ถ้าเราสามารถทำได้อย่างรวดเร็ว ทางเลือกหนึ่งที่ดีก็จะให้ x เป็นค่ามัธยฐานของค่า แล้ว แต่ละการเรียกซ้ำเฉพาะจะบนชุดย่อยของค่าครึ่ง แต่แน่นอนถ้าเรารู้วิธีการหาค่ามัธยฐาน เราจะสามารถ ทำ เพื่อค้นหาค่ามัธยฐานได้ดีหวังว่า แต่ เพียงลองไปสิ่งใกล้กับมัธยฐาน (พูดในตำแหน่ง n/4 ของมัน) แล้วจะเรียกแต่ละซ้ำในส่วนใหญ่ของการป้อนข้อมูล (4 วัน 3 คืน) แต่นี้ยังอาจจะดีพอ.
มัธยฐานของ medians
ว่าเราได้สิ่งที่ใกล้กับมัธยฐาน สมเหตุสมผลอย่างรวดเร็ว เหมือนที่ "เร็วเลือก" แทนการหามัธยฐานของชุดทั้งหมด ค้นหาค่ามัธยฐานของตัวอย่าง เราเลือกตัวอย่างได้อย่างไร Medians อีก!

มัธยฐานของ medians อัลกอริทึม:

จัดองค์ประกอบในกลุ่มที่ห้า (5 หมายเลขนี้ไม่สำคัญ เป็นเช่น 7 โดยไม่ต้องเปลี่ยนอัลกอริทึมมาก) เรียกแต่ละกลุ่ม S [i], กับผมตั้งแต่ 1 ถึง n/5.
หาค่ามัธยฐานของกลุ่มแต่ละกลุ่ม (โทร x[i]) นี้ นี้ใช้เปรียบเทียบ 6 ต่อ (เป็นเส้นตรงเวลาเนื่องจากเราจะมี medians ของชุดย่อยขนาดเล็กมาก) รวมกลุ่ม ดังนั้น 6n/5.
หามัธยฐานของ x [i], โดยใช้การเรียกซ้ำอัลกอริทึม ถ้าเราเขียนเกิดที่ T(n) เป็นเวลาที่จะเรียกใช้อัลกอริทึมรายการ n ขั้นตอนนี้ใช้เวลา T(n/5) ให้ M เป็นค่ามัธยฐานนี้ของ medians
M ใช้เพื่อแบ่งพาร์ติชันข้อมูลป้อนเข้า และเรียก recursively อัลกอริทึมของพาร์ติชัน เหมือนใน quickselect

สามารถเราพูดอะไรเกี่ยวกับสินค้าจะรวมอยู่ในนี้เรียกซ้ำสุดท้าย ง่ายต่อการพูดคุยเกี่ยวกับเรื่องนี้ในแง่ขององค์ประกอบขึ้นไป (ไม่รวมในการโทร)

เราจะทิ้งทั้ง L3 (ค่า M มากกว่า) หรือ L1 (ค่าน้อยกว่า M) สมมติว่าเราทิ้ง L3

ค่า n/5 x [i], n/10 หมู่มากกว่า M (ตั้งแต่ M ถูกกำหนดเป็น ค่ามัธยฐานของค่าเหล่านี้)

สำหรับแต่ละ i เช่นที่ x [i] ใหญ่กว่า M ยังมีค่าอื่น ๆ สองใน S [i] มากกว่า x [i] (ตั้งแต่ x [i] คือค่ามัธยฐานของ S[i])

L3 ให้ได้อย่างน้อย 3 ส่วนในแต่ละกลุ่มน้อย n/10 S [i], สำหรับผลรวมขององค์ประกอบอย่างน้อย 3 คืน/10 อาร์กิวเมนต์สมมาตร L1 มีองค์ประกอบอย่างน้อย 3 คืน/10.

ดังนั้นการเรียกซ้ำสุดท้ายเป็นรายการขององค์ประกอบที่สุด 7n/10 และใช้เวลามากที่สุด T(7n/10).

อัลกอริทึมนี้มีคุณสมบัติที่เราต้องการ ที่ซ้ำแต่ละโทรเฉพาะเกี่ยวข้องกับเศษส่วนคงที่ของเข้า
Deterministic เลือกอัลกอริทึม
ก่อนเราวิเคราะห์ขั้นตอนวิธีของเรา ลองเขียนออกเพิ่มเติมรหัสเทียมอย่างระมัดระวังในการ แทนที่จะใช้อัลกอริทึมพิเศษหาค่ามัธยฐานในแต่ละชุดย่อย S [i], ลองเพียงโทร recursively วิธีอีกด้วย ให้สอบอนันต์ เราต้องหยุดเมื่อ L ขนาดเล็กที่มีไม่เพียงพอ x [i] ค่าหา medians ของ

select(L,k)
{
ถ้า (L มีองค์ประกอบ 10 หรือน้อยกว่า)
{
เรียง L
กลับองค์ประกอบในตำแหน่งที่ kth
}

พาร์ทิชัน L เป็นชุดย่อย S [i] ห้าองค์ประกอบ
(จะมี n/5 ชุดย่อยรวม) .

สำหรับ (ฉัน = 1 n/5) ทำ
x [i] =เลือก (S [i], 3)

M =เลือก ({x [i] }, n/10)

พาร์ทิชัน L เป็น L1 < M, L2 = M, L3 > M
ถ้า (k < = length(L1))
กลับ select(L1,k)
ถ้าอื่น (k > length(L1) length(L2))
กลับ select(L3,k-length(L1)-length(L2))
อื่น กลับ M
}

วิเคราะห์
รหัสเทียมข้างให้จำนวนเปรียบเทียบที่สามารถพบได้ โดยการแก้ปัญหาที่เกิดขึ้น

T(n) < = 12n/5 T(n/5) T(7n/10)

คำ 12n/5 มาสอง: เราสามารถเรียงลำดับของชุด S [i] กับเจ็ดเปรียบเทียบ (การบ้าน 2.31), ดังนั้นในขั้นตอนที่เราคำนวณ x [i] ค่าเปรียบเทียบ 7n/5 ใช้เวลารวม แล้วขั้นตอนในการที่เราผนัง L ใช้ n-1 เปรียบเทียบเพิ่มเติม สองเงื่อนไขอื่น ๆ มาจากการเรียกซ้ำสอง ที่เราค้นหา M และค่าที่ส่งคืนโดยรวม เราพูดถึงก่อนหน้านี้ การโทรซ้ำสองเป็นรายการขององค์ประกอบที่สุด 7n/10 ดังนั้น T(7n/10) ความผูกกัน

จริง ด้วยดูแลบางอย่างเราสามารถทำได้ดีขึ้น: เราไม่ต้องการจริง ๆ เรียงชุด S [i] เพียงแค่หาของ medians ซึ่งต้องเปรียบเทียบ 6n/5 เท่านั้น ข้อมูลผลลัพธ์ กับ M การคำนวณแล้วควรพอที่จะกำจัดองค์ประกอบ 3 คืน/10 จาก L. ดังนั้น เราอาจได้รับเกิดกับ 6n/5 แทน 12n/5 กล่าว และบันทึกปัจจัยในการเปรียบเทียบทั้งหมด แต่เนื่องจากผลนี้เป็นส่วนใหญ่ของทฤษฎีดอกเบี้ย ฉันได้ทิ้ง ในเรียบง่าย และง่ายเข้าใจแบบฟอร์มข้างต้น

นี้เกิดเหมือนหนึ่งมาจากการแบ่ง และพิชิตอัลกอริทึม แต่ที่แยกส่วนปัญหาไม่ แต่ในกรณีนี้ ข้อเท็จจริงที่สำคัญ ว่า ส่วนที่เพิ่มขึ้นจะน้อยกว่าทั้งหมด เมื่อนี้เกิดขึ้นมันไม่ได้เรื่องเท่าไรมาก หรือไม่ก็มี

มีสองวิธีในการวิเคราะห์ปัญหานี้ แรกเป็นวิธีผมพบสำหรับ quickselect ซึ่งเราพยายามเพื่อพิสูจน์การเหนี่ยวสิ่ง O(n) โดยสมมติของ cn สำหรับบางเฉพาะ c ขยายด้านขวาเกิดขึ้น และทำงานโดยใช้คณิตศาสตร์เพื่อกำหนด c อะไรควร ในกรณีของเรา

T(n) < = 12n/5 T(n/5) T(7n/10)

= 12n/5 cn/5 7cn/10

= n (9c 12/5 10)

ถ้าเป็นเป็น cn มากที่สุดเพื่อให้การเหนี่ยวนำหลักฐานไปผ่าน ที่เราต้องการให้ ที่จริง

n (9c 12/5 10) < = cn

9c 12/5/10 < = c

12/5 < = c/10

c < = 24

ซึ่งบอกเราว่า เราสามารถพิสูจน์ โดยการเหนี่ยวนำ T(n) ที่ < = 24n (หรืออื่น ๆ ค่าคงมีขนาดใหญ่เวลา n) เรายังจำเป็นต้องจัดการกับกรณีพื้นฐาน แต่ที่พัก

ตอนที่สองการวิเคราะห์เกิดขึ้นเช่นนี้เป็นการ วาดแผนภูมิที่แสดงขนาดของปัญหาในแต่ละการเรียกซ้ำ และวิเคราะห์ขนาดของปัญหาในแต่ละระดับของแผนภูมิ แล้วจะพบจำนวนการเปรียบเทียบคูณนี้ขนาด subproblem โดยตัว 12/5 ของเปรียบเทียบสำหรับแต่ละองค์ประกอบในการเรียกแต่ละ เริ่มต้นกับปัญหารากขนาด n แล้ว แต่ละโหนมี subproblems สอง หนึ่งขนาด 1/5 หลัก และอื่น ๆ ของขนาด 7/10 หลัก

n
/
7n/10 n/5
/ /
n/25 7n/50 7n/50 49n/100
/ / / /

แต่ละปัญหาในระดับหนึ่งถูกแทนที่ ด้วยปัญหาสองระดับถัดไปลง ขนาด 1/5 และ 7/10 หลัก ดังนั้นขนาดในระดับถัดไปเป็น 1/5 7/10 = 9/10 ของระดับก่อนหน้า (บางครั้งแม้แต่น้อยเมื่อเป็น subproblem ถึงกรณีพื้นฐาน และไม่ทำการเรียกซ้ำเติม)

ดังนั้นจำนวนเปรียบเทียบ

5 12 (n 9n/10 81n/100...)

12/5 n = (1 9/10 (9/10)
2 (9/10)
3...)

= 12/5 1/(1-(9/10)) n

= 24n

เป็นกฎทั่วไป sum(x
i) อนุกรมเรขาคณิต (สำหรับ i 0 n-1) แก้ (1-x
n)/(1-x) และเมื่อ x คือ 1 น้อยกว่า จำนวน รวมเป็น n ไปว่าย 1/(1-x) ผลรวมข้างต้นเป็นเพียงกรณีของสูตรนี้ในที่ x = 9/10 วิธีการขยายแผนภูมิเดียวกันแล้วแสดงว่า มากขึ้นโดยทั่วไป ถ้า T(n) < = cn T(an) T(bn), b การ < 1 เวลารวมเป็นราคา c(1/(1-a-b)) n.

ดังนั้นอัลกอริทึมเราเลือก deterministic ใช้มากที่สุดเปรียบเทียบ 24n และ O(n) เวลานั้น

มีงาน หนึ่งสามารถลดจำนวนเปรียบเทียบกับ 2.95n [D. ดูฎและสหรัฐ Zwick "เลือกมัธยฐาน" โซดา 6, 1995] ซึ่งเป็นเล็กน้อยน้อยกว่าสองเท่าเป็น randomized เลือก แต่มีความซับซ้อนมากขึ้น และปฏิบัติน้อย

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

ICS 161 การออกแบบและการวิเคราะห์ในอัลกอริธึม
การบรรยายสำหรับวันที่ 30 มกราคม 1996

เซคแบบรู้ค่าแน่นอนการเลือก
ครั้งสุดท้ายเราก็เห็นเลือกอย่างรวดเร็วเวลาเหมาะสมอย่างดีเยี่ยมแบบสุ่มตัวอย่างตามแนวยาวคาดว่าที่อัลกอริทึมสำหรับการเลือกและเกาะกลางถนนค้นหา ในการฝึกซ้อมนี้มีทั้งหมดที่คุณจำเป็นต้องใช้ แต่สำหรับการใช้งานในทางทฤษฎีเป็นลำเอียงผลลัพธ์ในการมีเพียงอัลกอริธึมแบบสุ่มและในบางกรณีหายากบางคนอาจจะสำคัญกว่าจะสามารถคาดการณ์ได้มากกว่าที่จะทำได้อย่างรวดเร็ว ดังนั้นเราจะได้อัลกอริธึมแบบ linear กรณีเลวร้ายที่สุดเวลา เราจะอธิบายโซลูชันที่คิดค้นโดยคนห้าคนรายคือ Blum Capital Floyd แพร rivest และ tarjan .

quickselect จำได้ไหมว่าจะเลือกแบบสุ่ม"หมุน" x พาร์ติชันรายการที่เป็นส่วนประกอบน้อยกว่าและมากกว่า xและการโทรในตัวมันเอง'% s 'หนึ่งในสอง sublists ได้. แม้จะใช้วิธีทางเลือกรวดเร็วยิ่งขึ้นที่ผมสรุปไว้ทำอะไรสักอย่างคล้ายคลึงกันแต่จะเลือกหมุนที่อยู่ในทางที่มีความซับซ้อนด้วยการโทรติดต่อในตัวมันเอง(% s )ในตัวอย่างแบบสุ่มของอินพุต อัลกอริธึมรู้ของเราจะใช้ความคิดเดียวกันนี้ในการเลือก X โดยการโทรติดต่อการสอบถามแบบสอบถามซ้ำที่.

หากเราไม่สามารถทำได้อย่างรวดเร็วเป็นทางเลือกที่ดีก็จะเป็นการปล่อยให้ x จะอยู่ตรงกลางของค่าที่เลือก จากนั้นการโทรการสอบถามแบบสอบถามซ้ำแต่ละครั้งจะมีในส่วนย่อยของค่าที่ครึ่งเท่านั้น แต่แน่นอนว่าถ้าเรารู้ว่าจะได้พบกับเกาะกลางถนนที่เราก็จะทำการค้นหาเกาะกลางถนนจนเกินไปความหวังสำหรับ ปล่อยให้เป็นเพียงเพื่อทำให้บางสิ่งบางอย่างอยู่ใกล้กับเกาะกลางถนนที่(บอกว่า ภายใน n / 4 ตำแหน่งของมัน)จากนั้นการโทรการสอบถามแบบสอบถามซ้ำแต่ละครั้งจะมีเศษขนาดใหญ่ของอินพุต( 3 / 4 )แต่ในส่วนนี้ยังอาจจะดีพอ.

medians อยู่ตรงกลางของเราจะได้รับอะไรบางอย่างที่อยู่ใกล้กับเกาะกลางถนนที่เหมาะสมได้อย่างรวดเร็ว เหมือนกับ"ทางเลือกที่รวดเร็วกว่า"แทนที่จะออกไปหาที่เกาะกลางถนนในการตั้งค่าทั้งหมดที่พบกับเกาะกลางถนนที่ของตัวอย่าง ทำอย่างไรเราจะเลือกตัวอย่าง medians อีกครั้ง!

อัลกอริธึมเกาะกลางถนน - ของ - medians :

สายขึ้นส่วนในกลุ่มของห้า(หมายเลข 5 ซึ่งเป็นเรื่องที่สำคัญไม่ได้เป็นอย่างนั้นมันไม่ได้เช่น 7 โดยไม่มีการเปลี่ยนแปลงอัลกอริธึมที่มาก) การโทรแต่ละกลุ่ม: S [ i ]ด้วยผมตั้งแต่ 1 เพื่อไปยัง N / 5 .
พบอยู่ตรงกลางของแต่ละกลุ่ม (การโทรนี้ x [ i ]) รายการนี้จะใช้เวลาเดินทาง 6 การเปรียบเทียบต่อกลุ่มดังนั้น 6 N / 5 (เป็นเวลาตามแนวยาวเนื่องจากเรามีการ medians ในส่วนย่อยขนาดเล็กมาก)..
ค้นหาอยู่ตรงกลางของ X [ i ]การใช้สายเรียกการสอบถามแบบสอบถามซ้ำในอัลกอริธึมที่ หากเราเขียนซ้ำในที่ T ( N )เป็นเวลาที่จะเรียกใช้อัลกอริธึมที่อยู่ในรายการของรายการ n ขั้นตอนนี้จะใช้เวลา T ( N / 5 ) ปล่อยให้ม.เป็นเกาะกลางถนนนี้ของ medians .ม.
การใช้ไปยังพาร์ติชันที่ใส่และสายอัลกอริธึมที่(% s )บนหนึ่งในพาร์ติชันที่เหมือนใน quickselect .

เราจะพูดอะไรเกี่ยวกับจำนวนรายการรวมอยู่ในสายการสอบถามแบบสอบถามซ้ำครั้งล่าสุดนี้มันเป็นการง่ายที่จะพูดเกี่ยวกับเรื่องนี้ได้ในข้อกำหนดขององค์ประกอบที่อยู่ห่างออกไปในระยะทางโยน(ไม่รวมอยู่ในการโทรออก).

เราเสมอไม่ไกล L 3 อยู่ห่างออกไปใน(ค่าที่มากกว่าม.)หรือ L 1 (ค่าที่น้อยกว่าม.) คิดว่าเราทิ้งแคช L 3 .

ท่ามกลาง N / 5 ค่า X [ i ] N / 10 มีขนาดใหญ่กว่าม.(ตั้งแต่ม.ถูกกำหนดให้อยู่ตรงกลางของค่าเหล่านี้)

สำหรับผมแต่ละครั้งที่ x [ i ]มีขนาดใหญ่กว่าม.ทั้งสองค่าอื่นๆใน S [ i ]นอกจากนั้นยังมีขนาดใหญ่กว่า x [ i ](ตั้งแต่ x [ i ]จะอยู่ตรงกลางของ S [ i ]).

ดังนั้น L 3 ได้อย่างน้อย 3 ชิ้นในที่อย่างน้อย N / 10 กลุ่ม: S [ i ]สำหรับยอดรวมของที่อย่างน้อย 3 N / 10 องค์ประกอบแต่ละครั้ง โดยอาร์กิวเมนต์คีย์สมมาตร L 1 ได้อย่างน้อย 3 N / 10 องค์ประกอบ.

ดังนั้นการโทรการสอบถามแบบสอบถามซ้ำสุดท้ายที่อยู่ในรายชื่อของที่มากที่สุด 7 n / 10 องค์ประกอบและต้องใช้เวลาที่ T มากที่สุด( 7 / 10 ).

อัลกอริธึมโรงแรมแห่งนี้มีที่พักที่เราต้องการการสอบถามแบบสอบถามซ้ำว่ามีสายเรียกเข้าแต่ละเกี่ยวข้องกับเศษเท่านั้นคงที่ของอัลกอริธึม.

ซึ่งจะช่วยให้รู้ทางเลือกก่อนที่เราจะวิเคราะห์อัลกอริธึมของเราจะช่วยให้เขียนมันออกมามากขึ้นด้วยความเอาใจใส่ใน pseudocode นอกจากนั้นยังแทนการใช้อัลกอริธึมแบบพิเศษเพื่อไปพบกับเกาะกลางถนนในข้อย่อยแต่ละ: S [ i ]ปล่อยให้เป็นเพียงการเรียกใช้'% s 'ได้อีกครั้ง เพื่อป้องกันไม่ให้การสอบถามซ้ำแบบไม่มีขอบเขตเราต้องหยุดเมื่อ L มีขนาดเล็กที่มีไม่เพียงพอ x [ i ]ค่าเพื่อค้นหา medians ของ.

เลือก( L , K )

{หาก( L มีองค์ประกอบ 10 หรือน้อยกว่านั้น)สัญลักษณ์
{

เรียงลำดับ L กลับไปที่ส่วนใน kth ตำแหน่ง
}

พาร์ติชัน L ในส่วนย่อย: S [ i ]ของห้าส่วนประกอบแต่ละ
ตามมาตรฐาน(จะมี N / 5 ส่วนย่อยรวม)

สำหรับ( I = 1 เพื่อไปยัง N / 5 )ทำ
x [ i ]=เลือก( S [ i ], 3 )

M =เลือก({ x [ i ]}, N / 10 )

พาร์ติชัน L ใน L 1 < M , L 2 = M , L 3 >ม.
หาก( K <=ความยาว( L 1 ))
กลับไปเลือก( L 1 , K )
อื่นหาก( K >ความยาว( L 1 )ความยาว( L 2 ))
กลับไปเลือก(แคช L 3 , K - ความยาว( L 1 ) - ความยาว( L 2 ))

ตามมาตรฐานอื่นนอกเหนือจากนี้ให้กลับไปม.}


ซึ่งจะช่วยให้การวิเคราะห์จอมปลอม - รหัสข้างต้นทำให้เราที่หมายเลขของการเปรียบเทียบที่สามารถพบได้จากการแก้ปัญหาที่เกิด ซ้ำ

T ( N )= 12 N / 5 T ( N / 5 ) T ( 7 / 10 )

ที่ 12 N / 5 คำมาจากสองสถานที่:เราสามารถเรียงลำดับแต่ละชุด S [ i ]ด้วยเจ็ดการเปรียบเทียบ(การบ้าน 2.31 ),ดังนั้นขั้นตอนที่เราประมวลผลค่า X [ i ]จะใช้เวลาการเปรียบเทียบ 7 n / 5 ทั้งหมด และขั้นตอนที่เรา l พาร์ติชันใช้เวลา 1 การเปรียบเทียบมากขึ้น. สองเงื่อนไขอื่นๆที่มาจากสองสายการสอบถามแบบสอบถามซ้ำในที่ที่เราได้พบกับม.แล้วโดยรวมที่คืนค่า ในขณะที่เรามีประเด็นก่อนหน้าการโทรการสอบถามแบบสอบถามซ้ำที่สองอยู่ในรายชื่อของที่มากที่สุด 7 n / 10 องค์ประกอบดังนั้น T ( 7 / 10 )ที่ถูกมัดอยู่.

จริงๆแล้วด้วยความระมัดระวังมากขึ้นบางส่วนที่เราสามารถทำได้ดีที่เราไม่จำเป็นต้องเรียงชุด: S [ i ]เพียงได้พบกับ medians ของพวกเขาเท่านั้นซึ่งต้องใช้ 6 / 5 การเปรียบเทียบอย่างแท้จริง ข้อมูลที่ออกมาร่วมกันพร้อมด้วยมาตรวัดของม.ควรจะพอในการที่จะขจัด 3 N / 10 จากแอลดังนั้นเราจึงไม่สามารถรับการเกิดซ้ำที่พร้อมด้วย 6 N / 5 ใน 12 N / 5 ข้างต้นแล้วและบันทึกเป็นปัจจัยหนึ่งในสองในการเปรียบเทียบรวม. แต่นับตั้งแต่ส่งผลให้โรงแรมแห่งนี้เป็นของความสนใจในทางทฤษฎีผมมันในรูปแบบง่ายขึ้นและได้ง่ายขึ้นในการทำความเข้าใจที่อยู่เหนือ.

การเกิดซ้ำนี้มีลักษณะเหมือนกับหนึ่งมาจากอัลกอริธึมแบ่งและเอาชนะได้แต่สิ่งหนึ่งซึ่งเป็นปัญหาที่ส่วนความไม่เท่าเทียมกัน แต่ในกรณีนี้ความเป็นจริงที่สำคัญที่สุดคือส่วนที่เพิ่มขึ้นมาจะไม่น้อยกว่าทั้งหมดได้เมื่อเกิดเหตุการณ์นี้ไม่ได้เรื่องมากเท่าได้อย่างไรเท่ากับหรือไม่เท่าเทียมกันก็มี.

มีสองวิธีในการวิเคราะห์ปัญหาอย่างนี้ เป็นครั้งแรกที่เป็นวิธีการที่ผมแสดงให้เห็นสำหรับ quickselect ในซึ่งเราพยายามที่จะเป็นหลักฐานการเหนี่ยวนำสนามแม่เหล็กไฟฟ้าที่บางสิ่งบางอย่างคือ O ( N )โดยถือว่าของ CN สำหรับ C เฉพาะบางอย่างการขยายทางด้านขวาของการเกิดซ้ำได้และการทำงานผ่านทางคณิตศาสตร์ที่จะกำหนดว่าควรจะเป็น Cในกรณีที่เรา มี

T ( N )= 12 N / 5 T ( N / 5 ) T ( 7 / 10 )

= 12 N / 5 CN / 57 CN / 10

= N ( 12/5 9 c / 10 )

หากนี้เป็นที่มากที่สุด CN จึงทำให้เตาแม่เหล็กไฟฟ้าจะผ่านการตรวจสอบความถูกต้องที่เราต้องการความจริงที่ ว่า

N ( 12/5 9 c / 10 )<= CN

12/5 9 c / 10 <= C

12/5 <= C / 10

C <= 24

ที่บอกกับเราว่าเราสามารถพิสูจน์ได้ด้วยเตาแม่เหล็กไฟฟ้าที่ T ( N )= 24 N (หรือขนาดใหญ่อย่างต่อเนื่องครั้ง N )นอกจากนั้นเรายังจะต้องจัดการกับกรณีฐานที่แต่ว่าเป็นเรื่องง่ายๆ

วิธีที่สองในการวิเคราะห์การเกิดซ้ำที่เหมือนกับเป็นการทรีที่แสดงขนาดของปัญหาในการติดต่อการสอบถามแบบสอบถามซ้ำแต่ละครั้งและวิเคราะห์ขนาดของปัญหาในแต่ละชั้นของต้นไม้จำนวนรวมของการเปรียบเทียบสามารถพบได้จากการคูณขนาด subproblem ทั้งหมดนี้ได้โดยปัจจัย 12/5 ของการเปรียบเทียบต่อส่วนที่ในแต่ละสายแล้ว ที่จะเริ่มต้นด้วยรากปัญหาของขนาด N ,แล้วแต่ละโหนดได้สอง subproblems ,มีขนาด 1/5 ของแม่และที่อื่นๆมีขนาด 7/10 7/10 7/10 7/10 ของแม่.

n
/
N / 57 n / 10
//
N / 257 / 507 N / 5049 N / 100
////

ปัญหาแต่ละตัวในระดับหนึ่งจะถูกแทนที่ด้วยสองปัญหาในระดับถัดไปลงทุกขนาด 1/5 และ 7/10 7/10 7/10 7/10 หลัก ดังนั้นจึงมีขนาดรวมในระดับถัดไปคือ 1/5 7/10 7/10 7/10 7/10 = 9/10 ที่ก่อนหน้า(ในบางครั้งไม่น้อยเมื่อ subproblem มาถึงที่พักและไม่ได้ทำให้มากขึ้นการสอบถามแบบสอบถามซ้ำสาย)

ดังนั้นจำนวนของการเปรียบเทียบ เป็น

12/5 ( N 9 N / 1081 N / 100 ...)

= 12/5 N ( 1 9/10 ( 9/10 )
2 ( 9/10 )
3 ...)

= 12/5 N 1 /( 1 - ( 9/10 ))

= 24 n

เป็นกฎทั่วไป,ที่รูปทรงเรขาคณิต Series จำนวนเงิน( x
ฉัน)(สำหรับผม 0 เพื่อไปยัง n - 1 )ช่วยแก้ปัญหา( 1 - x
N )/( 1 - X ),และทุกครั้งจะน้อยกว่า x 1 ที่จำกัดของจำนวนเงินเป็น n ไปคัดสรรมาจะกลายเป็น 1 /( 1 - x ). จำนวนเงินที่สูงกว่าเป็นเพียงกรณีของสูตรนี้ที่ X = 9/10 วิธีทรี - ขยายตัวเดียวกันแล้วแสดงให้เห็นว่าโดยทั่วไปหาก T ( N )= CN T () T ( bn ,),ที่ 1 b <รวมเวลาคือ C ( 1 /( 1 - A - B ) N .

เรารู้การเลือกอัลกอริธึมที่ใช้มากที่สุด 24 N การเปรียบเทียบและนำ O ( N )เวลา.

พร้อมด้วยของใช้งานได้ครั้งเดียวสามารถลดจำนวนการเปรียบเทียบกับ 2.95 n [ดู D .ทดและสหรัฐอเมริกา zwick ,"การเลือกที่อยู่ตรงกลาง",โซดา 6 , 1995 ]ซึ่งเป็นเพียงเล็กน้อยไม่น้อยกว่าสองเท่าการเลือกแบบสุ่ม,แต่โดยส่วนมากความซับซ้อนมากขึ้นและไม่ได้.