배열과 객체의 성능 평가

객체의 빅 오(Big O)

객체를 사용하는 경우

• 순서가 필요 없는 경우
• 신속한 접근/삽입 및 삭제가 필요한 경우
  • 이때, 신속하게 처리할 수 있다는 의미는 접근, 삽입, 삭제하는 시간이 상수 시간 의미
  • 그러나, 탐색은 선형 시간임
    • 탐색은 접근과 다르게, 특정한 정보가 어떤 값에 있는지 확인하는 것
    • ex) true 값을 찾기 위해, 객체의 key들을 탐색. key (속성)들이 많을 수록 탐색하는 시간이 늘어

객체 관련 메서드

 

배열의 빅 오(Big O)

배열을 사용하는 경우

• 객체는 정렬이 필요한 경우 사용 (그러나 연산에 있어서는 객체보다 시간이 더 걸릴 수 있음)
• 특히 입력과 삭제가 필요한 경우
  • 접근은 선형 시간이 걸림
  • 삽입과 제거는 어느 위치의 요소에 작업하는지에 따라 결과가 다름
    • push(배열 마지막 위치에 추)는 O(1), 배열의 첫번째 위치에 추가하는 경우에는 O(N) (모든 배열의 인덱스 번호를 변경해야하기 때문). 동일하, 배열의 첫번째 요소를 삭제하는 경우에도 O(N) 시간이 걸림
    • 이에 따라, push & pop은 shift & unshift 작업보다 시간이 빠름 (비어있는 배열 제외)

배열 메소드 정리

1. push() - O(1):
   • push() 메서드는 배열의 끝에 요소를 추가합니다.
   • 시간 복잡도는 일반적으로 상수 시간이 소요되므로 O(1)입니다.
2. pop() - O(1):
   • pop() 메서드는 배열의 끝에서 요소를 제거합니다.
   • 마지막 요소를 제거하므로 상수 시간이 소요되며 O(1)입니다.
3. shift() - O(n):
   • shift() 메서드는 배열의 첫 번째 요소를 제거하고 나머지 요소를 왼쪽으로 이동합니다.
   • 모든 요소를 왼쪽으로 이동해야 하므로 배열의 길이(n)에 비례하는 시간이 소요되므로 O(n)입니다.
4. unshift() - O(n):
   • unshift() 메서드는 배열의 시작 부분에 요소를 추가하고 모든 요소를 오른쪽으로 이동시킵니다.
   • 모든 요소를 오른쪽으로 이동해야 하므로 배열의 길이(n)에 비례하는 시간이 소요되므로 O(n)입니다.
5. concat() - O(n):
   • concat() 메서드는 하나 이상의 배열을 결합합니다.
   • 모든 배열의 요소를 하나로 결합해야 하므로 모든 배열의 길이의 합에 비례하는 시간이 소요되므로 O(n)입니다.
6. slice() - O(k):
   • slice() 메서드는 배열의 일부를 추출하여 새로운 배열을 반환합니다.
   • 반환되는 배열의 길이는 추출한 요소 수(k)에 의해 결정되므로 시간 복잡도는 O(k)입니다.
7. splice() - O(n):
   • splice() 메서드는 배열에서 요소를 추가하거나 제거하며, 다른 요소를 이동합니다.
   • 제거한 요소의 수와 이동한 요소의 수가 배열의 길이(n)에 비례하므로 O(n)입니다.
8. forEach() - O(n):
   • forEach() 메서드는 배열의 각 요소에 대해 주어진 함수를 실행합니다.
   • 배열의 모든 요소를 한 번씩 방문해야 하므로 O(n)입니다.
9. map() - O(n):
   • map() 메서드는 배열의 각 요소에 대해 주어진 함수를 실행하고 그 결과를 새로운 배열에 저장합니다.
   • 모든 요소를 방문하고 새로운 배열을 생성하므로 O(n)입니다.
10. filter() - O(n):
    • filter() 메서드는 주어진 조건을 만족하는 배열의 요소를 추출하여 새로운 배열을 생성합니다.
    • 모든 요소를 확인하고 조건을 검사하므로 O(n)입니다.
11. sort() - O(n log n) (평균적인 경우):
    • sort() 메서드는 배열의 요소를 정렬합니다.
    • JavaScript 엔진은 일반적으로 퀵소트(Quick Sort) 알고리즘 또는 머지소트(Merge Sort) 알고리즘을 사용합니다.
    • 평균적인 경우에는 O(n log n)의 시간 복잡도를 가집니다. 이것은 배열의 길이(n)에 대해 로그 선형(log-linear)한 증가 추이를 의미합니다.
    • 그러나 최악의 경우에는 O(n^2)의 시간 복잡도를 가질 수 있습니다. 이는 정렬된 배열을 다시 정렬할 때 나타날 수 있습니다.

요약

참고

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array