앞선 배열(동적배열) 강의에서 추가(append) 할 때의 경우를 여유공간이 있을 때와 없을 때로 나누어 열심히 분석해서 amortized analysis 로 O(1)* 이 된다는 것을 배웠습니다.

삭제는 어떤가요?

자료구조 강의를 더 듣다 보니 동적배열 삭제 연산에서,

1) worst-case analysis 로 맨 앞 데이터를 삭제하는 경우, 삭제한 후 모든 나머지 데이터를 한칸씩 앞으로 당겨오는 과정에서 시간 복잡도는 O(n) 이 되고,

2) 맨 앞 데이터를 삭제하는 경우, 다른 것 건드릴 것 없이 삭제만 하면 되기에 O(1) 이 라고 강의노트에 써있습니다.

다만, amortized analysis 로 분석을 하지는 않아 동적배열의 삭제 경우도 결국 O(1)* 이다! 라는 결론은 없네요.

근데 추상자료형까지 듣다보면, 큐와 스택 구현을 동적 배열로 할 경우,

스택 - 맨 뒤 데이터 삭제 -> 분할상환 O(1)

큐 - 맨 앞 데이터 삭제 -> O(n)

이라고 써있네요.

동적배열에서의 데이터 삭제는 amortized analysis 로 O(1) 이다! 라고 결론 지을 수 있을까요?