배열(Array)

자료구조 특징

같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.

중복을 허용하고 순서가 있다.

 

시간복잡도

접근(검색)	탐색	삽입	삭제
\(O(1)\)	\(O(N)\)	\(O(N)\)	\(O(N)\)

삽입/삭제

출처: https://wondangcom.com/1567

새로운 요소를 삽입하면 그 인덱스의 뒷 요소는 모두 한 칸씩 뒤로 밀려난다. 그리고 특정 요소를 삭제하면 그 인덱스의 뒷 요소는 모두 한 칸씩 앞당겨진다.

이 과정에서 \(O(N)\)의 시간복잡도를 갖게 된다.

임의 접근(Random Access)

임의 접근은 인덱스를 사용하여 배열 내의 원소를 접근하는 방식이다. 각 요소는 고유한 인덱스를 갖고 있고, 이를 사용하여 배열의 특정 위치에 저장된 원소를 바로 찾아볼 수 있다. 덕분에 배열에 접근하기 위한 시간복잡도는 \(O(1)\)이다.

 

그렇다면 임의 접근이 가능한 이유를 알아보자.

 

출처: https://velog.io/@eagle5424/%EB%A9%94%EB%AA%A8%EB%A6%AC-%EB%B0%B0%EC%97%B4array

크기가 4인 배열 num이 있다고 가정하자. 이때 배열은 연속된 메모리 공간에 요소를 순차적으로 저장한다. 따라서 각 요소는 다음 공식으로 바로 구할 수 있고 이 것이 임의 접근의 원리가 된다.

시작주소 + 배열의 크기 * 인덱스