동적 배열

동적 배열 추가 연산 시간 복잡도

추가 연산(append operation): 배열의 가장 끝에 새로운 값을 넣는 것

동적 배열은 내부적으로는 정적 배열을 사용

정적 배열이 남는 공간이 있을 경우(1)와 정적 배열이 다 찼을 경우(2)가 있다.

1. 남는 공간 중 가장 앞 쪽에 데이터 저장 => O(1)

2. • 사용 중인 배열보다 두 배 큰 메모리를 예약
   • 기존 데이터를 새로운 배열로 복사
   • 새로운 데이터를 추가
     => O(n)

특정 인덱스에 접근하는 것은 O(1)이지만 이를 n번 수행하기 때문에 O(n), 데이터를 저장하는데 O(1) 따라서 총 O(n+1)이지만 1은 생략

분할 상환 분석(Amortized Analysis)

시간 복잡도는 최악의 경우를 고려하여 정하지만 위 동적 배열 추가 연산처럼 여러 경우 중 상대적으로 2번보다 1번이 일어날 확률이 크지만 시간 복잡도는 2번을 고려하는 비합리적인 상황을 대비하여 시간 복잡도를 조금 다르게 계산하는 방법

한단어로 저장하면 할부
최악을 가정하지 않고 평균을 내 계산하는 방법

• 같은 동작을 n번 했을 때 드는 시간이 x일 때
  동작을 한번 하는데 걸린 시간은 x/n

동적 배열 삽입 연산(Insert Operation)

• 정적 배열에 남는 공간이 있을 때
  삽입할 인덱스부터 마지막 데이터 인덱스의 값을 하나씩 뒤로 옮긴다.(O(n))
  데이터를 저장한다.(O(1))
  O(n+1) => O(n)
• 정적 배열에 남는 공간이 없을 때:
  기존의 두 배 크기의 배열로 데이터를 복사한다.(O(n))
  삽입할 인덱스부터 마지막 데이터 인덱스의 값을 하나씩 뒤로 옮긴다.(O(n))
  데이터를 저장한다.(O(1))
  O(2n+1) => O(n)

동적 배열 삭제 연산

• 특정 위치의 데이터를 삭제할 때
  특정 위치의 뒤에 있는 데이터를 하나씩 앞으로 옮긴다.(O(n))
• 가장 뒤에 있는 데이터를 삭제할 때(pop 연산)
  O(n)