Thailand OI: คอมพิวเตอร์โอลิมปิก ประเทศไทย

Union-Find Data Structure คือ โครงสร้างข้อมูลแบบหนึ่ง ที่เอาไว้ใช้สำหรับข้อมูลที่อยู่ในรูป Disjoint Set

Disjoint Set คืออะไร

Disjoint Set ก็คือ เวลาเรามี Universe ที่ประกอบด้วยสมาชิกจำนวนหนึ่ง แล้วเราแบ่งมันเป็น set ย่อยๆหลายๆเซต ที่มีคุณสมบัติดังนี้

• ถ้าหยิบมาสองเซตย่อยใดๆ จะ intersection กันได้เซตว่าง (สองเซตใดๆไม่มีสมาชิกซ้ำกัน)
• ทุกเซต union กันได้ Universe (ต้องมีสมาชิกครบ Universe)

พูดง่ายๆแล้ว Big-O Notation หรือ สัญกรณ์โอใหญ่ คืออะไรที่ช่วยเราประมาณ ว่าเวลาในการรันอัลกอริธึม(ส่วนใหญ่จะคิดในกรณีที่แย่ที่สุด หรือ worst-case) จะเป็นประมาณเท่าไหร่ หรือ จะใช้ประมาณเมมโมรี่ที่ใช้ก็ได้

ในบล็อกโพสต์นี้ จะขออธิบายการหา Big-O คร่าวๆก่อน (มีภาคต่อภายหลัง)

(ทางผู้เขียนขอแนะนำให้ท่านอ่าน กำหนดการพลวัตเบื้องต้น ก่อนที่จะเริ่มอ่านหน้านี้นะคะ เพราะเนื้อหาจะต่อเนื่องกัน)

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

(ต่อไปนี้จะขออนุญาตเรียก Dynamic Programming สั้น ๆ ว่า ไดนามิก หรือ “หมิก” นะคะ)

Update: ติดตามตอนต่อไปได้ที่นี่

เนื้อหาในที่นี้มีความยากอยู่พอสมควร ผู้อ่านควรมีความรู้เรื่อง ฟังก์ชั่นเรียกตัวเอง (Recursive function) และ สัญกรณ์โอใหญ่ (Big-O notation) มาก่อน ขอไม่อธิบายหลักการทำงานมา ณ ที่นี้ ผู้อ่านสามารถหาอ่านเพิ่มเติมได้จากวิกิพีเดีย หรือ ที่นี่

คนที่เข้ามาอ่านก็คงสนใจเรื่องการหมิกใช่ไหมคะ ว่าหมิกคืออะไร ดังนั้นก่อนอื่นจะขอแนะนำว่า หลักการของหมิกก็คือ “จะแก้ปัญหาเล็ก ๆ ก่อน แล้วขยายไปยังปัญหาที่ใหญ่กว่าต่อไป”
อ่านแล้วอาจจะงง ไม่เป็นไรค่ะ มีคำอธิบายที่ละเอียดกว่านี้รออยู่