동적배열 질문있어요

Question

c++기준으로 자료구조를 설명해주고 계신데 자바스크립트에는 동적배열, 정적배열의 구분이 없는거죠?

없다면 설명 내용으로 보아서는 동적배열에 가깝다고 생각하면 될까요?

그리고 동적배열에서 맨 앞 요소 삽입/삭제시 시간복잡도가 O(1)이라고 되어있는데 자바스크립트에서는 shift() unshift() 사용 시 O(n)으로 알고 있습니다. 제가 알고 있는 것이 맞는건가요?

Answer

안녕하세요 ㅎㅎ

네 동적배열 vector를 기반으로 자바스크립트의 Array를 대응해서 생각하시면 됩니다.

자바스크립트의 Array의 특징을 정하는 ECMA의 규격을 잠깐볼까요?

23.1.3.27 Array.prototype.shift ( )

This method removes the first element of the array and returns it.

It performs the following steps when called:

1. Let O be ? ToObject(this value).
2. Let len be ? LengthOfArrayLike(O).
3. If len = 0, then
1. a. Perform ? Set(O, "length", +0𝔽, true).
2. b. Return undefined.
4. Let first be ? Get(O, "0").
5. Let k be 1.
6. Repeat, while k < len,
1. a. Let from be ! ToString(𝔽(k)).
2. b. Let to be ! ToString(𝔽(k - 1)).
3. c. Let fromPresent be ? HasProperty(O, from).
4. d. If fromPresent is true, then
  1. i. Let fromVal be ? Get(O, from).
  2. ii. Perform ? Set(O, to, fromVal, true).
5. e. Else,
  1. i. Assert: fromPresent is false.
  2. ii. Perform ? DeletePropertyOrThrow(O, to).
6. f. Set k to k + 1.
7. Perform ? DeletePropertyOrThrow(O, ! ToString(𝔽(len - 1))).
8. Perform ? Set(O, "length", 𝔽(len - 1), true).
9. Return first.

이런식으로 되어있습니다. (shift)의 경우

앞의 설명처럼 따로 시간복잡도를 알려주지는 않습니다. 지금 보시면 k < len일 때까지 반복하는 것으로 최악의 경우 O(N)임을 알 수 있습니다.

또한, 배열의 다른 메서드의 시간복잡도도 공부하시라고 올려드립니다.

다만, 자바스크립트로 만약에 코테를 한다고 했을 때 array의 shift, unshift 등의 메서드에 관한 시간복잡도가 영향을 미치게 설계를 하지는 않아서 크게 상관하지는 않으셔도 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

감사합니다.

강사 큰돌 올림.