👩‍💻배경

코테 문제 풀이 중 파이썬으로 풀이를하면 heapq라는 내장 라이브러리를 활용해 최소힙을 이용해 쉽게 문제풀이를 할 수 있지만, 안타깝게도 js에는 최소힙을 만들어줘야한다.
또 deque를 통해 쉽게 double ended queue 자료구조를 쉽게 활용해서 popleft()를 통해 O(1)시간으로 덱의 맨 앞요소를 제거할 수도 있지만 popleft()와 같이 시간복잡도를 확 줄이는 방식 말고 class로 deque를 구현해야 O(1)을 만족하는 듯 싶다.
js자체가 브라우저에서 돌아가는 lightweight언어라서 성능최적화 자체를 무시할 경우가 많지만 코테라는 특수성 등 특정 환경에서는 비용적인 측면에서 최적화를 하는 습관화하는게 좋다고 판단하여, 이 기회에 정리를 해봤다.

1. 배열요소 접근과 수정

const arr = ['A', 'B', 'C', 'D', 'E', 'F'];

• arr에서 arr[2]에 접근(Access)할 때 어떤 일들이 일어나나?
  ❌ arr라는 배열을 0번째 인덱스부터 순회하면서 2번째 인덱스 읽기? O(n)?
  ⭕ 인덱스로 접근할 때는 물리적 메모리 주소와 논리적 메모리 주소 영역이 동일하므로 일일히 배열을 순회하는 것이 아니라 바로 인덱스에 해당되는 주소로 값을 가져올 수 있다. O(1) !

• 배열값을 수정하는 것

  • arr[2]='G'또한 O(1) ! : 인덱스는 주소값인데, 'G'라는 값을 해당 주소에다가 할당해주는 것이므로 접근하기(O(1))이고 할당해주기(O(1))로 시간복잡도는 O(1) !

2. Linear Search : 배열 순회하면서 값 찾기 ft. indexOf(), findIndex()

• ES6으로는 findIndex('C'), ES5로는 indexOf('C')에 해당되는 함수는 arr에서 특정 값이 있는 인덱스값을 찾고 싶을 때 쓴다.
• 해당 함수는 O(n) 시간복잡도를 지니는데, 0번 인덱스부터 시작해서 구할는 인자 'C'의 인덱스를 찾을 때까지 순회한다.

3. 배열요소 추가 & 삭제

➕ 배열요소 추가하기

➕ push() 👉 O(1)

• 배열의 맨 끝에 요소 추가만 하므로 시간복잡도는 O(1)

const arr = ['A', 'B', 'C', 'D', 'E', 'F'];
arr.push('G');
console.log(arr); /*['A', 'B', 'C', 'D', 'E', 'F','G']*/

➕ unshift() 👉 O(n)

• 배열의 맨 앞에 요소 추가 :시간복잡도는 O(n)

const arr = ['A', 'B', 'C', 'D', 'E', 'F'];
arr.unshift('G');
console.log(arr); /*['G','A', 'B', 'C', 'D', 'E', 'F']*/

• arr배열의 맨 앞 인덱스는 0인데 arr[0]의 주소값 자리의 값에 'G'를 할당하고, 다음 arr[1]의 주소값 자리에는 이전에 인덱스 0이었던 'A'값이 들어감.
• 하나씩 주소값에 있던 값들을 주소값+1해(O(n))주고 값을 할당(O(1))해줘야하므로 시간 복잡도는 O(n)

➖ 배열요소 삭제하기

➖ pop() 👉 O(1)

• 배열의 뒤의 요소 삭제만 하므로 시간복잡도는 O(1)

const arr = ['A', 'B', 'C', 'D', 'E', 'F'];
console.log(arr.pop()); //'F'
console.log(arr); /*['A', 'B', 'C', 'D', 'E']*/

➖ shift() 👉 O(n)

• 배열의 맨앞의 요소 삭제 :시간복잡도는 O(n)
• 위에서 unshift() 함수에서 맨 앞에 요소를 추가해줬을 때 뒤의 인덱스들을 하나씩 밀어줘야하는 상황과 동일

const arr = ['A', 'B', 'C', 'D', 'E', 'F'];
console.log(arr.shift()); //'A'
console.log(arr); /*['B', 'C', 'D', 'E','F']*/

4. Others (ft. O(n))

❇️ splice()

• 배열 요소를 특정 인덱스(indexOf()와 같이)에 삭제/삽입하므로 특정 인덱스에 접근하기 위해 시간복잡도는 O(n)

특징들

• sparse array (빈 값이 있는 배열)의 빈 공간을 유지함

const arr = ['A', , 'B', ,'C', 'D', ,'E', 'F'];
console.log(arr.splice(1,2)); // [empty,'B'] 
console.log(arr); // ['A', empty, 'C', 'D', empty, 'E', 'F']

• array가 아닌 object에 splice()호출했을 때 👉 splice()는 this의 length 속성을 읽어서 integer 키의 속성을 length속성에 맞게 업데이트해줌

const arrayLike = {
  length: 3,
  unrelated: "foo",
  0: 5,
  2: 4,
};
console.log(Array.prototype.splice.call(arrayLike, 0, 1, 2, 3)); 
// [ 5 ]
console.log(arrayLike); //0인 키값부터 1개 삭제하고 해당 키에 차례대로 2, 3 넣기 0의 값은 5 👉 2 , 1 👉 2 , 3 👉 4 
// { '0': 2, '1': 3, '3': 4, length: 4, unrelated: 'foo' }

• 인자의 개수 및 인자의 값에 따라 하는 역할이 조금 달라짐!

splice(start) // start인덱스부터 요소 삭제
splice(start, deleteCount) // start인덱스부터 deleteCount개의 요소 삭제
splice(start, deleteCount, item0) // start인덱스부터 deleteCount개의 요소 삭제하고 start위치에 item0 삽입
splice(start, deleteCount, item0, item1) // start인덱스부터 deleteCount개의 요소 삭제하고 start위치에 item0, item1 삽입
splice(start, deleteCount, item0, item1, /* … ,*/ itemN) // start인덱스부터 deleteCount개의 요소 삭제하고 start위치에 item1, /* … ,*/ itemN 삽입

인자들

• start : 필수⭕인 인자.
  • 음수라면 배열 끝에서 역으로 count를 함 (start+array.length)
  • 인자없이 전달한다면 삭제❌, cf. splice(undefined) === splice(0)
• deleteCount : 필수❌ 인자.
  • start 위치부터 샂게할 element의 개수
  • 생략하거나, start보다 값이 크거나 같으면 start위치부터 끝까지 모든 요소들을 삭제
  • itemN (추가할 요소)를 전달하고, 시작 위치부터 모든 요소들을 삭제하고 싶다면 Infinity를 전달해야 함 (undefined전달 시 0으로 변환됨)
  • 0이거나 음수값이면 삭제 ❌, 이 경우 반드시 하나 이상 추가할 요소를 제공해야함 (삭제도 안하고 추가도 안할거면 이 함수 왜 호출해)
• item0,...,itemN : 필수❌ 인자. 없으면 삭제만 함.

🛠️2023-06-24 ~ 업데이트예정

filter()

map()

find()

findIndex()

reduce()

forEach()

flatMap()

6. sort()

• O(N * log N) : quicksort 알고리즘을 사용함!

5. concat() 👉 O(n) ? O(n+m)

• O(n)일 때 : arr1을 순회하면서 복사하고 'G'라는 요소 하나 추가 👉 O(n) O(n+1)에서 상수는 무시

const arr1 = ['A', 'B', 'C', 'D', 'E', 'F'];
const arr2 = arr1.concat('G'); //['A', 'B', 'C', 'D', 'E', 'F','G']

• O(n+m)일 때 : arr1와 arr2을 순회하면서 각각 복사해서 배열의 길이가 다른 두 배열들을 순회하는 시간 복잡도인 👉 O(n+m)

const arr1 = ['A', 'B', 'C', 'D', 'E', 'F'];
const arr2 = arr1.concat('G'); 
const arr3 = arr1.concat(arr2); 
console.log(arr3);//['A', 'B', 'C', 'D', 'E', 'F','A', 'B', 'C', 'D', 'E', 'F','G'] 

---

😊 마치면서

• 물론 시간복잡도도 줄이면서 깔끔한 코드가 best case
• But 어쩔 수 없이 내장함수를 통해서 코드길이를 단축시키거나 깔끔하게 하기 위해서는 시간복잡도를 좀 희생해야할 경우도 있고, 반대로 시간복잡도가 worst case인 경우 문제가 될 경우에는 깔끔한 코드를 포기해야할 때도 있는 것같다.

📝 요약

시간복잡도	함수명
O(1)	at() , entries() , every() , isArray() , keys() , pop() , push() , shift() , values() , with()
O(n)	concat() , copyWithin() , fill() , filter() , find() , findIndex() , findLast() , findLastIndex() , flat() , flatMap() , forEach() , from() , fromAsync() , group() , groupToMap() , includes() , indexOf() , join() , lastIndexOf() , map() , of() , reduce() , reduceRight() , reverse() , slice() , some() , splice() , toLocaleString() , toReversed() , toSpliced() , toString() , unshift()
O(n log n) , linear time on average	sort() , toSorted()

---

📖 References

• 자바스크립트 배열 연산함수 시간 복잡도
• javascript mozilla docs
• javascript-arrays-and-big-o