[JS 알고리즘&자료구조] 배열 안의 데이터에 접근이 느린 이유

배열은 데이터가 정렬이 된 상태로 존재하며 데이터들은 정렬되어 있는 기준이 있다. 정렬되어 있다는 것은 유용하지만, 연산을 하는 데에 시간을 더 소모할 수 있다.

배열은 대부분 정렬되어 있는 데이터를 위해서 사용한다. 섞여있는 데이터에도 정렬을 쓸 수도 있지만 성능을 위해 권장되는 방법은 아니다. 배열을 사용하는 것은 정렬에는 아주 좋은 방법일 수 있으나 사실 성능적으로는 이득이 아닐 수 있다. 특히 입력과 제거에 있어서 그렇다.

입력 : 그 때 그 때 다름
제거 : 그 때 그 때 다름
탐색 : O(N)
접근 : O(1)

배열에 있는 데이터에 접근하는 것은 굉장히 빠르다. 객체와 마찬가지로 접근은 O(1)의 상수 시간을 가진다. 배열의 특정 인덱스에 위치하는 데이터를 요청한다고 하면 어떤 사람들은 해당 인덱스에 접근하기 위한 그 앞에 있는 모든 인덱스를 다 거쳐간다고 생각한다. (예를 들어, 90000번째 인덱스에 접근하기 위해 89999번까지 싹 다 훑는다던가) 하지만 그런 방식이 아니다. 각 인덱스의 엘리먼에 접근할 수 있는 지름길이 있다고 생각하면 편하다. 

탐색도 객체와 마찬가지로 배열 안에 데이터가 많아지면 많아질수록 훑어야 하는 데이터가 많아진다는 얘기이기 때문에 O(N)만큼의 시간이 걸린다.

삽입과 제거는 완전히 다르다. 우선 입력부터 보자. 입력은 어디에 입력을 하느냐에 따라서 달라진다. 만약 배열의 끝에 데이터를 추가하는 거라면 push를 사용하면 될 것이고 이 때는 상수 시간 O(1)이 소요된다. 인덱스를 하나 추가하고 데이터를 넣어주기만 하면 되기 때문에 아주 단순한 작업이다. 그러나 문제는 배열의 시작에 데이터를 추가할 때이다. 맨 앞에 데이터가 하나 추가됨으로써 뒤에 있는 모든 데이터들의 인덱스를 조정해줘야하기 때문이다. 이 경우에는 O(N)의 시간이 소요된다. 이와 같은 이유로 맨 앞의 데이터를 제거하는 것도 당연히 문제가 된다. 배열 맨 앞에 데이터를 추가하거나 혹은 삭제하는 작업은 성능이 좋을 수가 없다. 그러나 사용해야할 때는 사용해야 한다. 단지 끝에 추가하거나 삭제하는 것에 비해서 비효율적일 뿐이다.