CoE KKU

เวลาสำหรับกรณี worst case คือ $\Theta(M A(M, N))$ (โดย M ≥ N), เมื่อ $A(M, N)$ คือ functional inverse ของ Ackerman's function, ซึ่งมีนิยามดังนี้

$$A(1, j) = 2j for j ≥ 1$$ $$A(i, 1) = A(i - 1, 2) for i ≥ 2$$ $$A(i, j) = A(i - 1, A(i, j - 1)) for i, j ≥ 2$$

และกำหนดนิยามดังนี้

$$\alpha(M, N) = min{ i ≥ 1 : A( i, ⌊M / N⌋ ) > log\ N } $$

ในทางปฏิบัติแล้วค่าที่มีความสำคัญ คือ ค่าที่ $\alpha(M, N) ≤ 4$ ฟังก์ชัน $F(N) = A(2, N)$ เรียกว่า single-variable Ackerman's function และบางครั้งฟังก์ชัน single variable inverse Ackerman ก็เขียนอยู่ในรูป $log^*\ N$ ซึ่งก็คือ จำนวนครั้งที่ต้องใช้ log กับ N ไปจนกระทั่ง N ≤ 1 เช่น $log^* 65536 = 4$ เนื่องจาก $log\ log\ log\ log\ 65536 = 1$ และ $log^* 2^{65536} = 5$ ความจริงแล้ว $\alpha(M, N)$ โตช้ากว่า $log^*\ N$ เช่นเราจะเห็นว่า $A(3, 1) = A(2, 2) = 2^{2^2} = 16$ ดังนั้นสำหรับ N < 216 = 65536 นั้น $\alpha(M, N) ≤ 3$ แต่ $\alpha(M, N)$ ก็ไม่ได้เป็นค่าคงที่ เมื่อ M มีค่ามากกว่า N เล็กน้อย ดังนั้น running time จึงไม่ได้เป็น linear อย่างไรก็ตามถ้าหากว่า $M = N\ log^*\ N$ แล้ว $\alpha(M, N)$ จะมีค่าสูงสุดคือ 2 ดังนั้น ตราบเท่าที่ M มีค่ามากกว่าค่า linear เล็กน้อยแล้ว running time ก็จะเป็น linear ของ M

ในหัวข้อนี้จะกล่าวถึงขอบเขตของ running time ของลำดับการทำงานของ union/find จำนวน M การทำงานที่ $M = \Omega(N)$ โดยที่ unions และ finds อาจมีลำดับอย่างไรก็ได้ แต่ต้องเป็นการทำงานเป็น unions by rank และการทำงาน finds ที่มี path compression

เราจะเริ่มด้วย lemma ที่เกี่ยวข้องกับจำนวนโนดของทรีที่มี rank r เนื่องด้วยจากกฎของ union-by-rank นั้นจะทำให้มีโนดที่มี rank ขนาดเล็กในจำนวนมากกว่าโนดที่ rank ขนาดใหญ่ โดยเฉพาะอย่างยิ่งโนดที่มี rank เป็น $log\ N$ มีได้เพียงโนดเดียว สิ่งที่จะแสดงคือขอบเขตที่แน่ชัดที่สุดเท่าที่จะเป็นไปได้ของจำนวนโนดของ rank r ใด ๆ และเนื่องจากจะเกิดการเปลี่ยนแปลงของ rank ขึ้นได้ก็ต่อเมื่อมีการทำงาน unions (และคือ เมื่อทรี 2 ทรีมี rank เท่ากัน) ดังนั้นเราจึงสามารถหาขอบเขตนี้ได้โดยไม่ต้องสนใจเรื่อง path compression

LEMMA 8.1. เมื่อมีการทำงานของ union ต่อเนื่องกันแล้ว โนดใดๆ ที่มี rank r ต้องมีโนดลูก (descendants) อย่างน้อยที่สุดจำนวน $2^r$ โนด (รวมตัวมันเอง)

PROOF: โดยวิธี induction, Basis, r = 0, เป็นจริงชัดเจน

ให้ T เป็นทรีมี rank r ที่มีจำนวนโนดลูก (descendants) น้อยที่สุด และให้ X เป็นรากของ T สมมุติให้การทำงาน union ครั้งสุดท้ายที่มี X เกี่ยวข้องด้วยนั้นเป็นการเกิดขึ้นระหว่าง T1 และ T2 และให้ X เป็นรากของ T1 เดิม

ถ้า T1 เดิมมี rank r, ดังนั้น T1 จึงเป็นทรีที่มีความสูง (height) r และมีโนดลูกน้อยกว่าของ T ซึ่งจะขัดแย้งกับ assumption ที่ว่า T เป็นทรีที่มีจำนวนโนดลูกที่น้อยที่สุด ดังนั้น rank ของ T1 ≤ r – 1 และ rank ของ T2 ≤ rank of T1 เนื่องจาก T มี rank r และ rank จะสามารถเพิ่มขึ้นได้ด้วย T2 เท่านั้น นั่นคือ rank ของ T2 = r – 1 และ rank ของ T1 = r – 1 ดังนั้นด้วย induction hypothesis, แต่ละทรีจึงมีอย่างโนดลูกอย่างน้อย $2^{r–1}$ โนดทำให้ได้จำนวนทั้งสิ้นเป็น $2^r$

จาก Lemma 8.1 จะเห็นว่ากรณีที่ไม่มีการทำงานของ path compression แล้วจำนวนโนดของทรี rank r จะต้องมีโนดลูกอย่างน้อย $2^r$ โนด การทำงานของ path compression จะเปลี่ยนแปลงสิ่งนี้เนื่องจากมันจะขจัดโนด descendants ออกไปจากโนดได้ อย่างไรก็ตาม ในการทำงาน unions ที่ถึงแม้จะมีการใช้ path compression ก็ตาม เราใช้ ranks เสมือนหนึ่งไม่มีการใช้ path compression ดังนั้น เมื่อกำหนดขอบเขตของโนดของ rank r เราจึงละเลยเรื่องของ path compression

LEMMA 8.2. จำนวนโนดของ rank r มีมากที่สุด $N/2^r$

PROOF: เมื่อไม่มี path compression แต่ละโนดของ rank r คือรากของทรีย่อยที่มีโนดอย่างน้อย $2^r$ โนด ไม่มีโนดใด ๆ ในทรีย่อยที่จะมี rank r ได้ ดังนั้นทรีย่อยทั้งหมดของโนดของ rank r ทั้งหมดจึงเป็น disjoint กัน นั่นคือมีจำนวนทรีย่อยที่เป็น disjoint ได้มากที่สุดคือ $N/2^r$ ทรีย่อย และนั่นคือ $N/2^r$ โนดของ rank r นั่นเอง

LEMMA 8.3. ที่เวลาหนึ่งในระหว่างการทำงาน union/find algorithm นั้น ranks ของโนดในเส้นทางจาก leaf ไปยังรากจะเพิ่มขึ้นแบบ monotonically

PROOF: lemma นี้เป็นจริงถ้าไม่มี path compression (ดูตัวอย่าง). หลังจากมีการทำ path compression แล้วจะมีบางโนด v เป็นโนดต่อจาก w ซึ่ง v เป็นโนดต่อจาก w ก็ต่อเมื่อมี unions กันเท่านั้น ดังนั้น rank ของ v จึงน้อยกว่า rank ของ w

สรูปผลดังนี้ Lemma 8.2 บอกให้รู้ว่ามีจำนวนกี่โนดที่สามารถกำหนดเป็น rank r ได้ เนื่องจากการกำหนด ranks ทำได้ด้วยการ unions ซึ่งไม่มีเรื่องของ path compression เข้ามาเกี่ยวข้อง Lemma 8.2 เป็นจริงในทุกขั้นตอนระหว่างการทำงานของ union/find algorithm รูปที่ 8.16 แสดงสภาวะที่มีโนดจำนวนมากที่มี ranks 0 และ 1 และจำนวนโนดจะมีน้อยกว่าสำหรับ rank r ที่เมื่อ r มีขนาดใหญ่ขึ้น Lemma 8.3 แสดงถึงการกระจายของโนด ซึ่งเห็นได้ว่า rank ของโนดเพิ่มขึ้นเฉพาะตามเส้นทางจาก leaf ไปยังราก

จากนี้จะกล่าวถึงทฤษฎีหลัก แนวคิดพื้นฐานคือ การทำงาน find ที่ทำกับโนด v ใด ๆ ใช้เวลาผันแปรตามจำนวนโนดในเส้นทางจาก v ไปยังราก ถ้าให้ต้องเสียเวลาเป็นหนึ่งหน่วยเวลาสำหรับแต่ละโนดตามเส้นทางจาก v ไปยังรากสำหรับแต่ละการทำงาน find เพื่อช่วยในการนับค่าใช้จ่ายการทำงาน เราสมมติให้สะสม 1 เพนนีสำหรับโนด 1 โนดตามเส้นทาง เมื่อจบการทำงานของอัลกอริทึม จำนวนเงินทั้งหมดที่สะสมก็คือค่าใช้จ่ายทั้งหมด

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

เราจะแบ่งโนดออกตามค่าของ rank ของมันจากนั้นก็จะแบ่ง ranks ออกเป็น rank group ในการทำงาน find แต่ละครั้งเราจะสะสมเงินเหรียญอเมริกันจำนวนหนึ่งลงในกล่องเก็บเงินทั่วไปและเงินเหรียญแคนนาดาจำนวนหนึ่งลงในโนดที่เฉพาะเจาะจงเอาไว้แล้ว ในการคำนวณจำนวนเหรียญแคนนาดาที่สะสมไว้ทั้งหมดเราจะต้องคำนวณหาจำนวนเหรียญที่เก็บสะสมในแต่ละโนด และด้วยการรวมจำนวนเหรียญทั้งหมดในโนดที่มีค่า rank r เดียวกันก็จะได้จำนวนที่สะสมทั้งหมดต่อ rank ของ rank จากนั้นก็จะรวมจำนวนที่สะสมทั้งหมดของแต่ละ rank r ที่อยู่ใน rank group g เดียวกัน ซึ่งจะได้จำนวนสะสมของแต่ละ rank group g สุดท้ายจะทำการรวมจำนวนที่สะสมในแต่ละ rank group g ซึ่งจะได้เป็นจำนวนเหรียญแคนนาดาทั้งหมดที่สะสมได้ใน forest นั้น และรวมจำนวนที่ได้นี้เข้ากับจำนวนเหรียญอเมริกันที่อยู่ในกล่องเก็บเงินทั่วไปก็จะได้เป็นคำตอบที่เราต้องการ

เราจะแบ่งแยก ranks ออกเป็น group โดยโนดที่มี rank r จะถูกจัดเข้าอยู่ในกลุ่ม $G(r)$ และจะกำหนด G ในภายหลัง rank ที่มีขนาดใหญ่ที่สุดที่อยู่ใน rank group g คือ $F(g)$ เมื่อ $F = G – 1$ เป็น inverse ของ $G$ ดังนั้นจำนวนของ ranks ใน rank group g ใด ๆ ที่ g > 0 ก็คือ $F(g) – F(g – 1)$ และจะเห็นได้ว่าค่าขอบเขตบนโดยประมาณของ rank group ที่ใหญ่ที่สุดก็คือ $G(N)$ ตัวอย่างเช่น สมมติเราแบ่งแยก ranks ดังแสดงในรูปที่ 8.17 ก็จะได้ว่า $G(r)=⌈√r⌉$ และ rank ที่มีขนาดใหญ่ที่สุดใน group g คือ $F(g)=g^2$ อีกทั้ง group g ที่ g > 0 จะมี rank อยู่ตั้งแต่ $F(g – 1) + 1$ ถึง $F(g)$ ที่กล่าวมานี้ใช้ไม่ได้กับ rank group 0 ดังนั้นเพื่อความสะดวกเราจะกำหนดให้ rank group 0 มีเฉพาะสมาชิกที่มี rank 0 เท่านั้น จะเห็นว่า groups ต่าง ๆ นั้นเกิดจาก rank ที่มีขนาดเรียงลำดับกันไป

รูปที่ 8.17 รูปแบบหนึ่งของการแบ่งแยก ranks ออกเป็น groups

เวลาที่ใช้ในการทำงานของแต่ละ find(i) จะแปรผันตามจำนวนโนดบนเส้นทางจากโนดที่เป็นตัวแทนของ i ขึ้นไปถึงโนดราก ดังนั้นเราจะสะสมเงินหนึ่งเพนนีสำหรับแต่ละโนดบนเส้นทางนั้น โดยมีการกำหนดวิธีการสะสมให้เหมาะสมกับการใช้ประโยชน์จาก path compression ด้วย โดยถ้า v เป็นโนดบนเส้นทางดังกล่าวนี้แล้ว

1. ถ้า v เป็นโนดราก หรือถ้าโนดแม่ของ v เป็นโนดราก หรือโนดแม่ของ v อยู่ใน rank group คนละ rank group กับโนด v เราจะสะสมเงินเพนนีอเมริกัน 1 เพนนีลงในกล่องเก็บเงินทั่วไป
2. มิฉะนั้นเราก็จะเก็บเงินเพนนีแคนนาดาไวในโนดนั้น 1 เพนนี

LEMMA 8.4
สำหรับการทำงาน find(v) ใด ๆ ก็ตาม จำนวนเพนนีทั้งหมดที่สะสมได้ไม่ว่าจะในกล่องเก็บเงินทั่วไปหรือในโนดจะเท่ากับจำนวนโนดบนเส้นทางจาก v ไปยังโนดราก
PROOF: Obvious.

ดังนั้นสิ่งที่เราต้องทำก็คือการรวมเงินอเมริกันเพนนีทั้งหมดที่สะสมภายใต้เงื่อนไขข้อที่ 1 ข้างบนเข้ากับเพนนีแคนนาดาทั้งหมด ที่สะสมตามเงื่อนไขข้อ 2 ข้างบน

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

LEMMA 8.5
ตลอดการทำงานของอัลกอริทึม จำนวนเงินอเมริกันเพนนีทั้งหมดที่สะสมได้ตามเงื่อนไขข้อ 1 ข้างบนมีจำนวนมากที่สุดเป็น $M(G(N) + 2)$
PROOF:
ในการทำงานแต่ละ find จะมีการสะสมเงินอเมริกันเพนนีในจำนวนที่มากที่สุดได้ 2 เพนนี เนื่องจากโนดรากและโนดลูกของมัน จาก Lemma 8.3 ค่า ranks ของโนดในเส้นทางขึ้นไปยังรากจะเพิ่มขึ้นแบบ monotonically และเนื่องจากมีจำนวน rank group มากที่สุดได้ $G(N)$ rank groups หมายความว่าก็จะมีโนดอื่น ๆ จำนวนเพียง $G(N)$ โนดเท่านั้นที่อยู่ในเส้นทางที่สามารถเป็นไปตามเงื่อนไขการสะสมเงินข้อ 1 ข้างบนสำหรับการทำงาน find หนึ่ง ๆ ดังนั้นระหว่างการทำงาน find ใด ๆ หนึ่งจะสามารถสะสมเหรียญอเมริกันเพนนีลงในกล่องเก็บเงินทั่วไปได้เป็นจำนวน $G(N) + 2$ เพนนี นั่นคือภายใต้การทำงาน find เป็นจำนวน M ครั้งต่อเนื่องกันจึงสามารถเก็บสะสมเหรียญอเมริกันเพนนีตามเงื่อนไขการสะสมข้อ 1 ได้ทั้งสิ้นมากที่สุดคือ $M(G(N) + 2)$ เพนนี

เพื่อให้การประมาณการที่ดีสำหรับเหรียญแคนนาดาที่สะสมภายใต้เงื่อนไขการสะสมข้อ 2 เราจะทำการรวมเหรียญที่สะสมตามโนดแทนที่จะรวมตามการทำงานของ find ถ้ามีเหรียญสะสมในโนด v ตามเงื่อนไขการสะสมข้อ 2 โนด v ก็จะได้รับการเคลื่อนย้ายด้วย path compression และมันจะมีโนดแม่ใหม่ที่มี rank สูงกว่าโนดแม่เดิม ดังนั้น โนด v ที่อยู่ใน rank group g ที่ g > 0 จึงสามารถมีการเคลื่อนย้ายได้มากที่สุดไม่เกิน F(g) – F(g – 1) ครั้งก่อนที่โนดแม่ของมันจะถูกดันให้ออกจาก rank group g เนื่องจากนั่นเป็นขนาดของ rank group นั้น หลังจากนี้แล้วค่าใช้จ่ายที่เกิดขึ้นที่โนด v ก็จะเป็นการสะสมเหรียญตามเงื่อนไขการสะสมข้อ 2 ทั้งสิ้น

LEMMA 8.6
จำนวนโนด $V(g)$ ใน rank group g > 0 มีจำนวนสูงสุดไม่เกิน $N/2^{F(g – 1)}$
PROOF:
จาก Lemma 8.2 จำนวนโนดสูงสุดที่มีได้ของ rank r คือ $N/2^r$ รวมทุก ranks ใน group g จะได้ดังนี้
\begin{align*} V(g) & ≤ ∑_{r=F(g-1)+1}^{F(g)} N/2^r \\ & ≤ ∑_{r=F(g-1)+1}^∞ N/2^r \\ & ≤ N∑_{r=F(g-1)+1}^∞ 1/2^r \\ & ≤ \frac{N}{2^{F(g-1)+1}} ∑_{s=0}^∞ 1/2^s \\ & ≤ \frac{2N}{2^{F(g-1)+1}} \\ & ≤ \frac{N}{2^{F(g-1)}} \end{align*}

LEMMA 8.7
จำนวนเหรียญแคนนาดาเพนนีสูงสุดที่สะสมอยู่ในโนดทั้งหมดใน rank group g มีได้ไม่เกิน $NF(g)/2^{F(g – 1)}$
PROOF:
โนดแต่ละโนดใน rank group หนึ่ง ๆ สามารถได้รับเหรียญแคนนาดาเพนนีสูงสุดไม่เกิน $F(g) – F(g – 1) ≤ F(g)$ ในขณะที่โนดแม่ของมันยังคงอยู่ใน rank group ของมัน และ Lemma 8.6 จะบอกได้ว่ามีจำนวนโนดอยู่เท่าไหร่ (ผลลัพธ์ได้จากการคูณกันของ Lemma 8.5 และ Lemma 8.6)

LEMMA 8.8
จำนวนเหรียญแคนนาดาเพนนีที่สะสมได้ภายใต้เงื่อนไขการสะสมข้อ 2 มีมากที่สุดไม่เกิน $N∑_{g=1}^{G(N)} F(g)/2^{F(g-1)}$ เพนนี
PROOF:
เนื่องจาก rank group 0 มีสมาชิกที่มี rank 0 เท่านั้น มันจึงไม่เกี่ยวข้องกับการสะสมตามเงื่อนไขการสะสมข้อ 2 (มันไม่สามารถมีโนดแม่ที่อยู่ใน rank group เดียวกันได้) ดังนั้นขอบเขตของมันจึงได้จากการรวมกันของ rank group อื่น ๆ

ดังนั้นจากการสะสมเหรียญตามเงื่อนไขการสะสมข้อ 1 และ 2 รวมกันจะได้

$$ M(G(N)+2)+N∑_{g=1}^{G(N)} (F(g))/2^{F(g-1)} \tag{8.1}$$

สิ่งที่จะต้องพิจารณาต่อไปคือการระบุค่าของ $G(N)$ และ inverse ของมันคือ $F(N)$ ดูจะสมเหตุสมผลที่เราจะเลือก $G(N)$ เพื่อให้ขอบเขตที่ระบุข้างบนนี้มีค่าน้อยที่สุด อย่างไรก็ตามถ้า $G(N)$ มีค่าน้อยมากเกินไปก็จะทำให้ $F(N)$ มีค่าใหญ่มากซึ่งทำให้ขอบเขตที่ได้แย่ลงไป ดูเหมือนทางเลือกที่ดีสำหรับการเลือกคือ เลือกให้ $F(i)$ เป็น recursive function ที่มีนิยามคือ $F(0) = 0$ และ $F(i) = 2^{F(i – 1)}$ ซึ่งจะทำให้ได้ $G(N)=1+⌊log^*\ N⌋$ รูปที่ 8.18 แสดงการแบ่งแยก ranks ที่ได้นี้ จะเห็นว่า group 0 มีเฉพาะ rank 0 เท่านั้นตามที่ต้องการใน Lemma 8.7 ฟังก์ชัน F คล้ายกับ single-variable Ackerman function คือต่างกันที่นิยามของกรณี base case $(F(0) = 1)$

Theorem 8.1

Running time ของการทำงาน unions and finds เป็นจำนวน M ครั้ง คือ $O(M\ log^*\ N)$

Proof: แทนค่าตามนิยามของ F และ G ลงในสมการ (8.1) จำนวนอเมริกันเพนนีทั้งสิ้นคือ $O(MG(N)) = O(M\ log^*\ N)$ จำนวนแคนนาดาเพนนีทั้งสิ้นคือ $$N∑_{g=1}^{G(N)} (F(g))/2^{F(g-1)} = N∑_{g=1}^{G(N)} 1= NG(N) = O(N\ log^*\ N)$$ เนื่องจาก $M = \Omega(N)$

รูปที่ 8.18 รูปแบบการแบ่งแยก ranks ออกเป็น groups