นับการดำเนินการด้วย Big-O

ในการแข่งขัน ความเร็วเป็นสิ่งสำคัญ แทนที่จะจับเวลาโค้ด คุณจะประเมินว่าต้องใช้กี่ขั้นตอน ค่าประเมินนั้นเรียกว่า ความซับซ้อนเชิงเวลา 🚀

Big-O อธิบายว่าจำนวนการดำเนินการเติบโตขึ้นอย่างไรเมื่อขนาดข้อมูลขาเข้า n เพิ่มขึ้น โดยไม่นับรายละเอียดเล็กน้อยและมุ่งเน้นที่แนวโน้มหลัก

เมื่อการทำงานไม่ขึ้นกับ n การทำงานนั้นมีค่าเป็น O(1) การอ่านสมาชิกหนึ่งรายการหรือการบวกหนึ่งครั้งใช้เวลาเท่ากันเสมอ

ลูปง่าย ๆ ที่วนผ่านรายการ n รายการมีความซับซ้อนเป็น O(n) เมื่อข้อมูลขาเข้าเพิ่มเป็นสองเท่า งานก็จะเพิ่มขึ้นประมาณสองเท่า นี่คือรูปแบบงานหลักที่ใช้ในชีวิตประจำวัน

ลูปหนึ่งที่อยู่ภายในอีกลูปหนึ่งและวนผ่านรายการ n รายการมีความซับซ้อนเป็น O(n^2) เมื่อ n = 1000 จะมีหนึ่งล้านขั้นตอน และหลังจากนั้นจะเติบโตอย่างรวดเร็ว

เมื่อแต่ละขั้นตอนลดปัญหาเหลือครึ่งหนึ่ง คุณจะได้ O(log n) การค้นหาแบบทวิภาคสามารถจัดการรายการหนึ่งพันล้านรายการได้ในประมาณ 30 ขั้นตอนเท่านั้น ✨

จากเร็วที่สุดไปช้าที่สุด ลำดับความซับซ้อนที่พบบ่อยคือ O(1), O(log n), O(n), O(n log n), O(n^2) ยิ่งอยู่ด้านบนก็ยิ่งรองรับขนาดที่เพิ่มขึ้นได้ดี

Big-O ไม่สนใจตัวคูณคงที่ ดังนั้น O(2n) จึงเป็น O(n) การวนผ่านข้อมูลสองรอบยังคงเติบโตแบบเชิงเส้น ตัวคูณจึงไม่เปลี่ยนประเภทของความซับซ้อน

เมื่อพจน์ต่าง ๆ ถูกนำมาบวกกัน จะนับเฉพาะพจน์ที่เติบโตเร็วที่สุด O(n^2 + n) จึงย่อเป็น O(n^2) เพราะเมื่อ n เพิ่มขึ้น n^2 จะมีขนาดใหญ่กว่า n มาก

ลูปสองลูปที่ทำงานต่อกันจะรวมกันเป็น O(n + n) = O(n) ส่วนลูปสองลูปที่ซ้อนกันจะคูณกันเป็น O(n^2) รูปแบบของลูปจะบอกคุณได้ว่าเป็นกรณีใด

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

ได้เวลาทดสอบความเข้าใจเรื่อง Big-O ของคุณแล้ว

ตอนนี้คุณอ่านโค้ดในแง่การเติบโตได้แล้ว: O(1), O(n), O(n^2) และ O(log n) ตัดค่าคงที่ออก เก็บพจน์ที่ใหญ่ที่สุด และคิดถึงกรณีเลวร้ายที่สุด 🎯