자바스크립트 시간복잡도

자바스크립트에서의 시간 복잡도는 주로 사용되는 연산과 알고리즘에 따라 다를 수 있다.

• 배열의 접근: 배열에서 특정 인덱스의 요소에 직접 접근하는 것은 O(1)의 시간 복잡도를 가진다.

• 배열의 순회: 배열의 모든 요소를 순회하는 것은 O(n)의 시간 복잡도를 갖는다. (n은 배열의 길이)

• 객체 속성 접근: 객체의 속성에 직접 접근하는 것도 O(1)의 시간 복잡도를 가진다. 그러나 일부 엔진에서는 객체의 크기가 크면 성능이 떨어질 수 있다.

• 정렬 알고리즘: 자바스크립트의 Array.prototype.sort는 일반적으로 퀵 정렬 또는 병합 정렬과 같은 효율적인 알고리즘을 사용하며, O(n log n)의 시간 복잡도를 가진다.

• 문자열 연산: 문자열 연산도 일반적으로 O(n)의 시간 복잡도를 가진다. 예를 들어, 문자열의 길이에 비례하여 시간이 증가하는 경우가 많다.

• 객체의 크기 확인: 객체의 속성 수를 확인하는 것은 O(1)의 시간 복잡도를 가진다.

• 함수 호출: 함수 호출은 일반적으로 O(1)의 시간 복잡도를 갖는다. 그러나 함수 내부에서의 작업에 따라 시간 복잡도가 달라질 수 있다.

1. push() - O(1)
   배열의 끝에 원소를 추가한다.
   끝에만 추가하는 것이므로 O(1)의 복잡도를 가진다.

2. pop() - O(1)
   배열의 끝에 원소를 삭제한다.
   끝 요소만 제거하므로 O(1)의 시간 복잡도를 가진다.

3. shift() - O(n)
   배열의 첫번째 시작 원소를 삭제한다.
   나머지 배열의 요소를 한칸씩 다 앞으로 땡겨와야하므로 O(n)의 시간복잡도를 가진다

4. unshift() - O(n)
   배열의 첫번째에 원소를 추가한다.
   나머지 배열의 요소를 다 한칸씩 뒤로 밀어야하므로 O(n)의 시간복잡도를 가진다.

5. splice() - O(n)
   원소를 추가 , 삭제, 대체한다.
   splice 메서드 같은 경우는 삭제하려는 요소의 위치와 배열 개수에 따라서 시간 복잡도가 달라진다.
   삭제 하려는 요소가 배열의 맨 끝에 존재 할 경우에는 O(1)의 시간 복잡도이지만,
   요소가 중간에 위치할 경우 O(n)의 시간 복잡도를 가진다.

6. sort() - O(nlog(n))
   배열의 요소들을 정렬한다.
   O(n log(n))의 시간복잡도를 가진다.
   O(n log(n)) 복잡도는 O(n)보다는 높은 시간 복잡도를 가지지만 O(n^2)보다는 낮은 시간 복잡도를 가진다.

7. concat() - O(n)
   여러 배열을 합쳐 합친 새로운 배열을 만든다.
   O(n+m)이라고 표현하지만 이는 O(n)과 마찬가지이다.

8. slice()- O(n)
   배열의 시작과 끝 인덱스 사이의 배열을 복제하여 반환한다.
   보통 자르는 요소를 k개라 했을때, O(k)의 시간 복잡도를 가진다.

9. forEach() - O(n)
   배열의 각 원소를 실행시키는 함수

10. Map() - O(n)
    콜백ㅎ마수의 결과값으로 새로운 배열을 반환한다.

11. filter() - O(n)
    조건이 참인 새로운 배열을 반환한다.

• 그 밖에 reduce, some, every 등등 배열 전체를 순회하는 메서드
  배열 전체를 순회하므로 O(n)의 시간복잡도를 가진다.