배열(Array) - 배열의 연산과 동적 배열

데이터를 저장하기 위해 주로 사용되는 배열은 알고리즘에서 가장 기본적인 자료구조라고 할 수 있습니다. 배열을 사용한 연산은 시간복잡도로 따지면 얼마나 오래 걸릴까요? 오늘은 배열의 연산과 동적 배열에 대해서 알아보도록 하겠습니다.

 

 

🧮 배열의 연산

 

➕ 삽입

 

배열에 값을 삽입할 때의 시간복잡도는, 데이터가 들어가는 위치에 따라 달라집니다. 하지만 시간복잡도는 항상 최악의 상황을 가정하게 됩니다. 우선 각각의 위치에 따른 시간복잡도를 알아보도록 하겠습니다.

 

➡️ 맨 앞 또는 중간에 데이터를 삽입하는 경우

맨 앞 / 중간에 데이터 삽입

맨 앞 또는 중간에 데이터를 넣게 되면 이미 들어가 있던 데이터들이 해당 위치를 비우기 위해 뒤로 한칸씩 옮겨가게 됩니다. 따라서 일반적으로 $O(n)$의 시간복잡도를 가지게 됩니다.

 

➡️ 맨 뒤에 데이터를 삽입하는 경우

맨 뒤에 데이터를 삽입하게 되는 경우에는 데이터의 이동이 없기 때문에 시간복잡도는 $O(1)$이 됩니다.

 

이 떄, 최악의 상황에서의 시간복잡도만 따지기 때문에 배열에 데이터 삽입시의 시간복잡도는 맨 앞 또는 중간에 데이터를 넣는 경우인 $O(n)$이 됩니다.

 

 

➖ 삭제

 

삽입과 마찬가지로, 맨 앞 또는 중간의 데이터를 삭제하는 경우 $O(n)$, 맨 뒤의 데이터를 삭제하는 경우 $O(1)$의 시간복잡도를 가지게 됩니다. 따라서 삭제의 경우에도 $O(n)$의 시간복잡도로 표현할 수 있습니다.

 

 

✔️ 탐색

 

원하는 값을 찾는 방법인데요, 배열에서는 원하는 값이 어디 있는지 알 수 없기 때문에 배열 전체를 확인해야 합니다. 만약 찾는 값의 위치가 맨 마지막에 있다면 앞의 모든 값을 탐색해야 하기 때문에 $O(n)$의 시간복잡도를 가지게 됩니다.

단, 배열은 index를 기반으로 이루어져있기 때문에 원하는 index위치의 값을 가져오는 경우의 시간복잡도는 $O(1)$ 이 됩니다.

 

 

✏️ 동적 배열

배열에는 길이가 고정되어있는 정적 배열과 변화가능한 길이를 가진 동적 배열이 있습니다. Javascript에는 정적 배열이 없으며, 모든 배열은 동적입니다.

 

만약 정적인 배열처럼 만들고 싶다면 다음과 같이 작성할 수 있습니다.

let arr = [1, 2, 3];

//배열의 크기 변경 불가능한 경우
Object.seal(arr);

//배열의 내용과 크기 모두 변경 불가능한 경우
Object.freeze(arr);

- seal() : 배열의 크기를 변경하지 못하게 합니다. 이 때, 배열 내의 값은 변경이 가능합니다.

- freeze() : 배열의 내용과 크기를 모두 변경하지 못하게 합니다.

 

실제로 콘솔에서 테스트해보면 변경이 불가능한 것을 확인할 수 있습니다.

 

정적 배열은 정해놓은 배열 크기의 메모리를 사용하지만, 동적 배열은 메모리를 그때그때 필요한 만큼만 사용합니다. 이처럼 메모리 사용량에는 차이가 있지만, 동적 배열에서의 삽입, 삭제, 탐색 과정은 정적 배열과 동일하므로 시간복잡도는 똑같습니다.