การเข้าใจความซับซ้อนของห่วงจําเป็นสําหรับการออกแบบอัลกอริทึมที่มีประสิทธิภาพใน C และ C++ มันช่วยประเมินเวลาในการประมวลผล และปรับแต่งประสิทธิภาพของรหัส บทความนี้อธิบายวิธีวิเคราะห์ความซับซ้อนของห่วงอย่างมีประสิทธิภาพ

พื้นฐานการวนรอบความซับซ้อน

ความซับซ้อนของการหมุน จะวัดว่าเวลาในการประมวลผลของวงนั้น เพิ่มขึ้นเมื่อเทียบกับขนาดที่ป้อนเข้าไป มักจะแสดงโดยใช้สัญลักษณ์ของบิ๊กโอ ซึ่งอธิบายขอบเขตบนของอัลกอริทึมที่รันอยู่

หมุนแบบง่าย ๆ

สําหรับวงพื้นฐานที่วิ่งจาก 1 ถึง N ความซับซ้อนคือ O(N) การเขียนแบบแต่ละตัวทําหน้าที่ต่อเนื่องของงาน ดังนั้น เกล็ดการทํางานรวมเป็นอิสระเชิงเส้นด้วยขนาดป้อนข้อมูล

วนรอบที่ตั้งให้เป็นรัง

วงจรที่อยู่เป็นรัง (incordity) จะคูณความซับซ้อนของมัน ตัวอย่างเช่น วงในวงอื่น ทั้งสองคนวิ่งจาก 1 ไป N, ส่งผลให้ระบบ O(N^2) ซับซ้อน จํานวนครั้งที่มันวนอยู่ คือ N คูณด้วย N

การ หมุน เวียน และ สภาพ การณ์ หลาย อย่าง

เมื่อหลายวงทํางานแบบแยกส่วน องค์ประกอบของวงจะเพิ่มขึ้น ตัวอย่างเช่น วงแหวนสองวงที่วิ่งจาก 1 ถึง N มีความซับซ้อนรวมกันของ O(N) + O(N) = O(N) อย่างไรก็ตาม ถ้าวงวนเป็นรังหรือสภาพการวนของวงทั้งหมด ให้วิเคราะห์แต่ละกรณีแยกกันเพื่อตัดสินความซับซ้อนโดยรวม