안녕하세요 ㅎㅎ

네 동적배열 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. 1. Let O be ? ToObject(this value).

2. 2. Let len be ? LengthOfArrayLike(O).

3. 3. If len = 0, then

   1. a. Perform ? Set(O, "length", +0𝔽, true).

   2. b. Return undefined.

4. 4. Let first be ? Get(O, "0").

5. 5. Let k be 1.

6. 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. 7. Perform ? DeletePropertyOrThrow(O, ! ToString(𝔽(len - 1))).

8. 8. Perform ? Set(O, "length", 𝔽(len - 1), true).

9. 9. Return first.

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

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

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

• push() : O(1), 최악 - O(N) / array 재할당이 발생

• pop() : O(1)

• shift() : O(N)

• slice() : O(N)

• sort() : O(NlogN)

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

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

감사합니다.

강사 큰돌 올림.