이 시리즈는 학교 "컴퓨터 알고리즘" 수업 내용을 기반으로 합니다.
1. Amortized Analysis
Potential method
배열에 push를 하는데, 배열이 꽉차면 그 배열의 크기를 늘리면서 복사를 해야하기 때문에 갑자기 큰 비용이 발생함
그래서 potential(잠재에너지)개념이 등장
매번 push를 할 때 잠재 에너지에 1씩 저장함 -> 나중에 배열이 꽉차면 잠재에너지로 배열크기를 늘리고(복사) 계속해서 push를 하면 됨 -> 갑자기 큰 비용이 발생하지 않음
Amortized Cost = Actual Cost + Φ(D i) − Φ(D i−1)
잠재비용 = 실제 비용 + 잠재변화량
2. Space complexity
저장 공간(Storage space)에 들어가야 할 것들
- 명령어(Instructions)
- 상수, 간단한 변수(constants, simple variables)
- 입력 데이터와 추가 작업 공간(데이터 구조 포함)
입력데이터의 저장 형태
- 배열, 그래프 등등
- 배열로 저장되면, 추가 작업 공간만 분석하면 됨
- 그래프와 같은 형태의 경우, 입력되어있는 데이터와 추가작업공간 모두 분석해놔야함
분석 방법
- 최악의 경우 공간 분석(Worst-case space analysis)
최악의 입력이 들어왔을 때 알고리즘이 사용하는 최대 메모리 양 - 평균적인 경우 공간 분석(Average-case space analysis)
모든 가능한 입력에 대해 알고리즘이 사용하는 평균적인 메모리 양
