[자료구조] 배열

배열이란?

• 선형 자료 구조
• 동일한 데이터 타입을 연속적으로 저장한 자료 구조 
  • 그러므로 다른 데이터 타입을 담을 수 없다.

데이터를 순서대로 나열한다는 것과 메모리에 연속으로 저장한다는 점이 배열의 포인트이다. 

 

배열의 구성

• index : 배열의 순서 (0부터 시작)
• value : 배열의 값 
• element : index와 value를 통칭하는 요소

 

배열의 시간 복잡도

✅ 특정 인덱스를 알고 있는 경우 O(1)의 시간 복잡도를 가진다.

배열의 원소 추가/삭제를 무조건 O(n)의 복잡도를 가진다고 생각할 수 있지만, 인덱스를 이용해서 접근하는 경우 O(1)의 복잡도를 가진다.

• 특정 Index에 있는 원소를 참조하는 연산
• 특정 Index의 원소의 값을 변경하는 연산
• 배열의 가장 끝에 원소를 추가하는 연산
• 배열의 가장 끝의 원소를 삭제하는 연산

 

✅ 특정 인덱스를 모를 때, 추가/삭제를 한다면 O(n)의 시간 복잡도를 가진다. 

임의의 위치에 원소를 추가/삭제하는 연산은 O(n)의 시간 복잡도를 가진다.

왜냐하면 배열의 경우 연속적으로 값이 배치되어야 하기 때문이다.

 

삽입 연산이라면 삽입되는 index 이후의 요소들을 모두 뒤로 한 칸씩 밀어야 하고, 반대로 삭제 연산은 삭제한 index 이후의 요소들을 모두 앞으로 한 칸씩 당겨야 한다.
이 연산들은 최악의 경우 총 n번이 반복될 수 있기 때문에 O(n)의 시간복잡도를 가진다.