ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4"

รุ่นแก้ไขปัจจุบันเมื่อ 14:28, 2 กันยายน 2552

ในปัญหาข้อนี้เราจะใช้ binary search เหมือนกับปัญหาข้อที่ผ่านๆ มา แต่วัตถุที่เราทำการค้นหาจะแตกต่างจากข้ออื่นมาก

เพื่อความสะดวก เราจะกำหนดให้อะเรย์ $A\,$ และ $B\,$ มีช่อง $A[0]\,$ และ $B[0]\,$ โดยที่ $A[0]=-\infty \,$ และ $B[0]=-\infty \,$ กล่าวคือ $A[0]\,$ และ $B[0]\,$ จะมีค่าน้อยกว่าอะเรย์ช่องอื่นๆ ทั้งหมด แต่เราจะไม่นับว่าช่องที่เพิ่มมาใหม่นี้เป็นส่วนหนึ่งของอะเรย์

เราจะพิสูจน์ข้อความสามข้อความต่อไปนี้

lemma 1: ถ้า $i\,$ และ $j\,$ เป็นจำนวนเต็มที่

$0\leq i\leq m\,$ และ
$0\leq j\leq n\,$ และ
$i+j=k-1\,$ และ
$A[i+1]>B[j]\,$ และ
$B[j+1]>A[i]\,$

แล้วสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ ในอะเรย์ $A\,$ และ $B\,$ คือ $\min(A[i+1],B[j+1])\,$

พิสูจน์: ให้ $x\,$ เป็นจำนวนที่น้อยกว่าระหว่าง $A[i+1]\,$ และ $B[j+1]\,$ แล้วจะได้ว่ามีจำนวน $i\,$ ตัวใน $A\,$ ที่น้อยกว่า $x\,$ และจำนวน $j\,$ ตัวใน $B\,$ ที่น้อยกว่ามัน ฉะนั้นมีจำนวน $i+j=k-1\,$ ตัวใน $A\,$ และ $B\,$ ที่น้อยกว่ามันพอดี ดังนั้น $x\,$ เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ พอดี

lemma 2: ถ้า $A[i+1]\,$ คือจำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ใน $A\,$ และ $B\,$ โดยที่ $0\leq i\leq m\,$ แล้ว หากให้ $j=k-1-i\,$ แล้ว เราจะได้ว่า $A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$

พิสูจน์: เนื่องจาก $A[i+1]\,$ เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ ดังนั้นจะต้องมีสมาชิกใน $A\,$ และ $B\,$ ที่น้อยกว่ามัน $k-1\,$ ตัวพอดี และเนื่องจากมีสมาชิกที่น้อยกว่า $A[i+1]\,$ อยู่ $i\,$ ตัวในอะเรย์ $A\,$ จะต้องมีสมาชิกที่้น้อยกว่า $A[i+1]\,$ อยู่ $k-1-i=j\,$ ตัวใน $B\,$ ซึ่งนี่หมายความว่า $A[i+1]>B[j]\,$

อนึ่ง เราจะได้ว่า $B[j+1]>A[i+1]>A[i]\,$ ด้วย ฉะนั้น lemma เป็นจริง

lemma 3: ถ้า $B[j+1]\,$ คือจำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ใน $A\,$ และ $B\,$ โดยที่ $0\leq j\leq n\,$ แล้ว หากให้ $i=k-1-j\,$ แล้ว เราจะได้ว่า $A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$

พิสูจน์: ใช้วิธีพิสูจน์เดียวกันกับ lemma 2

สังเกตว่า lemma 2 และ lemma 3 เป็น converse ของ lemma 1 ฉะนั้นเราสามารถสรุปได้ว่า

Proposition 4: เราสามารถหาสมาชิกตัวที่มีค่าน้อยที่สุดเป็นอันดับ $k\,$ ในอะเรย์ $A\,$ และ $B\,$ ได้โดยการหาจำนวนเต็ม $i\,$ และ $j\,$ ที่ทำให้ (1) $i+j=k-1\,$ และ (2) $A[i+1]>B[j]\,$ และ (3) $B[j+1]>A[i]\,$ แล้วจึีงหาคำตอบด้วยการหาค่าที่น้อยกว่าระหว่าง $A[i+1]\,$ และ $B[j+1]\,$

(ข้อสังเกต: lemma 2 และ lemma 3 เป็นข้อความที่มีความสำคัญมากเนื่องจากมันรับประกันว่าจะีมี $i\,$ และ $j\,$ เีพียงคู่เดียวเท่านั้นที่จะสอดคล้องกับเงื่อนไขทั้งหมดใน lemma 1)

อัลกอริทึม

อาศัย Proposition 4 เราจะแก้ปัญหานี้ด้วยการทำ binary search บนวัตถุคู่ำลำดับ $(i,j)\,$ โดยที่ $i+j=k-1\,$ โดยเราจะได้ว่าคู่ำลำดับนี้จะมีอยู่อย่างมาก $k\,$ ตัวด้วยกัน ได้แต่ $(0,k-1),(1,k-2),(2,k-3),\ldots ,(k-2,1),(k-1,0)\,$

สำหรับวัตถุแต่ละอัน เราจะทำการเปรียบเทียบสองครั้ง ได้แก่ (1) เปรียบเทียบ $A[i+1]\,$ กับ $B[j]\,$ และ (2) เปรียบเทียบ $B[j+1]\,$ กับ $A[i]\,$ โดยการเปรียบเทียบนี้เกิดผลได้ 3 แบบด้วยกัน

$A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$ : ในกรณีเราจะได้ว่าเราหา $(i,j)\,$ ที่ต้องการเจอแล้ว เราสามารถหยุดการทำงานของ binary search ได้

$A[i+1]>B[j]\,$ และ $B[j+1]<A[i]\,$ : ในกรณีเราพบว่าสำหรับคู่ลำดับ $(i',j')\,$ อื่นๆ ที่ $i'>i\,$ เราจะได้ว่า $A[i'+1]>A[i+1]>B[j]>B[j']\,$ และ $B[j'+1]\leq B[j]<A[i]<A[i']\,$ ด้วยเหตุนี้ $(i',j')\,$ จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ $(i',j')\,$ โดยที่ $i'>i\,$ ออกจากวัตถุที่เป็นไปได้ทั้งหมด

$A[i+1]<B[j]\,$ และ $B[j+1]>A[i]\,$ : ในกรณีเราพบว่าสำหรับคู่ลำดับ $(i',j')\,$ อื่นๆ ที่ $i'<i\,$ เราจะได้ว่า $A[i'+1]<A[i+1]<B[j]<B[j']\,$ และ $B[j'+1]>B[j+1]>A[i]>A[i']\,$ ด้วยเหตุนี้ $(i',j')\,$ จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ $(i',j')\,$ โดยที่ $i'<i\,$ ออกจากวัตถุที่เป็นไปได้ทั้งหมด

จากแนวคิดข้างต้น เราสามารถเขียน pseudocode ของอัลกอริืทึมได้ดังต่อไปนี้

<geshi lang="c"> Search(A, B, k) {

   i_left = 0
   i_right = k-1

   while i_left <= i_right do
   {
      i = (i_left + i_right) / 2
      j = k - 1 - i

      if A[i+1] > B[j] and B[j+1] > A[i] then
           return min(A[i+1], B[j+1])
      else if A[i+1] > B[j] and B[j+1] < A[i] then
           i_right = i-1
      else if A[i+1] < B[j] and B[j+1] > A[i] then
           i_left = i+1
   }

} </geshi>

เนื่องจากในการเช็คเงื่อนไขแต่ละครั้งเราสามารถตัดวัตถุที่เป็นไปได้ออกประมาณครึ่งหนึ่ง เราจะได้ว่าจะมีการวนลูปใน pseudocode อย่างมาก $O(\log k)=O(\log(m+n))=O(\log m+\log n)\,$ ครั้ง ฉะนั้นอัลกอริทึมข้างบนจึงทำงานภายในเวลา $O(\log n+\log m)\,$ ตามต้องการ

@@ แถว 1: / แถว 1: @@
 ในปัญหาข้อนี้เราจะใช้ binary search เหมือนกับปัญหาข้อที่ผ่านๆ มา แต่วัตถุที่เราทำการค้นหาจะแตกต่างจากข้ออื่นมาก
-เพื่อความสะดวก เราจะกำหนดให้อะเรย์ <math>A \,</math> และ <math>B \,</math> มีช่อง <math>A[0] \,</math> และ <math>B[0] \,</math> โดยที่ <math>A[0] = -\infty \,</math> และ <math>B[0] = -\infty \,</math> กล่าวคือ <math>A[0] \,</math> และ <math>B[0] \,</math> จะมีค่าน้อยกว่าอะเรย์ช่องอื่นๆ ทั้งหมด
+เพื่อความสะดวก เราจะกำหนดให้อะเรย์ <math>A \,</math> และ <math>B \,</math> มีช่อง <math>A[0] \,</math> และ <math>B[0] \,</math> โดยที่ <math>A[0] = -\infty \,</math> และ <math>B[0] = -\infty \,</math> กล่าวคือ <math>A[0] \,</math> และ <math>B[0] \,</math> จะมีค่าน้อยกว่าอะเรย์ช่องอื่นๆ ทั้งหมด แต่เราจะไม่นับว่าช่องที่เพิ่มมาใหม่นี้เป็นส่วนหนึ่งของอะเรย์
-เราจะพิสูจน์ข้อความสองข้อความต่อไปนี้
+เราจะพิสูจน์ข้อความสามข้อความต่อไปนี้
@@ แถว 15: / แถว 15: @@
 '''พิสูจน์:''' ให้ <math>x \,</math> เป็นจำนวนที่น้อยกว่าระหว่าง <math>A[i+1] \,</math> และ <math>B[j+1] \,</math> แล้วจะได้ว่ามีจำนวน <math>i \,</math> ตัวใน <math>A \,</math> ที่น้อยกว่า <math>x \,</math> และจำนวน <math>j \,</math> ตัวใน <math>B \,</math> ที่น้อยกว่ามัน ฉะนั้นมีจำนวน <math>i + j = k-1 \,</math> ตัวใน <math>A \,</math> และ <math>B \,</math> ที่น้อยกว่ามันพอดี ดังนั้น <math>x \,</math> เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ <math>k \,</math> พอดี
+'''lemma 2:''' ถ้า <math>A[i+1] \,</math> คือจำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ใน <math>A \,</math> และ <math>B \,</math> โดยที่ <math>0 \leq i \leq m \,</math> แล้ว หากให้ <math>j = k-1-i \,</math> แล้ว เราจะได้ว่า <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>
+'''พิสูจน์:''' เนื่องจาก <math>A[i+1] \,</math> เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ <math>k \,</math> ดังนั้นจะต้องมีสมาชิกใน <math>A \,</math> และ <math>B \,</math> ที่น้อยกว่ามัน <math>k-1 \,</math> ตัวพอดี และเนื่องจากมีสมาชิกที่น้อยกว่า <math>A[i+1] \,</math> อยู่ <math>i \,</math> ตัวในอะเรย์ <math>A \,</math> จะต้องมีสมาชิกที่้น้อยกว่า <math>A[i+1] \,</math> อยู่ <math>k-1-i = j\,</math> ตัวใน <math>B \,</math> ซึ่งนี่หมายความว่า <math>A[i+1] > B[j] \,</math>
+อนึ่ง เราจะได้ว่า <math>B[j+1] > A[i+1] > A[i] \,</math> ด้วย ฉะนั้น lemma เป็นจริง
+'''lemma 3:''' ถ้า <math>B[j+1] \,</math> คือจำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ใน <math>A \,</math> และ <math>B \,</math> โดยที่ <math>0 \leq j \leq n \,</math> แล้ว หากให้ <math>i = k-1-j \,</math> แล้ว เราจะได้ว่า <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>
+'''พิสูจน์:''' ใช้วิธีพิสูจน์เดียวกันกับ lemma 2
+สังเกตว่า lemma 2 และ lemma 3 เป็น converse ของ lemma 1 ฉะนั้นเราสามารถสรุปได้ว่า
+'''Proposition 4:''' เราสามารถหาสมาชิกตัวที่มีค่าน้อยที่สุดเป็นอันดับ <math>k \,</math> ในอะเรย์ <math>A \,</math> และ <math>B \,</math> ได้โดยการหาจำนวนเต็ม <math>i \,</math> และ <math>j \,</math> ที่ทำให้ (1) <math>i+j = k-1 \,</math> และ (2) <math>A[i+1] > B[j] \,</math> และ (3) <math>B[j+1] > A[i] \,</math> แล้วจึีงหาคำตอบด้วยการหาค่าที่น้อยกว่าระหว่าง <math>A[i+1] \,</math> และ <math>B[j+1] \,</math>
+(ข้อสังเกต: lemma 2 และ lemma 3 เป็นข้อความที่มีความสำคัญมากเนื่องจากมันรับประกันว่าจะีมี <math>i \,</math> และ <math>j \,</math> เีพียงคู่เดียวเท่านั้นที่จะสอดคล้องกับเงื่อนไขทั้งหมดใน lemma 1)
+== อัลกอริทึม ==
+อาศัย Proposition 4 เราจะแก้ปัญหานี้ด้วยการทำ binary search บนวัตถุคู่ำลำดับ <math>(i,j) \,</math> โดยที่ <math>i+j = k-1 \,</math> โดยเราจะได้ว่าคู่ำลำดับนี้จะมีอยู่อย่างมาก <math>k \,</math> ตัวด้วยกัน ได้แต่ <math>(0,k-1), (1,k-2), (2,k-3), \ldots, (k-2,1), (k-1,0) \,</math>
+สำหรับวัตถุแต่ละอัน เราจะทำการเปรียบเทียบสองครั้ง ได้แก่ (1) เปรียบเทียบ <math>A[i+1] \,</math> กับ <math>B[j] \,</math> และ (2) เปรียบเทียบ <math>B[j+1] \,</math> กับ <math>A[i] \,</math> โดยการเปรียบเทียบนี้เกิดผลได้ 3 แบบด้วยกัน
+* <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>: ในกรณีเราจะได้ว่าเราหา <math>(i,j) \,</math> ที่ต้องการเจอแล้ว เราสามารถหยุดการทำงานของ binary search ได้
+* <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] < A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' > i \,</math> เราจะได้ว่า <math>A[i'+1] > A[i+1] > B[j] > B[j'] \,</math> และ <math>B[j'+1] \leq B[j] < A[i] < A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' > i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด
+* <math>A[i+1] < B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' < i \,</math> เราจะได้ว่า <math>A[i'+1] < A[i+1] < B[j] < B[j'] \,</math> และ <math>B[j'+1] > B[j+1] > A[i] > A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' < i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด
+จากแนวคิดข้างต้น เราสามารถเขียน pseudocode ของอัลกอริืทึมได้ดังต่อไปนี้
+<geshi lang="c">
+Search(A, B, k)
+{
+    i_left = 0
+    i_right = k-1
+    while i_left <= i_right do
+    {
+       i = (i_left + i_right) / 2
+       j = k - 1 - i
+       if A[i+1] > B[j] and B[j+1] > A[i] then
+            return min(A[i+1], B[j+1])
+       else if A[i+1] > B[j] and B[j+1] < A[i] then
+            i_right = i-1
+       else if A[i+1] < B[j] and B[j+1] > A[i] then
+            i_left = i+1
+    }
+}
+</geshi>
+เนื่องจากในการเช็คเงื่อนไขแต่ละครั้งเราสามารถตัดวัตถุที่เป็นไปได้ออกประมาณครึ่งหนึ่ง เราจะได้ว่าจะมีการวนลูปใน pseudocode อย่างมาก <math>O(\log k) = O(\log(m+n)) = O(\log m + \log n) \,</math> ครั้ง ฉะนั้นอัลกอริทึมข้างบนจึงทำงานภายในเวลา <math>O(\log n + \log m)\,</math> ตามต้องการ

ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4"

รุ่นแก้ไขปัจจุบันเมื่อ 14:28, 2 กันยายน 2552

อัลกอริทึม

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ