재수강하는 자료구조를 공부하다 나온 건데 처음본거라 적어본다.
수업자료에서는 array-based list에서 array가 꽉 차 확장할 때를 예로 들어 설명했다.
e.g.) 꽉 차기 전 list 맨 뒤에 insert한다면 O(1)이지만,
array를 확장해야 할 때는 새로운(capacity를 늘린) array에 복사 후 insert 해야 하기 때문에
O(n)이다.
좀 제대로 알아보고자 구글링을 해봤는데,
여기에선 다른 책의 내용을 인용했는데 다음과 같다.
But one it happens, it won’t happen again for so long that the cost is “amortized.”
(Cracking the Coding Interview 6th edition 43)
capacity를 늘려 O(n)이 되는 사건 자체가 자주 일어나지 않기 때문에, 가끔 이렇게 일어나서
worst case가 되는 것을 말하는 듯 하다.
그리고 우리 과 교수님 블로그도 있길래 봤는데
할부 시간 복잡도(amortized time complexity)는 각 입력의 처리시간을 고려한다는 점에서 평균 시간 복잡도와 유사하다. 그러나 각 입력이 들어올 빈도를 별도로 고려하지 않는다는 점에서 평균 시간 복잡도와는 차이가 있다. 할부 시간 복잡도를 계산할 때는 각 입력이 같은 빈도로 발생한다는 가정 하에 복잡도를 계산한다.
라고 설명하셨다.
