ในวิทยาการคอมพิวเตอร์การวิเคราะห์แบบเฉลี่ยเป็นวิธีการวิเคราะห์ความซับซ้อนของอัลกอริทึมที่กำหนดหรือปริมาณทรัพยากร โดยเฉพาะเวลาหรือหน่วยความจำ ที่ใช้ในการดำเนินการแรงจูงใจในการวิเคราะห์แบบเฉลี่ยคือการพิจารณาเวลาการทำงานในกรณีที่เลวร้ายที่สุดอาจมองโลกในแง่ร้ายเกินไป การวิเคราะห์แบบเฉลี่ยจึงหาค่าเฉลี่ยของเวลาการทำงานของการดำเนินการในลำดับหนึ่งๆ ตลอดลำดับนั้น^{[ 1 ] : 306} สรุปได้ว่า: "การวิเคราะห์แบบเฉลี่ยเป็นเครื่องมือที่มีประโยชน์ซึ่งช่วยเสริมเทคนิคอื่นๆ เช่น การวิเคราะห์ กรณีที่เลวร้ายที่สุดและ การวิเคราะห์ กรณีเฉลี่ย " ^{[ 2 ] : 14 [ 3 ]}

สำหรับการดำเนินการของอัลกอริทึมที่กำหนดไว้ สถานการณ์บางอย่าง (เช่น การกำหนดพารามิเตอร์อินพุตหรือเนื้อหาโครงสร้างข้อมูล) อาจส่งผลให้เกิดต้นทุนทรัพยากรจำนวนมาก ในขณะที่สถานการณ์อื่นๆ อาจมีต้นทุนไม่สูงนัก การวิเคราะห์แบบถัวเฉลี่ยจะพิจารณาการดำเนินการที่มีต้นทุนสูงและต้นทุนต่ำร่วมกันตลอดลำดับการดำเนินการทั้งหมด ซึ่งอาจรวมถึงการพิจารณาประเภทของอินพุตที่แตกต่างกัน ความยาวของอินพุต และปัจจัยอื่นๆ ที่ส่งผลต่อประสิทธิภาพ^{[ 2 ]}

การวิเคราะห์แบบคิดค่าเสื่อมราคาเริ่มต้นมาจากวิธีที่เรียกว่าการวิเคราะห์แบบรวม ซึ่งปัจจุบันถูกรวมเข้ากับการวิเคราะห์แบบคิดค่าเสื่อมราคาแล้ว เทคนิคนี้ได้รับการแนะนำอย่างเป็นทางการครั้งแรกโดยRobert TarjanในบทความAmortized Computational Complexity ในปี 1985 [ ^{1 ]}ซึ่งกล่าวถึงความต้องการรูปแบบการวิเคราะห์ที่มีประโยชน์มากกว่าวิธีการทางความน่าจะเป็นทั่วไปที่ใช้กัน การคิดค่าเสื่อมราคาในตอนแรกใช้สำหรับอัลกอริทึมเฉพาะบางประเภท โดยเฉพาะอย่างยิ่งที่เกี่ยวข้องกับ^{ต้นไม้}ไบนารีและ การดำเนินการ รวมอย่างไรก็ตาม ปัจจุบันเป็นที่แพร่หลายและมีบทบาทในการวิเคราะห์อัลกอริทึมอื่นๆ อีกมากมายเช่นกัน^{[ 2 ]}

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

โดยทั่วไปมี 3 วิธีในการวิเคราะห์ค่าเสื่อมราคา ได้แก่ วิธีรวมวิธีทางบัญชีและวิธีศักยภาพทั้งหมดนี้ให้คำตอบที่ถูกต้อง การเลือกใช้ขึ้นอยู่กับว่าวิธีใดสะดวกที่สุดสำหรับสถานการณ์นั้นๆ^{[ 4 ]}

• การวิเคราะห์โดยรวมจะกำหนดขอบเขตบนT ( n ) ของต้นทุนรวมของลำดับ การดำเนินการ n ^{ครั้ง}จากนั้นคำนวณต้นทุนที่ตัดจำหน่ายเป็นT ( n ) / n ^{[ 4} ]
• วิธีการบัญชีเป็นรูปแบบหนึ่งของการวิเคราะห์แบบรวม ซึ่งกำหนดต้นทุนที่ตัดจำหน่าย ให้กับการดำเนินงานแต่ละรายการ ซึ่งอาจแตกต่างจากต้นทุนจริง การดำเนินงานในช่วงแรกจะมีต้นทุนที่ตัดจำหน่ายสูงกว่าต้นทุนจริง ซึ่งจะสะสม "เครดิต" ที่ประหยัดไว้เพื่อชำระการดำเนินงานในภายหลังที่มีต้นทุนที่ตัดจำหน่ายต่ำกว่าต้นทุนจริง เนื่องจากเครดิตเริ่มต้นที่ศูนย์ ต้นทุนจริงของลำดับการดำเนินงานจึงเท่ากับต้นทุนที่ตัดจำหน่ายลบด้วยเครดิตที่สะสมไว้ เนื่องจากเครดิตจะต้องไม่เป็นลบ ต้นทุนที่ตัดจำหน่ายจึงเป็นขอบเขตบนของต้นทุนจริง โดยปกติ การดำเนินงานระยะสั้นจำนวนมากจะสะสมเครดิตดังกล่าวในปริมาณเล็กน้อย ในขณะที่การดำเนินงานระยะยาวที่หายากจะทำให้เครดิตลดลงอย่างมาก^{[ 4 ]}
• วิธีการศักยภาพเป็นรูปแบบหนึ่งของวิธีการบัญชีที่เครดิตที่ประหยัดจะถูกคำนวณเป็นฟังก์ชัน ("ศักยภาพ") ของสถานะของโครงสร้างข้อมูล ต้นทุนที่ตัดจำหน่ายคือต้นทุนทันทีบวกกับการเปลี่ยนแปลงในศักยภาพ^{[ 4 ]}

ลองพิจารณาอาร์เรย์แบบไดนามิกที่ขยายขนาดขึ้นเมื่อมีการเพิ่มองค์ประกอบเข้าไป เช่นArrayListในภาษา Java หรือstd::vectorC++ ถ้าเราเริ่มต้นด้วยอาร์เรย์แบบไดนามิกขนาด 4 เราสามารถเพิ่มองค์ประกอบได้ 4 ตัว และแต่ละครั้งจะใช้เวลาคงที่แต่การเพิ่มองค์ประกอบที่ห้าเข้าไปในอาร์เรย์นั้นจะใช้เวลานานขึ้น เนื่องจากอาร์เรย์จะต้องสร้างอาร์เรย์ใหม่ที่มีขนาดเพิ่มขึ้น คัดลอกองค์ประกอบเดิมไปยังอาร์เรย์ใหม่ จากนั้นจึงเพิ่มองค์ประกอบใหม่เข้าไป การเพิ่มองค์ประกอบในครั้งต่อๆ ไปก็จะใช้เวลาคงที่เช่นกัน จากนั้นการเพิ่มในครั้งต่อๆ ไปจะต้องมีการปรับขนาดของอาร์เรย์อย่างช้าๆ อีกครั้ง

โดยทั่วไป สำหรับจำนวนการผลักข้อมูลไปยังอาร์เรย์ที่มีขนาดเริ่มต้นใดๆ ก็ตาม เวลาสำหรับขั้นตอนที่ปรับขนาดอาร์เรย์จะรวมกันเป็นอนุกรมเรขาคณิตในขณะที่เวลาคงที่สำหรับการผลักข้อมูลที่เหลือแต่ละครั้งก็จะรวมกันเป็นเช่นกันดังนั้นเวลาเฉลี่ยต่อการดำเนินการผลักข้อมูลคือการให้เหตุผลนี้สามารถทำให้เป็นทางการและสรุปทั่วไปสำหรับโครงสร้างข้อมูลที่ซับซ้อนมากขึ้นโดยใช้การวิเคราะห์แบบถัวเฉลี่ย^{[ 4 ​​]}${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle O(n)/n=O(1)}$

ภาพแสดงการใช้งานคิวซึ่ง เป็น โครงสร้างข้อมูลแบบ FIFO (First-In, First-Out) ที่ เขียนด้วยภาษา Python :

คลาสQueue : """แทนคอลเลกชันแบบเข้าก่อนออกก่อน"""" # เริ่มต้นคิวด้วยลิสต์ว่างสองรายการdef __init__ ( self ): self . input = [] # เก็บองค์ประกอบที่ถูกเพิ่มเข้าไปใน คิว self . output = [] # เก็บองค์ประกอบที่ถูกดึงออกจากคิวdef enqueue ( self , element ): "" " เพิ่มวัตถุลงในท้ายคิว""" self.input.append(element ) # เพิ่มองค์ประกอบลงในรายการอินพุตdef dequeue ( self ): "" " ลบและส่งคืนอ็อบเจ็กต์ที่อยู่ต้นคิว""" if not self.output : # ถ้าลิสต์เอาต์พุตว่างเปล่า # โอนองค์ประกอบทั้งหมดจากลิสต์อินพุตไปยังลิสต์ เอาต์พุตโดยกลับลำดับwhile self.input : # ใน ขณะที่ลิสต์อินพุตไม่ว่างเปล่าself.output.append ( self.input.pop ( ) ) # ดึงองค์ประกอบสุดท้ายออกจากลิสต์อินพุตและเพิ่มเข้าไปในลิสต์เอาต์พุตreturn self.output.pop () # ดึงและส่งคืนองค์ประกอบสุดท้ายจากรายการผลลัพธ์

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

อย่างไรก็ตาม การดำเนินการ dequeue นั้นซับซ้อนกว่า หากอาร์เรย์เอาต์พุตมีองค์ประกอบอยู่แล้ว การดำเนินการ dequeue จะใช้เวลาคงที่ มิฉะนั้น การดำเนินการ dequeue จะใช้ เวลา ⁠ ⁠${\displaystyle O(n)}$ในการเพิ่มองค์ประกอบทั้งหมดลงในอาร์เรย์เอาต์พุตจากอาร์เรย์อินพุต โดยที่nคือความยาวปัจจุบันของอาร์เรย์อินพุต หลังจากคัดลอก องค์ประกอบ nรายการจากอินพุต เราสามารถดำเนิน การ dequeue ได้ nครั้ง โดยแต่ละครั้งใช้เวลาคงที่ ก่อนที่อาร์เรย์เอาต์พุตจะว่างเปล่าอีกครั้ง ดังนั้น เราสามารถดำเนินการ dequeue ต่อเนื่องกันได้nครั้งในเวลาเพียง⁠ ⁠${\displaystyle O(n)}$ซึ่งหมายความว่าเวลาเฉลี่ยของการดำเนินการ dequeue แต่ละครั้งคือ⁠ ⁠ ${\displaystyle O(1)}$^{[ 5 ]}

อีกทางเลือกหนึ่ง เราสามารถคิดค่าใช้จ่ายในการคัดลอกรายการใดๆ จากอาร์เรย์อินพุตไปยังอาร์เรย์เอาต์พุตให้กับขั้นตอนการเพิ่มรายการลงในคิว (enqueue) ก่อนหน้านี้สำหรับรายการนั้น วิธีการคิดค่าใช้จ่ายนี้จะเพิ่มเวลาเฉลี่ยในการเพิ่มรายการลงในคิวเป็นสองเท่า แต่จะลดเวลาเฉลี่ยในการลบรายการออกจากคิว (dequeue) เหลือ⁠ ⁠${\displaystyle O(1)}$ .

• โดยทั่วไปแล้ว "อัลกอริทึมแบบถัวเฉลี่ย" หมายถึงอัลกอริทึมที่การวิเคราะห์แบบถัวเฉลี่ยแสดงให้เห็นว่ามีประสิทธิภาพดี
• อัลกอริทึมออนไลน์ส่วนใหญ่มักใช้การวิเคราะห์แบบถัวเฉลี่ย

• "บรรยายครั้งที่ 7: การวิเคราะห์แบบคิดค่าเสื่อมราคา" (PDF)มหาวิทยาลัยคาร์เนกีเมลลอนสืบค้นเมื่อ 14 มีนาคม 2558
• Allan Borodinและ Ran El-Yaniv (1998). การคำนวณออนไลน์และการวิเคราะห์เชิงแข่งขันหน้า 20, 141.