JS Array prototype 함수의 시간 복잡도 비교(indexOf, concat ...)

자바스크립트의 배열 메서드는 내부적으로 반복문을 사용하여 배열의 요소를 탐색하고, 이에 따라 시간 복잡도가 달라집니다. 배열 메서드의 시간 복잡도를 비교하여 가장 효율적인 함수와 비효율적인 함수를 구분하는 것이 중요합니다. 아래는 주요 배열 메서드들의 시간 복잡도와 이들의 효율성에 대한 설명입니다.

1. indexOf의 시간 복잡도

Array.prototype.indexOf()는 배열에서 특정 값을 찾고 그 인덱스를 반환하는 메서드입니다.

• 시간 복잡도: O(n)
  • indexOf는 배열의 첫 번째 요소부터 끝까지 순차적으로 탐색하여 일치하는 값의 인덱스를 찾습니다. 배열의 길이가 n이라면 최악의 경우 배열의 모든 요소를 확인해야 하므로 시간 복잡도는 **O(n)**입니다.

2. 배열 함수들의 시간 복잡도

다음은 배열에서 자주 사용되는 다른 메서드들의 시간 복잡도입니다. 각 메서드의 시간 복잡도는 주로 배열의 길이에 비례하는 경우가 많습니다.

2-1. push()

배열의 끝에 요소를 추가합니다.

• 시간 복잡도: O(1)
  • push는 배열의 마지막에 요소를 추가하는 작업으로, 배열의 크기에 상관없이 일정 시간이 걸리기 때문에 **O(1)**입니다. 이는 상수 시간에 수행됩니다.

2-2. pop()

배열의 마지막 요소를 제거하고 그 값을 반환합니다.

• 시간 복잡도: O(1)
  • pop은 배열의 마지막 요소를 제거하는 작업으로, 끝에서 한 번만 요소를 제거하므로 **O(1)**입니다.

2-3. shift()

배열의 첫 번째 요소를 제거하고 그 값을 반환합니다.

• 시간 복잡도: O(n)
  • shift는 배열의 첫 번째 요소를 제거한 후, 나머지 요소를 한 칸씩 앞으로 당겨야 합니다. 따라서 **O(n)**의 시간 복잡도를 가집니다.

2-4. unshift()

배열의 첫 번째 자리에 새로운 요소를 추가합니다.

• 시간 복잡도: O(n)
  • unshift는 배열의 첫 번째 자리에 요소를 추가한 후, 나머지 요소들을 한 칸씩 뒤로 밀어야 하기 때문에 **O(n)**입니다.

2-5. concat()

두 개 이상의 배열을 합칩니다.

• 시간 복잡도: O(n)
  • concat은 기존 배열의 요소를 복사하고 새로운 배열을 반환합니다. 복사하려는 배열의 길이에 따라 **O(n)**의 시간이 걸립니다.

2-6. slice()

배열의 일부분을 추출하여 새로운 배열을 반환합니다.

• 시간 복잡도: O(k)
  • slice는 배열에서 k 개의 요소를 추출하여 새로운 배열로 반환합니다. k는 추출하려는 요소의 개수입니다.

2-7. splice()

배열의 특정 위치에서 요소를 추가, 제거 또는 교체합니다.

• 시간 복잡도: O(n)
  • splice는 요소를 삽입하거나 삭제한 후, 배열의 나머지 요소를 이동시켜야 하므로 **O(n)**입니다.

2-8. forEach()

배열의 각 요소에 대해 주어진 함수를 실행합니다.

• 시간 복잡도: O(n)
  • forEach는 배열의 모든 요소에 대해 한 번씩 함수를 호출하므로 배열의 길이 n에 비례하여 **O(n)**입니다.

2-9. map()

배열의 각 요소를 주어진 함수로 변환하여 새로운 배열을 반환합니다.

• 시간 복잡도: O(n)
  • map은 배열의 각 요소에 대해 변환 작업을 수행하므로 **O(n)**입니다.

2-10. filter()

배열에서 조건에 맞는 요소만을 필터링하여 새로운 배열을 반환합니다.

• 시간 복잡도: O(n)
  • filter는 배열을 순회하면서 조건을 체크하고, 조건에 맞는 요소만 새 배열에 추가합니다. 따라서 배열의 길이에 비례하는 **O(n)**입니다.

2-11. find()

배열에서 조건에 맞는 첫 번째 요소를 반환합니다.

• 시간 복잡도: O(n)
  • find는 배열을 순차적으로 탐색하면서 조건에 맞는 요소를 찾습니다. 최악의 경우 배열을 끝까지 탐색해야 하므로 **O(n)**입니다.

2-12. includes()

배열에 특정 값이 포함되어 있는지 여부를 확인합니다.

• 시간 복잡도: O(n)
  • includes는 배열을 처음부터 끝까지 확인하며 값을 찾습니다. 최악의 경우 전체 배열을 확인하므로 **O(n)**입니다.

3. 배열 함수들의 시간 복잡도 순위

• O(1):
  • push(), pop()
• O(n):
  • indexOf(), shift(), unshift(), concat(), splice(), forEach(), map(), filter(), find(), includes()
• O(k):
  • slice(): k는 추출할 요소의 개수

4. 성능 최적화를 위한 팁

• **indexOf()**를 사용하여 배열에서 값을 찾는 경우, 배열이 크면 **O(n)**의 시간이 걸리므로 Set 또는 Map을 사용하여 더 빠르게 검색할 수 있습니다.
  • 예를 들어, 배열이 크고 자주 검색이 필요한 경우, 배열을 Set으로 변환하면 검색 시간이 **O(1)**로 단축될 수 있습니다.
• **shift()**나 **unshift()**는 O(n) 시간이 걸리므로, 배열의 앞에서 요소를 추가하거나 제거하는 작업이 자주 필요하다면 링크드 리스트와 같은 데이터 구조를 사용하는 것이 더 효율적일 수 있습니다.

5. 결론

배열 메서드는 사용 편의성에 따라 다양한 메서드를 제공하지만, 시간 복잡도 측면에서 각각의 메서드는 고유의 특성을 갖습니다. 성능이 중요한 경우, 배열 메서드를 사용할 때 그 시간 복잡도를 고려하여 효율적인 메서드를 선택하는 것이 중요합니다. 예를 들어, 배열에서 요소를 검색할 때 **indexOf**를 사용한다면, 큰 배열에서는 성능 문제가 발생할 수 있기 때문에 **Map**이나 **Set**을 사용하여 성능을 최적화할 수 있습니다.