|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
รบกวนช่วยหาคำตอบด้วยครับ
การชั่งของครั้งละ 2 ชิ้น(ที่ละก้อน)เพื่อเปรียบเทียบและจัดเรียงตามลำดับจากน้อยไปมากโดยให้การชั่งได้จำนวนน้อยที่สุดจะทำอย่างไร ?
คำถาม 1. ถ้าชั่งที่ละ 2 ก้อนต้องทำอย่างไรเพื่อให้ได้จำนวนครั้งที่น้อยที่สุด ? 2. ถ้ามี n ก้อน โดยเงื่อนไขที่โจทย์กำหนดจะมีจำนวนครั้งเป็นฟังก์ชันของตัวแปร n อย่างไร ? |
#2
|
|||
|
|||
ผมจะตอบรวม ๆ สองข้อละกันนะครับ
ผมว่า มันยังเป็นเรื่องที่ยากมากนะครับ ที่จะหาวิธีที่ใช้จำนวนครั้งในการเปรียบเทียบน้อยที่สุด สำหรับข้อมูลน้อย ๆ อาจจะไม่ยาก แต่ถ้าข้อมูลมาก ๆ ผมไม่รู้ครับ และก็ยังไม่มีใครคิดได้ด้วย (เท่าที่ผมเรียนมาอะนะ) วิธีที่นิยมใช้ในการเรียงข้อมูล (ที่มี domain เป็นเซตอนันต์) ที่ใช้เวลาน้อยที่สุด 3 แบบคือ 1. HeapSort 2. QuickSort 3. MergeSort แต่ละตัวก็มีข้อดีข้อเสียต่างกันครับ โดยส่วนตัวแล้ว ผมเชื่อว่า MergeSort ใช้จำนวนการเปรียบเทียบน้อยที่สุดในสามวิธีนี้ครับ แต่ใช้หน่วยความจำเพิ่มเติมมากที่สุด สำหรับ MergeSort จำนวนครั้งในการเปรียบเทียบ (ในกรณีที่แย่ที่สุด) เป็นฟังก์ชันดังนี้ \[f(n) = n + 2f\left(\frac{n}{2}\right)\]\[f(n) = \Theta(n \log n)\] และในกรณีที่ดีที่สุด ก็จะเป็น \[f(n) = 1 + 2f\left(\frac{n}{2}\right)\]\[f(n) = \Theta(n)\] ส่วน HeapSort ในกรณีที่แย่ที่สุด จำนวนครั้งในการเปรียบเทียบจะเยอะกว่า คือ (ประมาณเอานะครับ) \[f(n) = n \sum_{i=1}^{\log_2(n/2)} \frac{i}{2^i} + \sum_{i=1}^{n - 1}i \log_2 i\]\[f(n) = \Theta(n \log n)\] ส่วนกรณีที่ดีที่สุด จำนวนการเปรียบเทียบคือ (ประมาณ) \[f(n) = n \sum_{i=1}^{\log_2(n/2)} \frac{i}{2^i}\]\[f(n) = \Theta(n)\] แล้วก็ QuickSort จะมีอยู่หลายเวอร์ชั่น (อันนี้แจกแจงยาก ขอสรุปเลยละกัน) ถ้าเป็นแบบ Randomized QuickSort กรณีแย่สุดจะได้ \[f(n) = \Theta(n^2)\]แต่กรณีที่ดีที่สุด จะเป็น\[f(n) = \Theta(n)\] แต่ถ้าเป็น QuickSort แบบ Median-of-Median-of-Five กรณีแย่ที่สุดจะได้\[f(n) = \Theta(n \log n)\]ส่วนกรณีที่ดีที่สุดก็จะเป็น \[f(n) = \Theta(n)\] ในการเขียนเป็นโปรแกรมคอมพิวเตอร์ เนื้อที่ในหน่วยความจำก็มีผลครับ MergeSort ใช้หน่วยความจำเพิ่มอีก \(\Theta(n)\) HeapSort ไม่ใช้หน่วยความจำเพิ่มเติม Randomized QuickSort ใช้หน่วยความจำเพิ่มอีก \(O(n), \Omega(\log n)\) Median-of-Median-of-Five QuickSort ใช้หน่วยความจำเพิ่มอีก \(\Theta(\log n)\) วิธีทำ MergeSort เริ่มจาก Merge ก่อนครับ สมมติว่ามีลำดับของข้อมูลที่เรียงอยู่แล้วสองชุด แต่ละชุดมี \(n\) ตัว เราจะมารวมกันให้เป็นลำดับของข้อมูลที่เรียงถูกต้อง ความยาว \(2n\) ได้อย่างไร? อันนี้ถือว่าคิดกันเองได้ละกันครับว่า กรณีที่แย่ที่สุด จะต้องเปรียบเทียบ \(2n - 1\) ครั้ง เราจึงรู้ว่า \[h(2n) = 2n\]เมื่อ \(h(2n)\) คือจำนวนการเปรียบเทียบที่เกิดขึ้นในการรวมข้อมูลที่เรียงแล้ว 2 ชุด ลองไปคิดเล่น ๆ ละกันนะครับ ว่า Induction Proof ต่อไปนี้ ทำยังไง Basis ข้อมูล 1 ตัวเป็นข้อมูลที่เรียงอยู่แล้ว Fact ถ้ามีข้อมูล \(n\) ตัว สองชุดที่เรียงอยู่แล้ว จะสามารถต่อกันให้เป็นข้อมูล \(2n\) ตัวที่เรียง ได้ในการเปรียบเทียบไม่เกิน \(2n - 1\) ครั้ง Hypothesis สามารถเรียงข้อมูล \(2^m\) ตัวได้ โดยใช้การเปรียบเทียบไม่เกิน \(m 2^m\) ครั้ง 20 กันยายน 2005 23:59 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ tunococ |
|
|