array.md

Array

Array란

번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조

---

• 배열의 인덱스는 0부터 시작하여 0,1,2,3 ... , size - 1의 인덱스를 참조할 수 있다.
• 배열A의 n번째에 해당하는 변수는 A[n]으로 표현한다.

Array의 특징

1. 데이터가 순차적으로 저장된다.

   • 배열은 실제 메모리 상에서도 메모리가 순차적으로 저장된다. 따라서 어느 위치에 있는지 인덱스로 손쉽게 접근이 가능하다.

2. 동일한 Type의 데이터가 저장된다.

3. 배열은 값의 중복을 허용한다.

4. 메모리 할당 시 크기를 바꿀 수 없다.

   • 다른 자료구조에 비해 한번 메모리 할당을 하면 크기를 바꿀 수 없다.

5. 자료를 삽입, 삭제하기 어렵다.

Array의 시간 복잡도

1. 접근 : O(1)

• 접근은 n번째 인덱스에 해당하는 값을 찾아내는 연산
• 순차저장의 특성상 시작 주소값에 해당 원하는 인덱스의 위치를 사칙연산하면 되기 때문에 O(1) 로 접근이 가능하다.

2. 검색 : O(n)

• 배열의 검색은 순차검색이기 때문에 원하는 값이 나올 때까지 순서대로 검색해야 한다. 따라서 O(n) 의 시간복잡도를 가진다.

3. 추가, 삭제: O(n)

추가와 삭제는 먼저 빈 공간이 마련됐다고 가정한다.

• 해당 인덱스를 찾아서 추가 및 삭제를 진행해야 하기 때문에 검색과 동일한 O(n) 의 시간복잡도를 가진다.