จากปัญหาการโยนไข่ตอนที่แล้ว เราได้ข้อเท็จจริงเพิ่มมาสองข้อนั่นคือ สำหรับตึก N ชั้น

1. ถ้ามีไข่ใบเดียว เราไม่มีวิธีอื่นนอกจากทดลองโยนทุกชั้น จำนวนครั้งที่โยนจะไม่เกิน N ครั้ง
2. ถ้ามีไข่สองใบ วิธีที่ดีที่สุดที่รับประกันคำตอบถูกต้องจะมีจำนวนครั้งการโยนเป็น $ O(\sqrt{N}) $

กรณีทั่วไปเมื่อมีไข่ K ใบ

จากกรณีไข่สองใบ เราเห็นว่าวิธีการคิดหาคำตอบนั้นเราใช้ข้อเท็จจริงเมื่อมีไข่หนึ่งใบเข้ามาช่วยคิด ดังนั้นหากเราทดลองคิดที่กรณีไข่สามใบโดยใช้วิธีการคิดแบบเดิม

• ไข่ใบแรก เราทดลองโยนที่ชั้น s,2s,3s,... เมื่อไข่แตกเราจะเหลือช่วงตึกขนาด s ชั้น
• ไข่อีกสองใบที่เหลือ เราใช้วิธีที่กล่าวไปเมื่อตอนที่แล้วทำให้ได้ว่าเราต้องโยนเพิ่มอีก $ O(\sqrt{s}) $ ครั้ง

เมื่อเราลองหาค่า s ที่ดีที่สุดเราจะได้ว่า

\[\begin{align} \sqrt{s} &= \frac{N}{s} \\ s^{\frac{3}{2}} &= N \\ s &= N^{\frac{2}{3}} \end{align}\]

ซึ่งถ้าให้ $ f(N,K) $ แทนจำนวนคร้งการโยนสำหรับตึก N ชั้นและมีไข่ K ใบ จำนวนครั้งการโยนจะเป็น

\[\begin{align} f(N,3) &= \frac{N}{s} + f(s,2) \\ &= \frac{N}{s} + \frac{s}{\sqrt{s}} + \sqrt{s} \\ &= N^{\frac{1}{3}} + \sqrt{N^{\frac{2}{3}}} + \sqrt{N^{\frac{2}{3}}} \\ &= 3N^{\frac{1}{3}} \\ &= O(N^{\frac{1}{3}}) \end{align}\]

ซึ่งเราใช้การให้เหตุผลแบบเดียวกับตอนที่แล้ว เราจะได้ว่าสำหรับไข่ K ใบใดๆ วิธีการโยนที่ดีที่สุดจะมีจำนวนครั้งการโยนไม่ดีไปกว่า $ O(N^\frac{1}{K}) $

จำนวนไข่ยิ่งมาก Big-O จะยิ่งดีขึ้นหรือไม่?

จะเห็นได้ว่าดูเหมือนยิ่งเราเพิ่มจำนวนไข่มากขึ้น Big-O ของจำนวนครั้งการโยนก็ยิ่งลดลง

แต่ถ้าสังเกตให้ดีเราจะพบว่าวิธีการโยนที่กล่าวมานั้นจะมีค่า K เป็นค่าคงที่ นั่นคือไม่ขึ้นกับค่า N

ถ้าหาก K นั้นขึ้นกับค่า N Big-O ของจำนวนครั้งการโยนจะไม่เท่ากับ $ O(N^{\frac{1}{K}}) $ แต่เป็น $ O(KN^{\frac{1}{K}}) $ เนื่องจากเป็นผลรวมของ $ O(N^{\frac{1}{K}}) $ จำนวน K ตัว

นั่นหมายความว่าหากเรามีไข่ N ใบเท่ากับจำนวนชั้นของตึก Big-O กลับกลายเป็น $ O(N*N^{\frac{1}{N}}) = O(N) $ ซึ่งแย่กว่าการที่มีไข่เพียงแค่สองใบเสียอีก นั่นหมายความว่าถ้าเรามีจำนวนไข่มากถึงค่าหนึ่งเราควรเปลี่ยนกลยุทธ์การโยน

ถ้ามีไข่ไม่จำกัด

เมื่อมีไข่ไม่จำกัด ปัญหานี้เราสามารถมองเป็นปัญหาที่เข้าใกล้การเขียนโปรแกรมมากขึ้น

นั่นคือเรามี strictly increasing array ของตัวเลขขนาด N ตัว เราต้องการหาตำแหน่งของตัวเลขใน array ที่มากที่สุดที่น้อยกว่าค่า x หนึ่งๆที่กำหนด

ซึ่งการไล่เช็คค่าทุกค่าใน array ก็เปรียบเสมือนการไล่โยนไข่จากทุกชั้นของตึก

ปัญหานี้มีอัลกอริทึมที่ใช้แก้ได้อย่างมีประสิทธิภาพคือ Binary search algorithm นั่นคือเราจะโยนไข่ จากตรงกลางของช่วงที่เหลือเสมอ การโยนหนึ่งครั้งจะทำให้ขนาดของช่วงลดลงทีละครึ่งหนึ่ง หมายความว่าเราจะโยนไม่เกิน $ \log_2 N $ ครั้ง (ปัดขึ้นเป็นจำนวนเต็มถ้าหากค่าลอการิทึมเป็นทศนิยม)

นั่นแปลว่าเมื่อมีไข่ K ใบที่ $ K \ge \log_2 N $ เราสามารถใช้วิธีนี้เพื่อให้ได้ Big-O ที่ดีกว่าวิธีก่อนหน้านี้

\[\log_2 N \le (\log_2 N)N^{\frac{1}{\log_2 N}}\]

ซึ่ง Binary search algorithm นั้นเป็นวิธีที่ดีที่สุดสำหรับปัญหานี้ อ่านเพิ่มเติมได้ที่นี่

ส่วนกรณี K ที่ขึ้นกับ N และ $ K \lt \log_2 N $ จำนวนครั้งการโยน $ O(KN^{\frac{1}{K}}) $ นั้นดีที่สุดหรือยัง ขอติดไว้โอกาสต่อๆไป