핵심만 먼저 말하자면 객체의 키/값 추가는 O(NlogN)정도의 시간복잡도를 가진다고 한다.
(정확하지는 않고 O(N)이상의 시간복잡도를 가진다고만 알아둬도 괜찮다)
문제를 풀던 도중 효율성에서 100점을 맞지 못했다.
시간복잡도를 생각하며 문제를 풀었다고 생각했는데 의아했고
다른 방식으로 문제를 풀어 제출했더니 100점이 나왔다.
사실 여기서 중요한 것은 100점이 나왔다는 것이 아니라
더 좋은 시간복잡도를 가지고 있는데 100점이 나오지 않았던 코드였다.
(코드는 하단에 있다)
분명 sort를 사용한 문제는 시간복잡도 O(NlogN)이 나올거고
객체를 사용한 문제는 시간복잡도 O(N)이 나올거라고 생각했는데
아래와 같은 코드 작성을 통해 시간을 계산해봐도 문제는 객체일 수 밖에 없었다.
(sort를 사용한 것이 훨씬 더 빨랐으며 100만단위 규모(문제 사이즈)에서 12배가량 빨랐다)
function solution(A) { //내가 생각하는 O(NlogN)
let arr = A.sort((a,b) => a-b)
let start = A.indexOf(1)
if(arr.indexOf(1) === -1){
return 1
}
else{
for(let i = start ; i < arr.length ; i++){
if(arr[i+1] > arr[i]+1){
return arr[i]+1
}
}
return arr[arr.length-1]+1
}
}
function solutionTwo(A) { //내가 생각했던 O(N)
let obj = {}
for(let i = 0 ; i < A.length ; i++){
obj[A[i]] = 1
}
for(let i = 1 ; i <= 100000 ; i++){
if(obj[i] === 0) return i
}
}
let arr = []
for(let i = 10000000; i > -10000000 ; i--){ //정렬이 우세해서 비정렬 상태로 만들었다
arr.push(i)
}
let befor = Date.now()
solution(arr)
let after = Date.now()
let beforT = Date.now()
solutionTwo(arr)
let afterT = Date.now()
console.log(after-befor, afterT-beforT)
객체의 시간복잡도를 검색해도 객체 자체에 대한 이야기는 나오지 않았고
오히려 공식문서 등에서는 시간복잡도에 대한 언급조차 되지 않았다.
외국인들이 쓴 칼럼을 봐도 객체 짱짱맨!! 같은 찬양글만 보였을 뿐이고
나와 같은 궁금증을 가진 사람은 없는 것 같았다.
도움의 손길을 찾아보다가 문득 얼마 전 멘토님이 보내주셨던 리뷰에서
부담없이 질문해도 괜찮다는 말씀이 생각났고
질문을 드리니 생각해보지 않았던 말씀을 해주셨다.
시간복잡도 계산에서 조건동일에 대한 부분을 언급하는 것을 본 기억이 없었는데(좀 당연하기도 하지만)
처리갯수(N)과 관련되지 않은 다른 부분에서 동작마다 시간이 다를 수 있다는 것이 새로웠고
그 뒤에 말씀해주신 객체에 값을 추가할 때 정렬된다는 놀라운 사실을 알려주셨다.
결국 객체에 값을 할당하고 읽는 작업에는 우리가 생각하는 O(1)의 시간이 소모되지만
키 자체를 추가하면 재정렬이 계속 들어가기 때문에 O(N?/정렬시간)*O(N/for문 1회)이 진행된 것이었다.
그래서 평소에는 대규모 데이터를 처리하면서 고정된 몇개의 키를 사용했기 때문에 시간복잡도 정렬문제를 겪지 않았고
그로 인해 객체를 맹신하게 된 것이었고
이번에는 모든 값들이 다 달랐기 때문에(내가 만든 수치지만) 정렬을 N번 진행해버리는 참사가 벌어진 것이었다.
대규모 데이터에서 소규모 키 변동인 경우에는 객체가 유리하고
대규모 데이터에서 서로 다 다른 값인 경우에는 객체가 불리한 것이라고 마무리할 수 있다.
(배열에 넣고 정렬때리면 NlogN이지만 정렬해가며 추가하는 것은 N*정렬이기 때문에)
@멘토님의 대화를 보던 중 생각난 포인트 하나 더 추가
