ความซับซ้อนของเวลาที่ตัดจำหน่ายในโครงสร้างข้อมูล

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

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

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

วิธีการรวม

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

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

$\frac{Cost ( n\:operations)}{n}=\frac{Cost (normal\:operations)+Cost (แพง\:operations)}{n}$

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

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

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

$So\:ci=1+\begin{cases}i\:-\:1,if\:i-1\:is\:power\:of\:2 \\0, \:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:มิฉะนั้น \end{cases}$

$$\frac{\displaystyle\sum\limits_{i=1}^n ci}{n}\leq\frac{n+\displaystyle\sum\limits_{j=1}^{\lfloor\log{2}{ \lgroup n-1\rgroup}\rfloor} 2j}{n}=\frac{O\lgroup n\rgroup}{n}$$