자바 스크립트 배열의 Big O

자바 스크립트 배열의 Big O

---

JavaScript의 배열은 항목을 추가하고 제거하여 수정하기가 매우 쉽습니다. 대부분의 언어 배열이 크기가 고정되어 있고 크기를 조정하려면 복잡한 작업이 필요하다는 사실을 다소가립니다. JavaScript를 사용하면 성능이 떨어지는 배열 코드를 쉽게 작성할 수 있습니다. 이것은 질문으로 이어집니다.

배열 성능과 관련하여 JavaScript 구현에서 어떤 성능 (큰 O 시간 복잡도 측면에서)을 기대할 수 있습니까?

모든 합리적인 JavaScript 구현에는 최소한 다음과 같은 큰 O가 있다고 가정합니다.

• 액세스-O (1)
• 추가-O (n)
• 준비중-O (n)
• 삽입-O (n)
• 삭제-O (n)
• 스와핑-O (1)

JavaScript를 사용하면 new Array(length)구문을 사용하여 배열을 특정 크기로 미리 채울 수 있습니다 . (보너스 질문 : O (1) 또는 O (n) 방식으로 배열을 생성합니까?) 이것은 기존 배열과 더 비슷하며 사전 크기 배열로 사용하면 O (1) 추가를 허용 할 수 있습니다. 순환 버퍼 로직이 추가되면 앞에 O (1)을 얻을 수 있습니다. 동적 확장 배열을 사용하는 경우 O (log n)는 두 가지 모두에 대한 평균 사례가됩니다.

여기에서 가정 한 것보다 더 나은 성능을 기대할 수 있습니까? 어떤 사양에도 설명되어 있지는 않지만 실제로는 모든 주요 구현이이면에서 최적화 된 배열을 사용할 수 있습니다. 작동중인 동적 확장 어레이 또는 기타 성능 향상 알고리즘이 있습니까?

추신

내가 궁금해하는 이유는 정렬 알고리즘을 연구하고 있기 때문이며, 대부분은 전체적인 큰 O를 설명 할 때 추가 및 삭제가 O (1) 작업이라고 가정하는 것 같습니다.

---

배열을 사용하여 배열을 구현하는 대부분의 언어와 달리 Javascript 배열은 객체이며 값은 일반 객체 값과 마찬가지로 해시 테이블에 저장됩니다. 이와 같이 :

• 액세스-O (1)
• Appending-Amortized O (1) (때로는 해시 테이블의 크기를 조정해야하며 일반적으로 삽입 만 필요함)
• Prepending-O (n) via unshift, 모든 인덱스를 재 할당해야하기 때문입니다.
• 삽입-값이 존재하지 않는 경우 상각 된 O (1). O (n) 기존 값을 이동하려는 경우 (예 :) splice.
• 삭제-상각 된 O (1)는 값을 제거하고, O (n)는를 통해 인덱스를 재 할당하려는 경우 splice입니다.
• 스와핑-O (1)

일반적으로 dict에서 키를 설정하거나 설정 해제하는 것은 O (1)로 분할되며 인덱스가 무엇이든 상관없이 배열에도 동일하게 적용됩니다. 영향을받는 모든 값을 업데이트해야하기 때문에 기존 값의 번호를 다시 매겨 야하는 모든 작업은 O (n)입니다.

참고 URL : https://stackoverflow.com/questions/11514308/big-o-of-javascript-arrays