동적배열 질문있어요

Question

c++기준으로 자료구조를 설명해주고 계신데 자바스크립트에는 동적배열, 정적배열의 구분이 없는거죠? 없다면 설명 내용으로 보아서는 동적배열에 가깝다고 생각하면 될까요? 그리고 동적배열에서 맨 앞 요소 삽입/삭제시 시간복잡도가 O(1)이라고 되어있는데 자바스크립트에서는 shift() unshift() 사용 시 O(n)으로 알고 있습니다. 제가 알고 있는 것이 맞는건가요?

kundol · 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 a. Perform ?  Set (O, "length" , +0 𝔽, true ). b. Return undefined . 4. Let first be ?  Get (O, "0" ). 5. Let k be 1. 6. Repeat, while k < len, a. Let from be !  ToString ( 𝔽 (k)). b. Let to be !  ToString ( 𝔽 (k - 1)). c. Let fromPresent be ?  HasProperty (O, from). d. If fromPresent is true , then i. Let fromVal be ?  Get (O, from). ii. Perform ?  Set (O, to, fromVal, true ). e. Else, i. Assert : fromPresent is false . ii. Perform ?  DeletePropertyOrThrow (O, to). 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)임을 알 수 있습니다. 또한, 배열의 다른 메서드의 시간복잡도도 공부하시라고 올려드립니다. push() : O(1), 최악 - O(N) / array 재할당이 발생 pop() : O(1) shift() : O(N) slice() : O(N) sort() : O(NlogN) 다만, 자바스크립트로 만약에 코테를 한다고 했을 때 array의 shift, unshift 등의 메서드에 관한 시간복잡도가 영향을 미치게 설계를 하지는 않아서 크게 상관하지는 않으셔도 됩니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 감사합니다. 강사 큰돌 올림.