반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 23: 분할 상환 분석 (Amortized Analysis) 분할 상환 분석 (Amortized Analysis)분할 상환 분석은 알고리즘의 시간 복잡도를 분석하는 기법으로, 개별 연산의 최악의 경우 시간 복잡도가 아닌, 일련의 연산에 대한 평균 시간 복잡도를 계산하는 방법입니다. 이는 데이터 구조의 연산이 불균등하게 발생할 때 매우 유용합니다. 분할 상환 분석의 주요 기법에는 Aggregate Analysis, Accounting Method, Potential Method가 있습니다.Aggregate AnalysisAggregate Analysis는 전체 연산에 대해 총 비용을 계산하고, 이를 연산 수로 나누어 평균 비용을 구하는 방법입니다.Accounting MethodAccounting Method는 각 연산에 대해 가상의 "크레딧"을 할당하여 연산 비용을.. 2024. 8. 1. 이전 1 다음 반응형
