อ่านข้อจำกัดและเลือกความซับซ้อน

โจทย์ทุกข้อระบุขีดจำกัดของ n และค่าต่าง ๆ ข้อจำกัดเหล่านี้จะบอกอย่างเงียบ ๆ ว่าผู้ออกโจทย์คาดหวังความซับซ้อนระดับใด 🔍

ก่อนออกแบบสิ่งใด ให้ดูค่า n ที่มากที่สุดในข้อจำกัดก่อน ขนาดของ n จะเป็นตัวตัดสินว่าต้องใช้วิธีแบบกำลังสอง เชิงเส้น หรือลอการิทึม

เมื่อ n มีค่าไม่เกิน 20 แม้แต่การลองครบทุกกรณีแบบ เอ็กซ์โพเนนเชียล ก็ยังอยู่ในขีดจำกัด ข้อจำกัดขนาดเล็กเป็นโอกาสให้ลองทุกชุดผสมได้โดยไม่ต้องกังวล

หาก n มีค่าถึงไม่กี่ร้อย วิธีแก้แบบ O(n^3) ก็ยังผ่านได้ ลูปสามชั้นหรือ DP พื้นฐานที่ทำงานกับคู่ค่าถือว่าเหมาะสมในกรณีนี้

เมื่อ n อยู่ราว 5000 ให้มุ่งไปที่ O(n^2) ลูปซ้อนที่วนผ่านรายการจะใช้ประมาณ 2.5 เท่าของ 10^7 ขั้นตอน ซึ่งยังอยู่ในงบประมาณ

เมื่อ n มีค่าเป็น 10^5 หรือ 10^6 คุณต้องใช้ O(n log n) หรือ O(n) การเรียงลำดับ ผลรวมสะสม และตัวชี้สองตัวจะเป็นเครื่องมือหลักของคุณ

หาก n มีค่าถึงหนึ่งพันล้าน ไม่มีลูปใดที่วนครบ n รอบแล้วจะทำงานทัน คุณต้องใช้ O(log n) หรือ O(1) โดยอาศัยคณิตศาสตร์หรือการค้นหาแบบทวิภาคบนคำตอบ

ข้อจำกัดของค่าก็สำคัญเช่นกัน ตัวเลขขนาดใหญ่เป็นสัญญาณเตือนเรื่องค่าล้นในภาษาอื่น และอาจบอกเป็นนัยว่าควรใช้เลขคณิตแบบมอดุลาร์

โจทย์ที่มีหลายชุดทดสอบมักจำกัด ผลรวมของ n แทนที่จะจำกัด n ของแต่ละชุด โปรดอ่านส่วนนี้อย่างละเอียด เพราะจะเปลี่ยนขนาดของลูปที่คุณใช้ได้อย่างปลอดภัย

เลือกความซับซ้อนเป้าหมายจาก n แล้วเลือกอัลกอริทึมที่ทำได้ตามนั้น การให้ n ชี้นำการออกแบบย่อมดีกว่าการเดาแล้วต้องเขียนใหม่ภายหลัง

จดจำตารางนี้ไว้ในใจ แผนผังจากข้อจำกัดสู่ความซับซ้อนจะเปลี่ยนการดูขีดจำกัดอย่างรวดเร็วให้กลายเป็นแผนทันทีระหว่างการแข่งขัน

ให้ n ชี้ทางไปสู่ความซับซ้อนที่เหมาะสม

ตอนนี้คุณอ่านข้อจำกัดเป็นเป้าหมายได้แล้ว: n ขนาดเล็กเปิดโอกาสให้ลองครบทุกกรณี, 10^5 ต้องใช้ n log n และ 10^9 ต้องใช้ลอการิทึมหรือคณิตศาสตร์ ให้ n เป็นตัวเลือกแนวทางของคุณ 🗺️