การวิเคราะห์ค่าตัดจำหน่าย

การวิเคราะห์ค่าตัดจำหน่าย

การวิเคราะห์นี้ใช้เมื่อการดำเนินการเป็นครั้งคราวช้ามาก แต่การดำเนินการส่วนใหญ่ที่ดำเนินการบ่อยมากจะเร็วกว่า โครงสร้างข้อมูลเราต้องการการวิเคราะห์ค่าตัดจำหน่ายสำหรับ Hash Tables, Disjoint Sets เป็นต้น

ในตารางแฮช เวลาส่วนใหญ่ที่ความซับซ้อนของเวลาในการค้นหาคือ O(1) แต่บางครั้งก็ดำเนินการ O(n) เมื่อเราต้องการค้นหาหรือแทรกองค์ประกอบในตารางแฮชสำหรับกรณีส่วนใหญ่ มันจะใช้เวลาคงที่ในการทำงาน แต่เมื่อเกิดการชนกัน มันต้องการการดำเนินการ O(n) ครั้งเพื่อแก้ปัญหาการชน

วิธีการรวม

วิธีการรวมจะใช้เพื่อค้นหาต้นทุนทั้งหมด หากเราต้องการเพิ่มข้อมูลจำนวนมาก เราก็ต้องหาค่าตัดจำหน่ายตามสูตรนี้

สำหรับลำดับของการดำเนินการ n รายการ ต้นทุนคือ −

ตัวอย่างการวิเคราะห์ค่าตัดจำหน่าย

สำหรับไดนามิกอาร์เรย์ สามารถแทรกไอเท็มที่ดัชนีที่กำหนดในเวลา O(1) แต่ถ้าดัชนีนั้นไม่มีอยู่ในอาร์เรย์ จะไม่สามารถทำงานในเวลาคงที่ได้ สำหรับกรณีนั้น ในขั้นต้นจะเพิ่มขนาดของอาร์เรย์เป็นสองเท่า จากนั้นแทรกองค์ประกอบหากมีดัชนี

สำหรับไดนามิกอาร์เรย์ ให้ =ต้นทุนของ ith การแทรก