วีดีโอ: O ใหญ่ของการค้นหาไบนารีคืออะไร?
2024 ผู้เขียน: Lynn Donovan | [email protected]. แก้ไขล่าสุด: 2023-12-15 23:54
ค้นหาไบนารี เร็วกว่าเชิงเส้น ค้นหา ยกเว้นอาร์เรย์ขนาดเล็ก
ค้นหาไบนารี อัลกอริทึม
| การแสดงภาพของ การค้นหาไบนารี อัลกอริทึมที่ 7 คือค่าเป้าหมาย | |
|---|---|
| ระดับ | ค้นหา อัลกอริทึม |
| ประสิทธิภาพเคสที่ดีที่สุด | โอ (1) |
| ประสิทธิภาพโดยเฉลี่ย | โอ (ล็อก n) |
| ความซับซ้อนของพื้นที่กรณีที่เลวร้ายที่สุด | โอ (1) |
ในที่นี้ ความซับซ้อนของการค้นหาแบบไบนารีคืออะไร?
ค้นหาไบนารี ทำงานในเวลาลอการิทึมที่เลวร้ายที่สุด โดยทำการเปรียบเทียบ O(log n) โดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์ O คือสัญกรณ์ Big O และ log คือลอการิทึม ค้นหาไบนารี ใช้พื้นที่คงที่ (O(1)) ซึ่งหมายความว่าพื้นที่ที่ใช้โดยอัลกอริทึมจะเหมือนกันสำหรับองค์ประกอบจำนวนเท่าใดก็ได้ในอาร์เรย์
นอกจากนี้ การค้นหาแบบไบนารีจะเร็วที่สุดหรือไม่ ใช่และไม่. ใช่แล้วล่ะ ค้นหา ที่เร็วกว่าโดยเฉลี่ยมากกว่าสองส่วน ค้นหา . แต่ฉันเชื่อว่าพวกมันยังคงเป็น O(lg N) โดยมีค่าคงที่ต่ำกว่า คุณต้องการลดเวลาที่ใช้ในการค้นหาองค์ประกอบของคุณ
ในทำนองเดียวกันอาจมีคนถามว่าคุณจะเขียนการค้นหาแบบไบนารีได้อย่างไร
ค้นหาไบนารี : ค้นหา อาร์เรย์ที่เรียงลำดับโดยการหาร.ซ้ำๆ ค้นหา แบ่งครึ่ง. เริ่มต้นด้วยช่วงเวลาที่ครอบคลุมทั้งอาร์เรย์ ถ้าค่าของ ค้นหา คีย์มีค่าน้อยกว่ารายการที่อยู่ตรงกลางของช่วงเวลา ให้จำกัดช่วงเวลาให้แคบลงเหลือครึ่งล่าง มิฉะนั้นให้แคบลงไปที่ครึ่งบน
ความซับซ้อนของเวลาของการค้นหาไบนารีคืออะไร?
ดังนั้นจึงต้องมีพฤติกรรมบางอย่างที่อัลกอริธึมแสดงให้ ความซับซ้อน ของล็อก n. เรามาดูกันว่ามันทำงานอย่างไร ตั้งแต่ การค้นหาไบนารี มีประสิทธิภาพกรณีที่ดีที่สุดของ O(1) และประสิทธิภาพกรณีที่เลวร้ายที่สุด (กรณีเฉลี่ย) ของ O (บันทึก n) เราจะดูตัวอย่างของกรณีที่แย่ที่สุด พิจารณาอาร์เรย์ที่เรียงลำดับจาก 16 องค์ประกอบ