1. 분할 상환 분석
- 알고리즘 분석시 각각의 연산마다 최악의 경우를 가정하는 것은 불합리하다.
- 어떠한 임의의 알고리즘에서 어떤 연산은 자원적 측면에서 상당한 비용을 소모하는 반면 다른 연산은 그렇게 고비용을 지불하지 않을 수도 있
- 상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려한다.
2. Array Doubling
: Array에 새로운 원소를 append 할 때는 O(1)의 시간이 들지만 Array가 full이 되는 순간 Array Doubling에 O(n)의 시간을 소요한 뒤에 append를 수행하게 된다. 따라서 Amortized Analysis를 통해 분석을 하고 O(1*)(amortized O(1) time)
3. Amortized Analysis
accounting cost : total cost / n = 2nt / n = 2t 으로 연산마다 미래 연산을 대비해서 저축한다.
actual cost : 더블링이 일어난다면 nt+1 그렇지 않다면 1
amortized cost : 1 + 2t
https://gazelle-and-cs.tistory.com/87
분할 상환 분석 (Amortized Analysis)
이번 포스트에서는 분할 상환 분석(amortized analysis)에 대해서 알아보도록 하겠습니다. 자료 구조나 알고리즘 수업을 들으셨다면 분명 한 번쯤은 들어 보신 개념일 것입니다. 개인적으로는 자료
gazelle-and-cs.tistory.com
https://zeddios.tistory.com/60
알고리즘 ) Amortized Analysis
안녕하세요. Zedd입니다ㅎㅎ 아까전에 어떤분이 글을 잘 봤다고 메세지를 주셨어요 :) 원래 글도 Amortized Analysis를 쓰기 위해서 썼던건데... 이참에 얼른 써야겠다고 생각했어요 XD 그래서 오늘은
zeddios.tistory.com
https://hororolol.tistory.com/407
[알고리즘] CH6. Amortized Analysis - Array Doubling
Array doubling 사이즈가 n인 배열 A가 있다고 하자. A가 꽉 찼을 때, push가 들어온다면 사이즈가 두 배인(2n) 배열 B를 만들어, 배열 A에 있는 것들을 옮기고, 새로운 데이터를 push한다. 이때, (n*t+1)만큼
hororolol.tistory.com
'Computer Science > Data Structure' 카테고리의 다른 글
| Heap, PQ (0) | 2022.06.11 |
|---|---|
| Binary Search (이분탐색) (0) | 2022.05.04 |
| Map and Hash (0) | 2022.04.28 |
| asymptotic notation(점근 표기법) (0) | 2022.04.13 |
