โจทย์จาก: http://www.spoj.com/problems/INVCNT/
แปล : ให้ A เป็น array ขนาด n โดยที่สมาชิกไม่ซ้ำ ถ้ามี i < j แล้ว A[i] > A[j] ถือว่าคู่ (A[i],A[j]) เกิดการ inversion จงหาว่า A เกิดการ inversion กี่ครั้ง
กำหนดให้
0 <= i,j <= n-1
ตัวอย่าง:
8 4 2 1
คำตอบคือ (8,4),(8,2),(8,1),(4,2),(4,1) = 5 ตัว
1 2 3
คำตอบคือ 0 เพราะทุก A[i] > A[j]
วิธีทำแบบตรงไปตรงมา
ถ้าแปลโจทย์ให้เข้าใจง่ายขึ้นจะแปลได้ว่า ทุกตำแหน่ง(A[i]) ถ้ามีตัวฝั่งขวา(A[j])ที่มือที่น้อยกว่า ถือว่าเป็น inversion จากแนวคิดนี้ ผมจะสามารถเช็คได้เพราะในแต่ละตำแหน่ง A[i] ผมจะมองหาตัวขวา A[j] ที่น้อยกว่า
จากแนวคิดข้างบน เมื่อ n มีค่ามากขึ้น algorithm เราจะช้ามาก big o ของ algorithm นี้ คือ O(n^2)
เราจะทำให้ดีขึ้นกว่านี้ได้อย่างไร
ถ้าเรามอง Algorithm ข้างบนดีๆ เราจะเห็นว่ามันคือ การ sort ตัวเลขใน array เราสามารถ sort ให้ไวขึ้นโดยใช้ Algorithm ที่ชื่อ ว่า merge sort และเมื่อ n มากๆ big o ของ algorithm นี้คือ O(nlog n) ซึ่งถือว่าไวกว่า O(n^2) พอสมควร
ทำไม merge sort ถึงเวิค
ถ้าเรามี A = {2,3,8,6,1}
merge sort จะแยก 2 3 8 6 1 ออกจากกัน แล้วเปรียบเทียบทีละคู่ 2 กับ 3 เรียงแล้ว 8 กับ 6 ยังไม่เรียงเราก็เรียงเป็น 6,8 ตอนนี้ A จะเป็น 2,3 8,6 1 เราเปรียบเทียบ 8,6 กับ 1 จะได้ใหม่เป็น 1,6,8
A จะกลายเป็น 2,3 1,6,8 เปรียบเทียบ 2,3 กับ 1,6,8 เราจะได้เป็น 1,2,3,6,8
แต่ละครั้งที่เราเปรียบเทียบ เราจะรู้ว่ามีฝั่งขวาที่มากกว่าฝั่งซ้ายกี่ตัว
บรรทัดที่ 27 จะหาจำนวนตัวฝั่งซ้ายที่มากกว่าฝั่งขวา
ไม่มีความคิดเห็น:
แสดงความคิดเห็น