Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

ความซับซ้อนตัดจำหน่าย


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

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

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

วิธีการรวม

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

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

ความซับซ้อนตัดจำหน่าย

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

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

ความซับซ้อนตัดจำหน่าย

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

ความซับซ้อนตัดจำหน่าย