Celebrity
ดาวเด่นในงาน คือ ผู้ที่ทุกคนในงานรู้จักเธอ (หรือเขา) แต่เธอ (หรือเขา) ไม่รู้จักใครสักคนเลย
เราหาดาวเด่นในงานได้หลายวิธี เช่น
- ลุยทดสอบไปทีละคน (แต่รู้สึกว่าจะช้า ไม่มีทำในการทดลองนี้ แต่น่าไปลองเขียนดู)
- ใช้ divide and conquer แบ่งคนเป็นสองกลุ่มจำนวนพอ ๆ กัน หาดาวเด่นในชุดแรก ถ้ามีก็นำมาตรวจกับคนในชุดหลัง
ถ้าไม่ใช่ ก็ไปหาดาวเด่นชุดหลัง ถ้ามีก็นำมาตรวจสอบกับชุดแรก (วิธีเขียนในเมท็อด celebDQ5050) ถ้าวิเคราะห์เชิงคณิตศาสตร์จะได้ O(n log n)
- ใช้ divide and conquer เหมือนกันแบบที่แล้ว แต่แบ่งคนคนออกเป็น 1 กับ n-1 คน โดยเลือก 1 คนที่มั่นใจว่าไม่ใช่ดาวเด่นแน่
หากวิเคราะห์เชิงคณิตศาสตร์ จะพบว่าได้ประสิทธิภาพเป็น O(n) ที่ดีกว่าแบบก่อนนี้ (อ่านรายละเอียดในหนังสือ) (วิธีนี้เขียนในเมท็อด celebDQ1)
- นำวิธีที่แบ่ง 1 กับ n-1 ข้างบนนี้มาเขียนเป็นวงวน while แล้วไม่มีการตรวจสอบระหว่างการวน แต่ละย้านการตรวจสอบไว้ท้ายสุด (วิธีนี้เขียนในเมท็อด celeb)
ใช้เวลาการทำงานเป็น O(n) เช่นกัน
เรานำวิธีทั้งสามมาทดลองกับข้อมูลแบบที่มีดาวเด่น กับแบบที่ไม่มีดาวเด่น สิ่งที่น่าสนใจคือ แบบแบ่งครึ่งมีภาระมากกว่าก็จริง แต่มีแนวโน้มเป็นเชิงเส้น
ทำไมจึงเป็นเข่นนั้น ?
และอยากให้ลองเปรียบเทียบเฉพาะจำนวนการถามว่า i รู้จัก j หรือไม่ ซึ่งคือคำสั่ง if (a[ ][ ] ) หรือ if (!a[ ][ ] ) ในโปรแกรมข้างล่างนี้
เลือกพิจารณาของแต่ละเมท็อด เนื่องจากในหนึ่งวิธีที่เขียนอาจมีการถามเช่นนี้มากกว่าหนึ่งแห่ง อย่าลืม tick sumLines ข้างล่างกราฟเส้น
เพื่อรวมจำนวนการถามให้ถูกต้อง
(อย่าลืมอ่านข้อแนะนำในการตีความผลการทดลอง)
มีดาวเด่น
การทดลองนี้หาดาวเด่นที่ปรากฏในทุก ๆ ตำแหน่ง ดังนั้นหามี n คน ก็หา n ครั้ง ผลที่ได้เป็นภาระสะสมของการหาทั้ง n ครั้ง
จึงนำภาระที่ได้มาหารด้วย n (ดูที่ f(n,c) = c/n) ได้เป็นเส้นตรง ตีความได้ว่า ใช้เวลาแปรเป็นเชิงเส้นกับจำนวนคน
ไม่มีดาวเด่น
การทดลองนี้หาดาวเด่นที่ไม่มีอยู่ในงาน แต่จะทำ n กรณีโดยที่แต่ละกรณีแทนแต่ละคนเกือบเป็นดาวเด่น
ดังนั้นหามี n คน ก็หา n ครั้ง ผลที่ได้เป็นภาระสะสมของการหาทั้ง n ครั้ง
จึงนำภาระที่ได้มาหารด้วย n (ดูที่ f(n,c) = c/n) ได้เป็นเส้นตรง ตีความได้ว่า ใช้เวลาแปรเป็นเชิงเส้นกับจำนวนคน
สมชาย ประสิทธิ์จูตระกูล