การวิเคราะห์แบบไม่แสดงอาการ

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

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

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

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

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

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

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

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

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

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