ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 1"
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 5: | แถว 5: | ||
วัตถุ ที่เราต้องทำการตรวจสอบในข้อนี้คือ ตัวเลข 1,2,3,... (หรือ index ของอะเรย์นั่นเอง) ซึ่ง ค่า <math> n \, </math> จะเป็นค่าที่อยู่ในช่วงดังกล่าว และมีเงื่อนไขคือ A[0]ถึง A[n]มีค่าเป็นศูนย์ และ A[n+1] เป็นต้นไปมีค่าเป็นหนึ่ง (เขียนสั้น ๆ คือ A[n]=0 และ A[n+1]=1) แต่โจทย์ต้องการให้เวลาในการหาค่า <math> n \, </math> ดังกล่าวเป็น <math>O(\log n) \,</math> จากการตัวอย่างการค้นหาในห้องเรียน เราได้เรียน binary search ไปแล้ว เราจะใช้วิธีดังกล่าว | วัตถุ ที่เราต้องทำการตรวจสอบในข้อนี้คือ ตัวเลข 1,2,3,... (หรือ index ของอะเรย์นั่นเอง) ซึ่ง ค่า <math> n \, </math> จะเป็นค่าที่อยู่ในช่วงดังกล่าว และมีเงื่อนไขคือ A[0]ถึง A[n]มีค่าเป็นศูนย์ และ A[n+1] เป็นต้นไปมีค่าเป็นหนึ่ง (เขียนสั้น ๆ คือ A[n]=0 และ A[n+1]=1) แต่โจทย์ต้องการให้เวลาในการหาค่า <math> n \, </math> ดังกล่าวเป็น <math>O(\log n) \,</math> จากการตัวอย่างการค้นหาในห้องเรียน เราได้เรียน binary search ไปแล้ว เราจะใช้วิธีดังกล่าว | ||
| − | วิธีการค้นหาจะทำดังนี้ | + | วิธีการค้นหาจะทำดังนี้ ให้เริ่มค้นหาก่อนว่าค่าของอะเรย์ในตำแหน่งต่อไปนี้ <math>2^1, 2^2,2^3,...,2^j \,</math> เป็นศูนย์หรือไม่ การค้นหาดังกล่าวทำเพื่อที่จะจำกัดช่วงของคำตอบว่าค่าที่ต้องการอยู่ในช่วงไหนกันแน่ เพราะจากโจทย์ขนาดของอะเรย์ที่เป็นอินพุตมีขนาดไม่จำกัด ดังนั้นการหาค่ากลางจะทำไม่ได้ พอได้ช่วงของคำตอบที่เป็นไปได้ที่เป็นช่วงจำกัดมา เราจึงทำการหาแบบ binary search อีกทีว่าค่าที่ต้องการอยู่ตรงไหน |
จากในห้องเรียนเราได้เห็นแล้วว่าเงื่อนไขของ binary search มีสามเงื่อนไขคือ หยุด ไปทางซ้าย และไปทางขวา สำหรับข้อนี้เงื่อนไขเหล่านี้จะเป็นดังนี้ | จากในห้องเรียนเราได้เห็นแล้วว่าเงื่อนไขของ binary search มีสามเงื่อนไขคือ หยุด ไปทางซ้าย และไปทางขวา สำหรับข้อนี้เงื่อนไขเหล่านี้จะเป็นดังนี้ | ||
| แถว 22: | แถว 22: | ||
::: return k | ::: return k | ||
:: else if a[k]=1 and a[k+1]=1 | :: else if a[k]=1 and a[k+1]=1 | ||
| − | ::: return FindN(a,2^(j-1),2^j) | + | ::: return FindN(a,2^(j-1),2^j) // ได้ช่วงจำกัดที่ต้องการมาแล้ว |
:: else if a[k]= 0 and a[k+1]=0 | :: else if a[k]= 0 and a[k+1]=0 | ||
| − | ::: return FindInterval(a,j+1) | + | ::: return FindInterval(a,j+1) // วิ่งไปหาช่วงต่อไปในอะเรย์ด้านขวา |
FindN(a,i,j) | FindN(a,i,j) | ||
| แถว 34: | แถว 34: | ||
::: return k | ::: return k | ||
:: else if a[k]=1 and a[k+1]=1 | :: else if a[k]=1 and a[k+1]=1 | ||
| + | ::: return FindN(a,i,k-1) | ||
| + | :: else if a[k]= 0 and a[k+1]=0 | ||
::: return FindN(a,k+1,j) | ::: return FindN(a,k+1,j) | ||
| − | |||
| − | |||
เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน FindN และการค้นหาใน FindInterval ซึ่ง FindInterval จะหยุดทำเมื่อค่า <math> n \leq 2^j < 2n \,</math> ซึ่งจะทำงานทั้งหมด <math> j \, </math> รอบ ส่วน FindN จะทำการหาค่า <math> n\, </math> ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด <math> O(\log 2^j)=O(\log n) \,</math> รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น <math> j+O(\log n)=O(\log n) </math> รอบ | เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน FindN และการค้นหาใน FindInterval ซึ่ง FindInterval จะหยุดทำเมื่อค่า <math> n \leq 2^j < 2n \,</math> ซึ่งจะทำงานทั้งหมด <math> j \, </math> รอบ ส่วน FindN จะทำการหาค่า <math> n\, </math> ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด <math> O(\log 2^j)=O(\log n) \,</math> รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น <math> j+O(\log n)=O(\log n) </math> รอบ | ||
รุ่นแก้ไขเมื่อ 08:36, 2 กันยายน 2552
อินพุต: อะเรย์ ที่มีขนาดเป็น infinity ที่มีคุณสมบัติคือสมาชิก ตัวแรกมีค่าเป็นศูนย์ นอกนั้นมีค่าเป็นหนึ่ง
![{\displaystyle A[.]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d7c94f2709bd2a774f6ba82f90c80116d6baeb6)
เอาพุต: ค่า
วัตถุ ที่เราต้องทำการตรวจสอบในข้อนี้คือ ตัวเลข 1,2,3,... (หรือ index ของอะเรย์นั่นเอง) ซึ่ง ค่า จะเป็นค่าที่อยู่ในช่วงดังกล่าว และมีเงื่อนไขคือ A[0]ถึง A[n]มีค่าเป็นศูนย์ และ A[n+1] เป็นต้นไปมีค่าเป็นหนึ่ง (เขียนสั้น ๆ คือ A[n]=0 และ A[n+1]=1) แต่โจทย์ต้องการให้เวลาในการหาค่า ดังกล่าวเป็น จากการตัวอย่างการค้นหาในห้องเรียน เราได้เรียน binary search ไปแล้ว เราจะใช้วิธีดังกล่าว
วิธีการค้นหาจะทำดังนี้ ให้เริ่มค้นหาก่อนว่าค่าของอะเรย์ในตำแหน่งต่อไปนี้ เป็นศูนย์หรือไม่ การค้นหาดังกล่าวทำเพื่อที่จะจำกัดช่วงของคำตอบว่าค่าที่ต้องการอยู่ในช่วงไหนกันแน่ เพราะจากโจทย์ขนาดของอะเรย์ที่เป็นอินพุตมีขนาดไม่จำกัด ดังนั้นการหาค่ากลางจะทำไม่ได้ พอได้ช่วงของคำตอบที่เป็นไปได้ที่เป็นช่วงจำกัดมา เราจึงทำการหาแบบ binary search อีกทีว่าค่าที่ต้องการอยู่ตรงไหน
จากในห้องเรียนเราได้เห็นแล้วว่าเงื่อนไขของ binary search มีสามเงื่อนไขคือ หยุด ไปทางซ้าย และไปทางขวา สำหรับข้อนี้เงื่อนไขเหล่านี้จะเป็นดังนี้
- เงื่อนไขหยุด คือ A[k]=0 and A[k+1]=1
- เงื่อนไขไปทางซ้ายคือ A[k]=1 and A[k+1]=1 // แสดงว่าวิ่งเกินมาทางขวาเกินไปแล้ว คำตอบต้องอยู่ทางซ้ายแน่นอน
- เงื่อนไขไปทางขวาคือ A[k]=0 and A[k+1]=0 // แสดงว่าวิ่งยังไม่ถึงคำตอบ วิ่งช้าไป คำตอบต้องอยู่ทางขวาแน่นอน
เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้ (รอบแรกของการทำงานให้ ให้ j=1)
FindInterval(a,j)
- if j<0
- return -1
- else
- k = 2^j
- if a[k]=0 and a[k+1]=1
- return k
- else if a[k]=1 and a[k+1]=1
- return FindN(a,2^(j-1),2^j) // ได้ช่วงจำกัดที่ต้องการมาแล้ว
- else if a[k]= 0 and a[k+1]=0
- return FindInterval(a,j+1) // วิ่งไปหาช่วงต่อไปในอะเรย์ด้านขวา
FindN(a,i,j)
- if j<i
- return -1
- else
- k = (i+j)/2
- if a[k]=0 and a[k+1]=1
- return k
- else if a[k]=1 and a[k+1]=1
- return FindN(a,i,k-1)
- else if a[k]= 0 and a[k+1]=0
- return FindN(a,k+1,j)
เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน FindN และการค้นหาใน FindInterval ซึ่ง FindInterval จะหยุดทำเมื่อค่า ซึ่งจะทำงานทั้งหมด รอบ ส่วน FindN จะทำการหาค่า ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น รอบ
