พบกันตรงกลาง
ลดเลขชี้กำลังลงครึ่งหนึ่งด้วยการแบ่งพื้นที่ค้นหา
พบกันตรงกลาง เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เมื่อการลองทุกกรณีช้าเกินไป
ปัญหาบางข้อมี N ประมาณ 40 ซึ่งการลองเซตย่อยทั้งหมด 2^N แบบทำได้ยากเกินไป การแบ่งครึ่งแล้วพบคำตอบช่วยแก้ปัญหาขนาดกลางเหล่านี้ได้ 🤝
แนวคิดหลัก
แบ่งอินพุตออกเป็น สองครึ่ง แก้แต่ละครึ่งด้วยการลองทุกกรณี แล้วรวมผลลัพธ์บางส่วนทั้งสองฝั่งเข้าด้วยกันอย่างชาญฉลาด
ลดเลขชี้กำลังลงครึ่งหนึ่ง
ครึ่งสองส่วนที่มีขนาด N/2 ใช้ค่าใช้จ่ายส่วนละ 2^(N/2) แทนที่จะเป็น 2^N รวมทั้งหมด การลดลงแบบ รากที่สองนี้เปลี่ยน 2^40 ให้เป็น 2^20 ที่จัดการได้ง่าย
เป้าหมายคลาสสิก: ผลรวมเซตย่อย
ถามว่ามีเซตย่อยใดบ้างที่รวมกันได้ค่าเป้าหมาย T หรือไม่ ผลรวมเซตย่อยที่มี N ใกล้ 40 เป็นปัญหาตัวอย่างมาตรฐานของการแบ่งครึ่งแล้วพบคำตอบ
แจกแจงครึ่งแรก
แจกแจงผลรวมของทุกเซตย่อยใน ครึ่งซ้ายแล้วจัดเก็บไว้ เมื่อมีสมาชิก N/2 ตัว จะมีผลรวมเพียง 2^(N/2) ค่า
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []แจกแจงครึ่งที่สอง
ทำแบบเดียวกันกับ ครึ่งขวา โดยสร้างรายการผลรวมของเซตย่อยทั้งหมด ตอนนี้คุณมีรายการสองชุดที่จัดการได้ง่าย
รวมด้วยการค้นหา
สำหรับผลรวมฝั่งขวาแต่ละค่า r คุณต้องการผลรวมฝั่งซ้ายที่เท่ากับ T ลบ r เซตหรือรายการที่เรียงลำดับแล้วช่วยให้ตรวจสอบนี้ได้รวดเร็ว
need = T - r
found = need in left_setสองวิธีในการจับคู่
สำหรับเป้าหมายที่ต้องตรงกันพอดี ให้ใช้ เซตแฮช หากต้องการนับหรือหาผลรวมที่ใกล้ที่สุด ให้เรียงครึ่งหนึ่งแล้วค้นหาแบบทวิภาคในครึ่งนั้น
ต้นทุนด้านเวลา
งานทั้งหมดใช้เวลาประมาณ 2^(N/2) คูณด้วยตัวประกอบลอการิทึมสำหรับการค้นหาหรือการเรียงลำดับ ความซับซ้อนนี้ทำให้ N ใกล้ 40 สามารถจัดการได้
หน่วยความจำคือสิ่งที่ต้องแลก
คุณจัดเก็บครึ่งหนึ่งไว้ทั้งหมด ดังนั้น หน่วยความจำจึงเพิ่มขึ้นเป็น 2^(N/2) โปรดเก็บไว้เฉพาะสิ่งที่จำเป็นเพื่อให้อยู่ภายในขีดจำกัด
จุดเด่นในปัญหาอื่น
นอกเหนือจากผลรวมเซตย่อยแล้ว ยังใช้วิธีนี้กับการหาเซตย่อยค่าสูงสุดภายใต้ขีดจำกัด การนับคู่ และปัญหาแนวลอการิทึมไม่ต่อเนื่องได้ วิธีนี้เหมาะกับการ แบ่งที่ชัดเจน
ตรวจสอบอย่างรวดเร็ว
คุณใช้การแบ่งครึ่งแล้วพบคำตอบกับปัญหาเซตย่อยที่มีสมาชิก N ตัว ต้นทุนด้านเวลาโดยประมาณคือเท่าใด
ทบทวน
แบ่งเป็น สองครึ่ง ลองทุกกรณีในแต่ละครึ่ง แล้วจับคู่ผลรวมฝั่งซ้ายและขวา คุณแลกหน่วยความจำเพิ่มขึ้นเล็กน้อยกับความเร็วที่เพิ่มขึ้นอย่างมาก 🚀
คำถามที่พบบ่อย
บทเรียน “พบกันตรงกลาง” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “พบกันตรงกลาง” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “พบกันตรงกลาง”
ลดเลขชี้กำลังลงครึ่งหนึ่งด้วยการแบ่งพื้นที่ค้นหา คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “พบกันตรงกลาง” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ