การวิเคราะห์ค่าตัดจำหน่าย
การวิเคราะห์นี้ใช้เมื่อการดำเนินการเป็นครั้งคราวช้ามาก แต่การดำเนินการส่วนใหญ่ที่ดำเนินการบ่อยมากจะเร็วกว่า ในโครงสร้างข้อมูล เราต้องวิเคราะห์ค่าตัดจำหน่ายสำหรับตารางแฮช ชุดแยกส่วน ฯลฯ
ในตารางแฮช เวลาส่วนใหญ่ที่ความซับซ้อนของเวลาในการค้นหาคือ O(1) แต่บางครั้งก็ดำเนินการ O(n) เมื่อเราต้องการค้นหาหรือแทรกองค์ประกอบในตารางแฮชสำหรับกรณีส่วนใหญ่ มันจะใช้เวลาคงที่ในการทำงาน แต่เมื่อเกิดการชนกัน มันต้องใช้การดำเนินการ O(n) ครั้งเพื่อแก้ปัญหาการชน
วิธีการรวม
วิธีการรวมจะใช้เพื่อค้นหาต้นทุนทั้งหมด หากเราต้องการเพิ่มข้อมูลจำนวนมาก เราก็ต้องหาค่าตัดจำหน่ายตามสูตรนี้
สำหรับลำดับของการดำเนินการ n รายการ ต้นทุนคือ −
ตัวอย่างการวิเคราะห์ค่าตัดจำหน่าย
สำหรับไดนามิกอาร์เรย์ สามารถแทรกไอเท็มที่ดัชนีที่กำหนดในเวลา O(1) แต่ถ้าดัชนีนั้นไม่มีอยู่ในอาร์เรย์ จะไม่สามารถทำงานในเวลาคงที่ได้ สำหรับกรณีนั้น ในขั้นต้นจะเพิ่มขนาดของอาร์เรย์เป็นสองเท่า จากนั้นแทรกองค์ประกอบหากมีดัชนี
สำหรับไดนามิกอาร์เรย์ ให้ 𝑐𝑖 =ต้นทุนของการแทรก 𝑖𝑡ℎ