Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

ความซับซ้อนที่ไม่แสดงอาการ


การวิเคราะห์เชิงสัญลักษณ์

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

สำหรับความซับซ้อนของพื้นที่ เป้าหมายของเราคือรับความสัมพันธ์หรือฟังก์ชันที่มีพื้นที่ว่างในหน่วยความจำหลักเพื่อให้อัลกอริทึมสมบูรณ์

พฤติกรรมการแสดงอาการ

สำหรับฟังก์ชัน f(n) พฤติกรรมเชิงซีมโทติกคือการเติบโตของ f(n) เมื่อ n มีขนาดใหญ่ขึ้น ไม่พิจารณาค่าอินพุตขนาดเล็ก งานของเราคือค้นหาว่าต้องใช้เวลาเท่าใดสำหรับค่าที่ป้อนเข้ามามาก

ตัวอย่างเช่น f(n) =c * n + k เป็นความซับซ้อนของเวลาเชิงเส้น f(n) =c * n 2 + k คือความซับซ้อนของเวลากำลังสอง

การวิเคราะห์อัลกอริทึมสามารถแบ่งออกเป็นสามกรณีที่แตกต่างกัน กรณีดังต่อไปนี้ −

กรณีที่ดีที่สุด − ที่นี่คำนวณขอบเขตล่างของเวลาทำงาน อธิบายพฤติกรรมของอัลกอริทึมภายใต้สภาวะที่เหมาะสม

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

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

ความซับซ้อนที่ไม่แสดงอาการ