배열 (Array)
같은 타입의 변수들로 이루어진 집합.
배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)이다.
배열의 인덱스는 0부터 시작해 0, 1, 2, 3, ..., size - 1 의 인덱스를 참조할 수 있다.
배열 A의 n번 째에 해당하는 변수는 A[n]으로 표시한다.
배열 내 연산은 크게 접근(access), 검색(search), 추가(add), 제거(remove) 으로 나뉜다.
아래는 크기가 10인 Integer형 배열이며,
1. 접근
접근은 배열 내에서 n번째 인덱스에 해당하는 값을 찾아내는 연산이다.
배열의 접근은 O(1)의 시간복잡도를 갖는다. 따라서 찾고자 하는 값이 몇 번째 인덱스에 있는지 알고 있다면 굉장히 빠른 검색 속도를 갖는다. 배열의 첫번째 변수에는 시작 주소값이 저장되고, A[n]의 값을 찾아가기 위해 시작 주소값에서 단순 사칙연산이 수행되기 때문이다.
2. 검색
배열의 검색은 순차검색이다. 인덱스를 알지 못할 때 원하는 값을 찾기 위해 배열을 하나하나 확인해야한다.
A[3]의 값을 찾기 위해 A[0], A[1]... 을 순서대로 검색한다. 따라서 최대 O(n)의 시간 복잡도를 가진다.
3. 추가, 삭제
추가와 삭제는 먼저 빈 공간이 마련되 있다를 전제로 한다.
추가, 삭제의 시간복잡도는 앞서 말한 접근과 검색의 방법 차이에 따라 시간복잡도가 나뉜다.
A[6]에 5라는 값을 넣고, 혹은 빼고 싶을 때 해당 인덱스를 정확하게 알고 있다면 접근의 개념으로 O(1)의 시간복잡도를 가지지만 해당 인덱스를 찾아야한다면 검색의 시간복잡도인 O(n)에 해당한다.
댓글