การวิเคราะห์เชิงสัญลักษณ์
เมื่อใช้การวิเคราะห์แบบ asymptotic เราจะได้รับแนวคิดเกี่ยวกับประสิทธิภาพของอัลกอริธึมตามขนาดอินพุต เราไม่ควรคำนวณเวลาทำงานที่แน่นอน แต่เราควรค้นหาความสัมพันธ์ระหว่างเวลาทำงานและขนาดอินพุต เราควรติดตามเวลาทำงานเมื่อขนาดของอินพุตเพิ่มขึ้น
สำหรับความซับซ้อนของพื้นที่ เป้าหมายของเราคือรับความสัมพันธ์หรือฟังก์ชันที่มีพื้นที่ว่างในหน่วยความจำหลักเพื่อให้อัลกอริทึมสมบูรณ์
พฤติกรรมการแสดงอาการ
สำหรับฟังก์ชัน f(n) พฤติกรรมเชิงซีมโทติกคือการเติบโตของ f(n) เมื่อ n มีขนาดใหญ่ขึ้น ไม่พิจารณาค่าอินพุตขนาดเล็ก งานของเราคือค้นหาว่าต้องใช้เวลาเท่าใดสำหรับค่าที่ป้อนเข้ามามาก
ตัวอย่างเช่น f(n) =c * n + k เป็นความซับซ้อนของเวลาเชิงเส้น f(n) =c * n 2 + k คือความซับซ้อนของเวลากำลังสอง
การวิเคราะห์อัลกอริทึมสามารถแบ่งออกเป็นสามกรณีที่แตกต่างกัน กรณีดังต่อไปนี้ −
กรณีที่ดีที่สุด − ที่นี่คำนวณขอบเขตล่างของเวลาทำงาน อธิบายพฤติกรรมของอัลกอริทึมภายใต้สภาวะที่เหมาะสม
กรณีเฉลี่ย − ในกรณีนี้ เราคำนวณขอบเขตระหว่างขอบเขตบนและขอบเขตล่างของเวลาทำงานของอัลกอริทึม ในกรณีนี้จำนวนการดำเนินการที่ดำเนินการจะไม่ใช่ค่าต่ำสุดและสูงสุด
กรณีที่เลวร้ายที่สุด − ในกรณีนี้ เราคำนวณขอบเขตบนของเวลาทำงานของอัลกอริทึม ในกรณีนี้จะมีการดำเนินการตามจำนวนครั้งสูงสุด
