ผลต่างระหว่างรุ่นของ "204512-53/lecture3"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 1: แถว 1:
 +
{{หัวคำบรรยาย|204512-53}}
 +
'''จดบันทึกคำบรรยายโดย:'''
 +
:<table border='0'>
 +
<tr><td>นายดลวัฒน์ งามภักดิ์</td><td>5314550075</td></tr>
 +
<tr><td>นายณรงค์ศักดิ์ ทิพย์จ้อย</td><td>5314552230</td></tr>
 +
<tr><td>นายปริตร หมึ่นคง</td><td>5314552248</td></tr>
 +
</table>
 +
 
=Red-Black Tree (Cont.)=
 
=Red-Black Tree (Cont.)=
  

รุ่นแก้ไขเมื่อ 13:47, 12 สิงหาคม 2553

บันทึกคำบรรยายวิชา 204512-53 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย:

นายดลวัฒน์ งามภักดิ์5314550075
นายณรงค์ศักดิ์ ทิพย์จ้อย5314552230
นายปริตร หมึ่นคง5314552248

Red-Black Tree (Cont.)

  • Tree ใดๆ จะเป็น Red-Black Tree ได้ต้องมีคุณสมบัติ 5 ข้อ ได้แก่
  1. โหนดเป็นได้ 2 สี คือ แดง กับ ดำ
  2. Root ต้องเป็นสีดำ
  3. Leaf ทั้งหมดต้องเป็นสีดำ
  4. โหนดสีแดงมีโหนดลูกเป็นสีดำ ทั้ง 2 โหนด
  5. จากโหนดใดๆ ไปหา Leaf ที่เป็นลูกหลานของตัวเอง จะต้องมีจำนวนโหนดสีดำเท่ากันหมด

ความสูงของ Red-Black Tree เป็น O(log n)

วิธีแก้ปัญหา เมื่อเพิ่ม Leaf Node เข้าไปใหม่ที่จุดใดจุดหนึ่ง ใน Leaf Node ที่เพิ่มเข้าไปใหม่ เราต้องทำการปรับสมดุลใหม่ โดยการตรวจสอบแล้วเปลี่ยนสีในบางจุดที่ต้องเปลี่ยนให้ตรงกับคุณสมบัติของ Red-Black Tree ทั้ง 5 ข้อไปเรื่อยๆ ไล่ตั้งแต่ Leaf Node ที่ได้ทำการเพิ่มเข้ามาขึ้นไปจนถึง Root

Divide and Conqure

เป็นยุทธศาสตร์ในการแก้ปัญหาด้วยอัลกอริทึมแบบหนึ่ง เช่น ถ้าต้องการหาข้อมูลอันหนึ่ง ให้จิ้มไปที่จุดกึ่งกลาง ถ้าเจอคำตอบก็จบ แต่ถ้าไม่เจอ เราก็เลือกว่าควรจะไปทางมากกว่าหรือน้อยกว่า (เนื่องจาก Binary Search นั้น ข้อมูลได้มีการเรียงกันก่อนอยู่แล้ว)

Concept – ตีเมืองใหญ่ให้เป็นเมืองเล็กก่อน

Review Merge Sort

  1. จิ้มไปที่กิ่งกลางจะได้ array 2 ส่วน คือ Array Aขนาด n และ Array B ขนาด m
  2. ซึ่ง array แต่ละส่วนจะทำการ Sort ใน Array ของตัวเอง เรียกว่า Merge Sort
  3. หลังจากนั้นทำการ เปรียบค่าแต่ละค่า ในแต่ละ Index ระหว่าง array ได้ค่าไหนที่น้อยกว่าก็ทำการ Add เข้าไปใน array ใหม่ ชื่อว่า C และทำไปเรื่อยๆ จนครบ เรียกว่า การ Merge

Merge Sort cr.png

Algorithm

  เราจะได้อัลกอริทึมในการ Merge โดยให้ k=0, i=1, j=1
  1. While k < n+m 
  2.	 k  k+1
  3.	if A[i] < B[j]
  4.		C[k]  A[i]
  5.		i i+1
  6.	else
  7.		C[k]  B[j]
  8.		j  j+1

Proof

 เราจะพิสูจน์ว่าอัลกอริทึมข้างบนถูกต้อง โดย
  *ถ้า array A เรียงจากน้อยไปหามาก และ
  *ถ้า array B เรียงจากน้อยไปหามาก แล้ว
  *Array C จะเป็น array ที่มาจาก array A และ array B ที่เรียงจากน้อยไปหามาก

Loop Invariants

จาก C[1…k] มีข้อมูลของ A[1…i+1] และ B[1…j-1] และเรียงลำดับ

Loop invariant cr1.png

จะพิสูจน์ว่า array ชุดใหม่ มาจาก


Loop invariant cr2.png

จะได้ว่า Z เป็นค่าใหญ่ที่สุดใน array Aที่ตำแหน่ง i แต่ปัญหาอยู่ที่จะทำอย่างไรให้เห็นว่า Z มีค่ามากที่สุดใน array B ในตำแหน่ง j

Loop invariant cr3.png

จากรูปข้างบนแสดงให้เห็นว่า เงื่อนไขใน Loop Invariants ยังไม่แข็งแกร่งพอ โดยจะเพิ่มเงื่อนไขใหม่ได้เป็น จาก C[1…k] มีข้อมูลของ A[1…i+1] และ B[1…j-1] และเรียงลำดับ (เพิ่ม และข้อมูลทุกตัวใน C[1…k] น้อยกว่าหรือเท่ากับ A[i] และ B[j]

Trick หากเงื่อนไขของ Loop Invariants แรกยังไม่แข็งแกร่งพอ ก็ให้หาเงื่อนไขเพิ่มเติมที่รัดกุมกว่าเดิมใส่เข้าไปจนกว่าจะพิสูจน์ได้ ทำให้ได้ว่าอัลกอริทึมนี้ จะได้ Big O = O(m+n) ซึ่งวนลูปทั้งหมด m+n รอบ ซึ่งหลักๆแล้วเราจะดูที่เวลาการทำงานมากกว่า

Merge Sort Algorithm

  Merge Sort(A) ให้  n = ขนาดของ A                       ใช้เวลา T(n)
  A(left)  A[1…(n/2)]          	                          ใช้เวลา O(n)
  A(right)  A[(n+1)/2 …n] 			          ใช้เวลา O(n)
  
  Assume ว่า n เป็นกำลังของ 2
  
  S(left)  Merge Sort(A(left))	                	  ใช้เวลา T(n/2)
  S(right)  Merge Sort(A(right))		          ใช้เวลา T(n/2)
  S  Merge Sort(S(left), S(right))		          ใช้เวลา O(n)
  Return S
   ให้ T(n) เป็นเวลาการทำงานที่แย่ที่สุด เมื่อ input ขนาด n โดยที่ O(n)+O(n) = O(n) ดังนั้น จะได้ T(n) = 2T(n/2) + O(n)

ปัญหาอยู่ที่อัลกอริทึมนี้ยังผิดอยู่ เพราะเนื่องจากยังไม่มี Base Case จึงไม่รู้ว่าจะต้องเริ่มทำ Loop เมื่อไร โดยในที่นี้ จะให้ Base Case เป็น T(1) = O(1) และให้ T(n) เป็น recurrence แต่เนื่องจาก O(n)+O(n)=O(n) นั้น ค่าคงที่บางส่วนจะหายไป ดังนั้นจึงเปลี่ยน T(n) ใหม่เป็น T(n) <= 2T(n/2) +Cn

Review Quick Sort

 Quick sort cr1.jpg

เมื่อแยกตัว pivotแล้ว จะได้

 Quick sort cr2.jpg

เมื่อทำการ Quick Sort แล้ว จะได้

 Quick sort cr3.jpg

ต่างจาก Merge Sort ตรงที่ Merge Sort จะเริ่มจากจุดกึ่งกลาง แต่ Quick Sort จะต้องเริ่มหาตัว pivot ก่อน

 Quick sort cr4.jpg
 จะใช้เวลา T(n) = O(n) + T(k) + T(n-k-1) โดยที่ในกรณีที่แย่ที่สุดนั้น จะได้ T(n) = O(n) + T(n-1)

การหาค่า pivot จะง่าย ก็ต่อเมื่อตัว pivot อยู่ตรงกลาง ซึ่งเราจะใช้วิธี Selection หาค่า Median

Selection

ให้ข้อมูล x1, x2, x3, … , xn และจำนวนเต็ม k ให้หาข้อมูลตัวที่น้อยที่สุด เป็นอันดับที่ k
ได้เวลา O(n log n) โดยใช้การ Merge Sort และหยิบตัวที่ k ซึ่งหากต้องการทำให้ได้ O(n) จะใช้การ Quick Selection

การ Quick Selection

ใช้เวลาเลือกตัว Pivot = O(x) Quick selection cr1.jpg

ใช้เวลาตรวจสอบว่าอยู่ฝั่งซ้ายหรือขวา = O(n) Quick selection cr2.jpg

จะได้ว่า T(n) = O(x) + O(n) + T(n/2) เมื่อ T(n/2) เป็นเวลาที่ใช้ในการ recursive ฝั่งใดฝั่งหนึ่ง

  ดังนั้น เมื่อ 		T(1)  = 1
 			T(n)  = Cn + ((Cn/2) + T(n/4))
 			        = Cn + (Cn/2) + (Cn/4) + T(n/8)
 			        <= Cn[1+(1/2)+(1/4)+(1/8)+…]
  
  ซึ่ง [1+(1/2)+(1/4)+(1/8)+…] มีค่าได้ไม่เกิน 2
  ดังนั้น			           <= 2Cn	= O(n)

จากตัวอย่างนี้ โชคดีตรงที่ว่า ได้ค่าตรงกลางพอดี แต่ถ้าหากแบ่งได้ 1/10 แล้ว จะได้ใหม่ว่า

  			 T(1) = 1
  			 T(n) = Cn + T(9n/10)
  			        = Cn + (Cn(9/10) + T(n(9/10)^2))
  			        = Cn + Cn(9/10) + Cn(9/10)^2 + T(n(9/10)^3)
 			        <= 2Cn	= O(n)


Finding medians in linear time

เป็นอีกอัลกอริทึมหนึ่งสำหรับหาค่ากลางเหมือนกัน

  • ในแต่ละแถว Sort ใช้เวลา C1
  • เนื่องจากมี n/5 แถว จึงใช้เวลา ((C1*n)/5)
  • หลัง Sort แล้วเอาข้อมูลตรงแถวกลางมาเป็นค่า Median
  Finding median in linear time cr.jpg

algorithm

Select cr1.jpg

   ดังนั้น ใช้เวลาทั้งหมด T(n) = Cn + T(n/5) + T(max(l, n-l))

จาก Select cr2.jpg

ค่า Medium ที่เราได้ จะมากกว่าสมาชิกในช่องที่ 1 จำนวณ n/4 ตัว และจะน้อยกว่าช่อง 2 จำนวน n/4 ตัว ดังนั้น T(n) <= Cn + T(n/5) + T(3n/4)

Conclusion

 Base Case: 		T(1) = 1
 Merge Sort: 		T(n) = Cn + 2T(n/2)
 Quick Sort:		T(n) = Cn + T(1) + T(n-1)
 		        	        <= Cn + T(n-1)
 Selection:		T(n) <= Cn + T(n/5) + T(3n/4)
 Binary Search:		T(n) = 1+ T(n/2)

Polynomial Multiplication

จาก Polynomial: 
f(x) = a0x^0 + a1x^1 + a2x^2 + … + a(n-1)x^(n-1)
g(x) = b0x^0 + b1x^1 + b2x^2 + … + b(n-1)x^(n-1)

หากนำ polynomial ทั้งสองมาคูณกันแล้วใช้ Divide and conquer จะได้

Array.JPG
	f(x) = x^((n-1)/2)A(x) + B(x)
	g(x) = x^(n/2)C(x) + D(x)
ดังนั้น f(x) * g(x) = x^n A(x)B(x) + x^(n/2) [A(x)D(x)+C(x)D(x)] + B(x)D(x)
ดังนั้น T(n) = 4T(n/2) + Cn

จะอธิบายโดยรูปได้ว่า

Polynomial Multiplication cr1.jpg

แต่ปัญหาของการใช้ Divide and Conqure ก็คือ ถึงแม้แต่ละชั้นจะใช้ O(n) ก็ตาม แต่ชั้นสุดท้ายมีลูกมากเกินไป จึงได้ค่าออกมาเป็น O(n^2) = 2^(log n) Cn

Polynomial Multiplication cr2.jpg

ดังนั้น จะได้ O(n log n)

Polynomial Multiplication cr3.jpg

ดังนั้น จะได้ O(n)