หลักคร่าว ๆ 10^8

โดยทั่วไประบบตรวจคำตอบออนไลน์จะทำการดำเนินการง่าย ๆ ได้ประมาณ 10^8 ครั้งต่อวินาที ตัวเลขนี้คืองบประมาณการทำงานสำหรับทั้งโปรแกรมของคุณ 💡

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

การไล่ตรวจแบบ O(n) เมื่อ n = 10^6 ใช้เพียงหนึ่งล้านขั้นตอน ซึ่งต่ำกว่างบประมาณมาก วิธีแก้แบบเชิงเส้นมักผ่านได้อย่างสบาย

เมื่อ n = 10^6 การเรียงลำดับแบบ O(n log n) ใช้ประมาณ 2 เท่าของ 10^7 ขั้นตอน ซึ่งยังอยู่ในงบประมาณหนึ่งวินาทีได้สบาย ดังนั้นการเรียงลำดับจึงไม่ค่อยเป็นคอขวด

วิธีแก้แบบ O(n^2) จะใช้งบประมาณเกือบเต็มเมื่อ n = 10^4 ซึ่งมีค่าใช้จ่าย 10^8 ขั้นตอน หลังจากนั้นความซับซ้อนเชิงกำลังสองจะเริ่มเกินขีดจำกัดเวลา

วิธีแก้แบบ O(n^3) จะยังทำงานได้ถึงประมาณ n = 500 เท่านั้น เมื่อนำค่านี้มายกกำลังสามจะได้ประมาณ 10^8 ขั้นตอน ซึ่งอยู่ตรงขอบของงบประมาณ

O(2^n) จะเพิ่มเป็นสองเท่าในแต่ละขั้นตอน จึงใช้ได้เฉพาะกับ n ขนาดเล็กประมาณ 20 ถึง 25 เท่านั้น หลังจากนั้นจำนวนการดำเนินการจะพุ่งเกิน 10^8

Python ทำงานต่อขั้นตอนได้ช้ากว่า ดังนั้นสำหรับลูปที่ทำงานหนัก ให้คิดว่างบประมาณใกล้เคียง 10^7 มากกว่า โปรดประเมินอย่างเผื่อไว้เมื่อข้อจำกัดดูเฉียดขีดจำกัด

กฎ 10^8 นับเฉพาะขั้นตอนง่าย ๆ การทำงานหนักภายในลูป เช่น การสร้างข้อความ จะเพิ่ม ตัวคูณคงที่ ซึ่งทำให้งบประมาณจริงของคุณลดลง

ขีดจำกัดเวลามักอยู่ที่ 1 หรือ 2 วินาที ขีดจำกัด 2 วินาทีทำให้งบประมาณ เพิ่มเป็นประมาณสองเท่า จึงมีเวลาเผื่อเพิ่มขึ้นเล็กน้อย

แทนค่า n ลงในความซับซ้อนของคุณเสมอ แล้วเปรียบเทียบกับ 10^8 ก่อน การตรวจสอบความสมเหตุสมผลอย่างรวดเร็วนี้ช่วยป้องกันไม่ให้คุณเขียนวิธีแก้ที่ไม่มีทางผ่าน

ลองนำกฎ 10^8 ไปใช้

ตอนนี้คุณเชื่อมโยงจำนวนการดำเนินการกับเวลาได้แล้ว: ประมาณ 10^8 ครั้งต่อวินาที วิธีแบบเชิงเส้นและ n log n ปลอดภัย วิธีแบบกำลังสองมีเพดานใกล้ 10^4 และคุณรู้จักตรวจสอบก่อนเขียนโค้ด ✅