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

อัลกอริทึมสำหรับนับอินเวอร์ชันสำคัญนั้นเหมือนกับอัลกอริทึมการนับอินเวอร์ชันธรรมดาเกือบทุกประการ กล่าวคือเราจะนับอินเวอร์ชันสำคัญไปพร้อมๆ กับทำ merge sort แต่สำหรับการนับอินเวอร์ชันสำคัญ เราจะปรับปรุงฟังก์ชัน merge เล็กน้อยดังต่อไปนี้

ในฟังก์ชัน merge เรามีตัวแปร $i_{x}\,$ และ $i_{y}\,$ เพื่อบอกตำแหน่งของสมาชิกในอะเรย์ $x\,$ และ $y\,$ ที่ยังไม่ได้นำไปใส่อะเรย์ $z\,$ ซึ่งเป็นผลลัพธ์ แต่ในอัลกอริทึมสำหรับการนับอินเวอร์ชันสำคัญ เราจะให้มีตัวแปร $i_{2y}\,$ ซึ่งเราจะนิยามให้เป็นจำนวนเต็มที่มากที่สุดที่ทำให้ $x[i_{x}]>2y[i_{2y}]\,$ สังเกตว่า $i_{2y}$ มีค่าเท่ากับจำนวนสมาชิกของอะเรย์ $y\,$ ที่มีค่าน้อยกว่า $x[i_{x}]/2\,$ ด้วยเหตุนี้ เมื่อเรานำสมาชิกจาก $x\,$ ไปใส่ใน $z\,$ เราสามารถนำ $i_{2y}\,$ ไปบวกเข้ากับจำนวนอินเวอร์ชันสำคัญได้ เมื่อทำเช่นนี้ไปจนครบสมาชิกทุกตัวของ $x\,$ เราจะได้จำนวนอินเวอร์ชันสำคัญที่เลขตัวหน้าอยู่ใน $x\,$ และเลขตัวหลังอยู่ใน $y\,$

เมื่อเรานำสมาชิกตัวหนึ่งของ $x\,$ ไปใส่ใน $z\,$ เราจะเพิ่มค่า $i_{x}\,$ ขึ้นหนึ่ง ซึ่งนั่นหมายความว่าเราจะต้องเปลี่ยน $i_{2y}\,$ ให้สอดคล้องกับ $x[i_{x}]\,$ ค่าใหม่ การเปลี่ยน ​$i_{2y}\,$ นี้ทำได้โดยเพิ่ม ​$i_{2y}\,$ ไปเรื่อยๆ จนกระทั่ง ​$x[i_{x}]\leq 2y[i_{2y}+1]\,$

เราสามารถนำแนวความคิดข้างบนมาเขียนเป็น pseudocode ได้ดังต่อไปนี้

<geshi lang="c"> Merge(x, nx, y, ny) {

   สร้างอะเรย์ z ขนาด nx + ny
   
   ix = 1
   iy = 1
   iz = 1
   
   i2y = 0
   while (i2y < ny) and (x[ix] > 2*y[i2y+1]) do
       i2y = i2y + 1

   inversion_count = 0  // จำนวนอินเวอร์ชันสำคัญ

   while (ix <= nx) and (y <= ny) do
   {
        if x[ix] < y[iy] then
        {
           z[iz] = x[ix]
           ix = ix + 1
           iz = iz + 1
           // เพิ่มจำนวนอินเวอร์ชันสำคัญขึ้น i2y
           inversion_count = inversion_count + i2y
           // ปรับค่า i2y ใหม่
           while (i2y < ny) and (x[ix] > 2*y[i2y+1]) do
               i2y = i2y + 1            
        }
        else
        {
           z[iz] = y[iy]
           iy = iy + 1
           iz = iz + 1
        }
   }

   while ix <= nx do
   {
       z[iz] = x[ix]
       ix = ix + 1
       iz = iz + 1
       // เพิ่มจำนวนอินเวอร์ชันสำคัญขึ้น i2y
       inversion_count = inversion_count + i2y
       // ปรับค่า i2y ใหม่
       while (i2y < ny) and (x[ix] > 2*y[i2y+1]) do
           i2y = i2y + 1            
   }

   while iy <= ny do
   {
       z[iz] = y[iy]
       iy = iy + 1
       iz = iz + 1    
   }

   return inversion_count, z

} </geshi>

เวลาการทำงานของฟังก์ชัน Merge ใหม่คือ $O(n)\,$ เหมือนเดิม เนื่องจากลูป <geshi lang="c"> while (i2y < ny) and (x[ix] > 2*y[i2y+1]) do

   i2y = i2y + 1            

</geshi> จะเริ่มต้นทำงานรวมทั้งหมดไม่เกิน $n_{x}\,$ ครั้ง (เนื่องจากมันจะเริ่มต้นทำงานทุกครั้งที่ $x[i_{x}]\,$ จะถูกนำไปใส่ยังอะเรย์​ $z\,$) และคำสั่ง i2y = i2y + 1 จะทำงานไม่เกิน $n_{y}\,$ ครั้งเนื่องจาก $i_{2y}\leq n_{y}\,$ ฉะนั้นเวลาที่เราใช้ทั้งหมดกับการจัดการค่า $i_{2y}\,$ ไม่เกิน ​$O(n_{x}+n_{y})=O(n)\,$

ด้วยเหตุนี้เราจึงสามารถนับอินเวอร์ชันสำคัญได้ในเวลา $O(n\log n)\,$