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

การวิเคราะห์แบบตัดจำหน่ายเกี่ยวข้องกับการประมาณระยะเวลาดำเนินการสำหรับลำดับการดำเนินการในโปรแกรมโดยไม่คำนึงถึงช่วงของการกระจายข้อมูลในค่าอินพุต ตัวอย่างง่ายๆคือการค้นหาค่าในรายการที่เรียงลำดับจะเร็วกว่าในรายการที่ไม่เรียงลำดับ หากมีการจัดเรียงรายการแล้วไม่สำคัญว่าข้อมูลจะกระจายเพียงใด แต่แน่นอนว่าความยาวของรายการมีผลกระทบเนื่องจากการตัดสินใจจำนวนขั้นตอนที่อัลกอริทึมต้องดำเนินการเพื่อให้ได้ผลลัพธ์สุดท้าย

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

• Accounting Method- สิ่งนี้เกี่ยวข้องกับการกำหนดต้นทุนให้กับการดำเนินการแต่ละครั้ง หากการดำเนินการจริงเสร็จสิ้นเร็วกว่าเวลาที่กำหนดเครดิตเชิงบวกบางส่วนจะถูกสะสมในการวิเคราะห์ ในสถานการณ์ย้อนกลับเครดิตจะติดลบ ในการติดตามเครดิตสะสมเหล่านี้เราใช้โครงสร้างข้อมูลสแต็กหรือโครงสร้างต้นไม้ การดำเนินงานที่ดำเนินการก่อนกำหนด (เช่นการจัดเรียงรายการ) มีต้นทุนตัดจำหน่ายสูง แต่การดำเนินงานที่ล่าช้าตามลำดับมีต้นทุนตัดจำหน่ายต่ำกว่าเมื่อใช้เครดิตสะสม ดังนั้นต้นทุนตัดจำหน่ายจึงเป็นขอบเขตบนของต้นทุนจริง

• Potential Method- ในวิธีนี้เครดิตที่บันทึกไว้จะถูกใช้สำหรับการดำเนินการในอนาคตเป็นฟังก์ชันทางคณิตศาสตร์ของสถานะของโครงสร้างข้อมูล การประเมินฟังก์ชันทางคณิตศาสตร์และต้นทุนตัดจำหน่ายควรเท่ากัน ดังนั้นเมื่อต้นทุนจริงมากกว่าต้นทุนตัดจำหน่ายจึงมีโอกาสลดลงและถูกนำไปใช้เพื่อการดำเนินงานในอนาคตซึ่งมีราคาแพง

• Aggregate analysis - ในวิธีนี้เราจะประมาณขอบเขตบนของต้นทุนรวมของ n ขั้นตอน ต้นทุนตัดจำหน่ายคือการหารต้นทุนรวมและจำนวนขั้นตอนอย่างง่าย ๆ (n) ..